Android版数据结构与算法（二叉排序树）

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述Android版数据结构与算法：二叉排序树相关的知识，希望能为你提供帮助。
本文目录

文章图片

前两篇文章我们学习了一些树的基本概念以及常用操作，本篇我们了解一下二叉树的一种特殊形式：二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
一、二叉排序树定义
二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：

若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值
它的左，右子树也分别为二叉排序树

也就是说二叉排序树中左子树结点值均小于根结点值，右子树节点值均大于跟节点值，左右子树同样满足上述约定。
如下图，即为一颗二叉排序树：

文章图片

由二叉树定义知道，我们通过中序遍历二叉树就可以按照从小到大顺序排列二叉树中所有元素。
如上图中序遍历结果为：35, 40, 42, 45, 50, 67
二、java代码实现二叉排序树核心方法
下面我们通过java代码实现二叉排序树中的几个核心方法
我们先看下每个结点类定义如下：

1class TreeNode{ 2private int data; 3private TreeNode leftChild; 4private TreeNode rightChild; 5private TreeNode parent; 6 7public TreeNode(int data) { 8this.data = https://www.songbingjia.com/android/data; 9this.leftChild = null; 10this.rightChild = null; 11this.parent = null; 12} 13}

很简单，每个结点记录自己以及左右孩子，父类的信息。
二叉排序树的创建(增加元素方法)【Android版数据结构与算法（二叉排序树）】创建一颗二叉排序树就是不断往里面添加元素。
整体思路为：

判断整棵树根结点是否创建过，如果没有创建那么第一个加入进来的元素指定为根结点，方法返回。
如果二叉排序树已经创建过，那么再往里面加入元素需要先找出其父节点，然后将要插入的元素挂载到父节点下即可。
经过上面过程找出其父结点，这里只需创建节点，挂载到父节点下即可，指定为父节点左孩子还是右孩子只需比较一下元素大小即可。

源码：

1public TreeNode put(int data){ 2TreeNode node = root; 3TreeNode parent = null; 4//判断二叉排序树根结点是否存在，不存在则创建 5if (root == null){ 6root = new TreeNode(data); 7return root; 8} 9//查找其父类 10while (node != null){ 11parent = node; //记录其父亲节点 12if (data > node.data){ 13node = node.rightChild; 14}else if (data < node.data){ 15node = node.leftChild; 16}else { 17//已经存在则直接返回 18return node; 19} 20} 21//创建新节点并插入原有树中 22node = new TreeNode(data); 23if (data < parent.data){ 24parent.leftChild = node; 25}else { 26parent.rightChild = node; 27} 28node.parent = parent; 29return node; 30}

二叉排序树的查找二叉排序树中查找比较简单，思路为：

当前结点与查找的数据比较，相等则返回
若小于当前结点则从左子树查找即可
若大于当前结点则从右子树查找即可
重复上述过程，这里就看出二分查找思想了

源码：

1public TreeNode searchNode(int data) { 2TreeNode node = root; 3if (node == null){ 4return null; 5}else { 6while (node != null & & data != node.data){ 7if (data < node.data){ 8node = node.leftChild; 9}else { 10node = node.rightChild; 11} 12} 13} 14return node; 15}

二叉排序树的删除二叉排序树的删除操作分4中情况：

若要删除的结点无左右孩子也就是叶子结点，那么直接删除即可，将其父节点左或者右孩子置null即可
若要删除的结点有左孩子无右孩子，则只需要将删除结点的左孩子与其父节点建立关系即可
若要删除的结点有右孩子无左孩子，则只需要将删除结点的右孩子与其父节点建立关系即可
若要删除的结点左右孩子均有，就需要选一个结点将其替换，这里需要保证选取的结点保证比左子树都大，右子树都小，可以选取左子树中最大的结点，或者右子树中最小的结点，并且需要将选取的结点从二叉排序树中删除。

源码：这里我们选取右子树最小的结点

1public void deleteNode(int data){ 2TreeNode node = searchNode(data); 3if (node == null){ 4throw new RuntimeException("未找到要删除的节点"); 5}else { 6delete(node); 7} 8} 9 10private void delete(TreeNode node) { 11if (node == null){ 12throw new RuntimeException("未找到要删除的节点"); 13}else { 14TreeNode parent = node.parent; 15//删除的节点无左右孩子 16if (node.leftChild == null & & node.rightChild == null){ 17if (parent.leftChild == node){ 18parent.leftChild = null; 19}else { 20parent.rightChild = null; 21} 22return; 23} 24//删除的节点有左无右 25if (node.leftChild != null 26& & node.rightChild == null){ 27if (parent.leftChild == node){ 28parent.leftChild = node.leftChild; 29}else { 30parent.rightChild = node.leftChild; 31} 32return; 33} 34//删除的节点有右无左 35if (node.leftChild == null 36& & node.rightChild != null){ 37if (parent.leftChild == node){ 38parent.leftChild = node.rightChild; 39}else { 40parent.rightChild = node.rightChild; 41} 42return; 43} 44//删除的结点左右都有 45TreeNode rightMinNode = getRightMinNode(node.rightChild); 46delete(rightMinNode); 47node.data = https://www.songbingjia.com/android/rightMinNode.data; 48} 49} 50 51//获取右子树最小的结点 52private TreeNode getRightMinNode(TreeNode node) { 53TreeNode minNode = node; 54while (minNode != null & & minNode.leftChild != null){ 55minNode = minNode.leftChild; 56} 57System.out.println("minNode" + minNode.data); 58return minNode; 59}

接下来我们测试一下测试代码：

1 SearchBinaryTree ss = new SearchBinaryTree(); 2 int[] array = {77,88,34,55,66,2,34,67,78}; 3 for (int data : array) { 4ss.put(data); 5 } 6 ss.midIter(ss.getRoot()); 7 System.out.println(); 8 SearchBinaryTree.TreeNode node = ss.searchNode(66); 9 System.out.println("find node:"+node.getData()); 10 ss.deleteNode(66); 11 SearchBinaryTree.TreeNode dnode = ss.searchNode(66); 12 if (dnode != null){ 13System.out.println("find node:"+node.getData()); 14 }else { 15System.out.println("not find node"); 16 } 17 ss.midIter(ss.getRoot());

打印信息如下：

12 34 55 66 67 77 78 88 2find node:66 3not find node 42 34 55 67 77 78 88

三、二叉排序树性能问题
二叉排序树最好的情况下其查找性能是很高的，接近二分查找法。
但是在有些情况下构建出的二叉排序树类似一个链表，其查找性能为O(n),如下图：

文章图片

构建出这样的树肯定不是我们希望的，需要调整此树达到平衡的效果，这里就需要二叉平衡树了（AVL树），关于AVL树会在后续篇章介绍，这里知道二叉平衡树有这个问题就可以了。
四、总结
本篇主要介绍了二叉平衡树以及Java代码实现其核心方法，希望你能掌握其与普通二叉树的区别，以及其存在的问题，好了，本片到此为止，希望对你有用。
声明：文章将会陆续搬迁到个人公众号，以后也会第一时间发布到个人公众号，及时获取文章内容请关注公众号

文章图片

最后附上整个类的全部源码，拷贝过去就可以用了：

1public class SearchBinaryTree { 2 3private TreeNode root; //二叉树根结点 4 5public TreeNode getRoot() { 6return root; 7} 8 9//中序遍历二叉排序树：按照从小到大排序 10public void midIter(TreeNode node){ 11if (node == null){ 12return; 13} 14midIter(node.leftChild); 15System.out.print(" "+node.data); 16midIter(node.rightChild); 17} 18 19public TreeNode put(int data){ 20TreeNode node = root; 21TreeNode parent = null; 22//判断二叉排序树根结点是否存在，不存在则创建 23if (root == null){ 24root = new TreeNode(data); 25return root; 26} 27//查找其父类 28while (node != null){ 29parent = node; //记录其父亲节点 30if (data > node.data){ 31node = node.rightChild; 32}else if (data < node.data){ 33node = node.leftChild; 34}else { 35//已经存在则直接返回 36return node; 37} 38} 39//创建新节点并插入原有树中 40node = new TreeNode(data); 41if (data < parent.data){ 42parent.leftChild = node; 43}else { 44parent.rightChild = node; 45} 46node.parent = parent; 47return node; 48} 49 50public void deleteNode(int data){ 51TreeNode node = searchNode(data); 52if (node == null){ 53throw new RuntimeException("未找到要删除的节点"); 54}else { 55delete(node); 56} 57} 58 59private void delete(TreeNode node) { 60if (node == null){ 61throw new RuntimeException("未找到要删除的节点"); 62}else { 63TreeNode parent = node.parent; 64//删除的节点无左右孩子 65if (node.leftChild == null & & node.rightChild == null){ 66if (parent.leftChild == node){ 67parent.leftChild = null; 68}else { 69parent.rightChild = null; 70} 71return; 72} 73//删除的节点有左无右 74if (node.leftChild != null 75& & node.rightChild == null){ 76if (parent.leftChild == node){ 77parent.leftChild = node.leftChild; 78}else { 79parent.rightChild = node.leftChild; 80} 81return; 82} 83//删除的节点有右无左 84if (node.leftChild == null 85& & node.rightChild != null){ 86if (parent.leftChild == node){ 87parent.leftChild = node.rightChild; 88}else { 89parent.rightChild = node.rightChild; 90} 91return; 92} 93//删除的结点左右都有 94TreeNode rightMinNode = getRightMinNode(node.rightChild); 95delete(rightMinNode); 96node.data = https://www.songbingjia.com/android/rightMinNode.data; 97} 98} 99 100private TreeNode getRightMinNode(TreeNode node) { 101TreeNode minNode = node; 102while (minNode != null & & minNode.leftChild != null){ 103minNode = minNode.leftChild; 104} 105System.out.println("minNode" + minNode.data); 106return minNode; 107} 108 109public TreeNode searchNode(int data) { 110TreeNode node = root; 111if (node == null){ 112return null; 113}else { 114while (node != null & & data != node.data){ 115if (data < node.data){ 116node = node.leftChild; 117}else { 118node = node.rightChild; 119} 120} 121} 122return node; 123} 124 125 126public class TreeNode{ 127private int data; 128private TreeNode leftChild; 129private TreeNode rightChild; 130private TreeNode parent; 131 132public TreeNode(int data) { 133this.data = https://www.songbingjia.com/android/data; 134this.leftChild = null; 135this.rightChild = null; 136this.parent = null; 137} 138 139public int getData() { 140return data; 141} 142 143public void setData(int data) { 144this.data = data; 145} 146 147public TreeNode getLeftChild() { 148return leftChild; 149} 150 151public void setLeftChild(TreeNode leftChild) { 152this.leftChild = leftChild; 153} 154 155public TreeNode getRightChild() { 156return rightChild; 157} 158 159public void setRightChild(TreeNode rightChild) { 160this.rightChild = rightChild; 161} 162 163public TreeNode getParent() { 164return parent; 165} 166 167public void setParent(TreeNode parent) { 168this.parent = parent; 169} 170} 171}