一、简介 二叉排序树 亦称二叉查找树 ,是树形数据结构的一种,在一般情况下,二叉排序树的查找效率要高于 普通链表,它要么是一棵空树,要么具有以下性质:
若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值 ; 若它的右子树不为空,则右子树上所有结点的值均大于它的根结点的值 ; 它的左、右子树分别为二叉排序树 。下面是一棵标准的二叉排序树
二、二叉排序树的生成与节点插入 2.1、生成 1、创建Node类和Tree类 创建一个Node 类作为二叉排序树的节点类 ,这里省略getter、setter和toString方法
1 2 3 4 5 6 7 8 public class Node { int data; Node left; Node right; }
创建一个Tree 类,这个类包含一个Node类型的root属性。
1 2 3 4 public class Tree { Node root; }
2、生成思路 既可以在创建二叉树对象时直接使用有参构造函数传入根节点对象,也可以在添加节点时才插入root节点
注:当一棵树root节点为空时,第一个插入该树的节点就是根节点。
2、节点插入 1、思路 在Tree类中添加一个addNode方法,如果当前树的根节点为空,那么将要添加到二叉排序树的节点设置为根节点 ,否则就调用root节点对象的add方法 ,在root对象的add方法中:
如果传入要添加的节点node为空,那么直接返回,不做添加。 如果传入要添加的节点node的数值小于当前节点的数值,那么进行判断,如果当前节点的左子树为空,那么直接让当前节点的左子树为要添加的节点node。否则向左进行递归添加,判断待添加节点node的数据与当前左子节点数据的关系,重复以上操作。 如果传入要添加的节点node的数值大于等于当前节点的数值,这种情况需要尽量避免,这个时候进行判断,如果当前节点右子树为空,那么令当前节点右子树等于要添加的节点node。否则向右进行递归添加,判断待添加节点node的数据与当前右子节点数据的关系,重复以上操作。 2、插入节点–Tree 1 2 3 4 5 6 7 public void addNode (Node node) { if (this .root == null ) { this .root = node; } else { this .root.add(node); } }
3、节点的比较与插入–Node 比较节点树的静态方法 如下
1 2 3 public static boolean compare (Node node1,Node node2) { return node1.data > node2.data; }
Node类中插入节点的方法如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public void add (Node node) { if (node == null ) { return ; } if (compare(this ,node)) { if (this .left == null ) { this .left = node; } else { this .left.add(node); } } else { if (this .right == null ) { this .right = node; } else { this .right.add(node); } } }
三、二叉树的前中后序遍历 前序遍历的顺序:根节点–左子节点–右子节点
中序遍历的顺序:左子节点–根节点–右子节点
后序遍历的顺序:左子节点–右子节点–根节点
3.1、递归实现 1、前序遍历 先输出当前节点,然后判断当前节点的左子树是否为空,如果不为空,就向左递归进行前序遍历。然后判断当前节点的右子树是否为空,若不为空,向右递归进行前序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void preOrder () { if (this .root != null ) { this .root.preOrder(); } else { System.out.println("二叉树为空,无法遍历!" ); } } public void preOrder () { System.out.println(this ); if (this .getLeft() != null ) { this .getLeft().preOrder(); } if (this .getRight() != null ) { this .getRight().preOrder(); } }
2、中序遍历 先判断当前节点左子树是否为空,若不为空,向左递归进行中序遍历,然后输出当前节点;最后判断当前节点的右子树是否为空,若不为空,向右递归进行中序遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void infixOrder () { if (this .root != null ) { this .root.infixOrder(); } else { System.out.println("二叉树为空,无法遍历!" ); } } public void infixOrder () { if (this .getLeft() != null ) { this .getLeft().infixOrder(); } System.out.println(this ); if (this .getRight() != null ) { this .getRight().infixOrder(); } }
3、后序遍历 先判断当前节点左子树是否为空,若不为空,向左递归进行后序遍历;然后判断当前节点的右子树是否为空,若不为空,向右递归进行后序遍历。最后输出当前节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 public void postOrder () { if (this .root != null ) { this .root.postOrder(); } else { System.out.println("二叉树为空,无法遍历!" ); } } public void postOrder () { if (this .getLeft() != null ) { this .getLeft().postOrder(); } if (this .getRight() != null ) { this .getRight().postOrder(); } System.out.println(this ); }
3.2、非递归实现 我们需要使用到栈 这一数据结构来解决问题
1、前序遍历 如果当前节点不为空,先输出当前节点信息,然后将该节点压入栈,并将指针移动到当前节点的左子节点,此时如果该左子树为空,就退出循环,此时如果栈不为空,就弹出栈顶数据,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public void preOrder (Node node) { Stack<Node> nodeStack = new Stack<>(); while (node != null || !nodeStack.empty()) { while (node != null ) { System.out.println(node); nodeStack.push(node); node = node.getLeft(); } if (!nodeStack.empty()) { node = nodeStack.pop(); node = node.getRight(); } } }
2、中序遍历 如果当前节点不为空,将当前节点压入栈中,然后将指针指向当前节点左子树,直到左子树为空,此时栈不为空,将栈顶元素弹出并输出后,将指针移动到当前结点右子树,循环,直到栈空或者当前节点为空。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 public void midOrder (Node node) { Stack<Node> nodeStack = new Stack<>(); while (node != null || !nodeStack.empty()) { while (node != null ) { nodeStack.push(node); node = node.getLeft(); } if (!nodeStack.empty()) { node = nodeStack.pop(); System.out.println(node); node = node.getRight(); } } }
3、后序遍历 需要利用到一个辅助栈用于输出结果,由于栈具有先进后出的特点,而后序遍历的顺序是左右根,所以压入栈顺序为根、右、左。最后使用辅助栈输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public void postOrder (Node node) { if (node == null ) { System.out.println("要遍历的二叉树为空!" ); return ; } Stack<Node> stack = new Stack<>(); Stack<Node> assistStack = new Stack<>(); while (node != null || !stack.isEmpty()) { while (node != null ) { stack.push(node); assistStack.push(node); node = node.getRight(); } if (!stack.isEmpty()) { node = stack.pop(); node = node.getLeft(); } } while (!assistStack.isEmpty()) { System.out.println(assistStack.pop()); } }
四、二叉排序树节点的删除 二叉排序树中的节点可以分为以下三种:
我们需要判断待删除节点为什么类型,然后根据节点类型进行删除操作。
4.1、编写用于搜索待删除节点和待删除节点父节点的方法 1、搜索待删除节点的方法 搜索待删除节点,首先判断当前二叉排序树是否为空,若为空,直接返回,否则调用当前二叉排序树根节点的search方法
如果当前传入的数据data的值刚好等于当前节点的data值,那么当前节点就是待删除节点,直接返回即可
如果当前传入的数据data的值小于当前节点的值且当前节点的左子树为空,证明当前二叉排序树中没有要删除的节点;如果当前传入数据data值小于当前节点值且当前节点左子树不为空,那么调用当前节点左子树的search方法,向左递归查询。
同理,如果当前传入的数据data值大于当前节点值且当前节点右子树为空,证明当前二叉排序树没有要删除节点,此刻只能返回null;如果当前传入数据data值大于当前节点且当前节点右子树不为空,那么调用当前右子树的search方法,向右递归查询。
代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public Node search (int data) { if (data == this .data) { return this ; } else if (data < this .data) { if (this .left == null ) { return null ; } return this .left.search(data); } else { if (this .right == null ) { return null ; } return this .right.search(data); } }
2、搜索待删除节点父节点的方法 搜索待删除节点的父节点的方法,同理先判断当前二叉排序树的根节点是否为空,若为空,返回null,否则调用当前二叉排序树的根节点的搜索待删除节点父节点(searchParent)的方法。
如果当前节点的左子树不为空且当前节点左子树的data值等于用户传入的要检索的data值或者当前节点右子树不为空且当前节点右子树的data值等于用户传入的要检索的data值,那么证明当前节点就是待检索节点,返回当前节点。
如果传入的data值小于当前节点值且当前左子树不为空,那么调用当前左子节点的searchParent的方法。
同理,如果传入data值大于等于当前节点的data值且当前节点右子树不为空,那么调用当前节点右子节点的searchParent方法。
如果程序走到此处,证明没有找到待删除数据的父节点,此时返回null。
代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public Node searchParent (int data) { if ((this .left != null && this .left.data == data) || (this .right != null && this .right.data == data)) { return this ; } else { if (data < this .data && this .left != null ) { return this .left.searchParent(data); } else if (data >= this .data && this .right != null ) { return this .right.searchParent(data); } else { return null ; } } }
4.2、删除叶子节点 对于叶子节点,我们需要先找到待删除节点target和待删除节点的父节点parent,然后判断待删除叶子节点是其父节点的左子树还是右子树,如果为左子树,那么令parent.left = null,否则让parent.right = null。
二叉排序树中判断待删除节点是否为叶子节点的静态方法与Node类中判断传入节点为当前左子树/右子树的方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static boolean isLeaf (Node node) { return node.left == null && node.right == null ; } public boolean isLeft (Node target) { return this .left != null && this .left.data == target.data; } public boolean isRight (Node target) { return this .right != null && this .right.data == target.data; }
4.3、删除有一棵子树的节点 对于有一棵子树的节点的删除,我们需要找到待删除节点和待删除节点的父节点,然后判断两个条件:1(待删除节点是其父节点的左子树还是右子树)、2(待删除节点有左子树还是右子树)
如果待删除节点有左子树且为其父节点的左子树:此时让待删除节点的父节点的左子树等于待删除节点的左子树,即parent.left = target.left。
如果待删除节点有左子树且为其父节点的右子树:此时根据二叉排序树的性质,待删除节点的左子树的数据要全部大于(等于)其父节点的数据,所以令待删除节点父节点的右子树等于待删除节点的左子树,即parent.right = target.left。
如果待删除节点有右子树且为其父节点的左子树:此时让parent.left = target.right
如果待删除节点有右子树且为其父节点的右子树,此时让parent.right = target.right
Node类中判断传入节点是否为当前节点左/右子树的方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public boolean isLeft (Node target) { return this .left != null && this .left.data == target.data; } public boolean isRight (Node target) { return this .right != null && this .right.data == target.data; }
4.4、删除有两棵树的节点 对于有两棵子树的节点的删除:需要先取到待删除节点的右子树的最小节点的值,然后将数值最小的节点删除,最后将前面取到的最小节点的值赋值给待删除节点。
获取待删除节点右子树中最小节点的值并删除最小节点的方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public int delTreeMin (Node node) { Node target = node; while (target.left != null ) { target = target.left; } delNode(target.data); return target.data; }
1 2 3 4 5 6 7 8 public static boolean hasTwoSon (Node node) { return node.left != null && node.right != null ; }
4.5、二叉排序树中根据节点数据删除节点的方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 public void delNode (int data) { if (root == null ) { return ; } else { Node target = search(data); if (target == null ) { return ; } if (root.left == null && root.right == null ) { root = null ; return ; } Node parent = searchParent(data); if (isLeaf(target)) { if (parent.isLeft(target)) { parent.left = null ; } else if (parent.isRight(target)) { parent.right = null ; } } else if (hasTwoSon(target)) { int minData = delTreeMin(target.right); target.data = minData; } else { if (target.left != null ) { if (parent.isLeft(target)) { parent.left = target.left; } else { parent.right = target.left; } } else { if (parent.isLeft(target)) { parent.left = target.right; } else { parent.right = target.right; } } } } }
五、使用递归获取二叉树深度 1 2 3 4 5 6 7 8 9 10 public static int getTreeDepth (Node root) { return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right))); }
六、测试 6.1、测试二叉排序树的生成和插入 1 2 3 4 5 6 7 8 9 Tree tree = new Tree(null ); int [] arr = {7 ,8 ,19 ,-1 ,26 ,100 ,777 ,-1012 ,222 ,18 };for (int i = 0 ; i < arr.length; i++) { int data = arr[i]; Node node = new Node(data); tree.addNode(node); } System.out.println("tree:" ); Tree.show(tree.root);
结果
6.2、测试二叉排序树的删除 1、删除叶子节点 1 2 3 4 5 System.out.println("---------------------------------删除叶子节点-1012,删除前:" ); Tree.show(tree.root); tree.delNode(-1012 ); System.out.println("---------------------------------删除叶子节点-1012,删除后:" ); Tree.show(tree.root);
删除前:
删除后:
2、删除有一棵子树的节点 1 2 3 4 5 System.out.println("---------------------------------删除有一棵树的节点-1,删除前:" ); Tree.show(tree.root); tree.delNode(-1 ); System.out.println("---------------------------------删除有一棵树的节点-1,删除后:" ); Tree.show(tree.root);
删除前:
删除后:
3、删除有两棵子树的节点 1 2 3 4 5 System.out.println("---------------------------------删除有两棵子树的节点7,删除前:" ); Tree.show(tree.root); tree.delNode(7 ); System.out.println("---------------------------------删除有两棵子树的节点7,删除后:" ); Tree.show(tree.root);
删除前:
删除后: