Android版本数据结构和算法（八）: 二进制排序树

Java

在前两篇文章中，我们学习了树的一些基本概念和常见操作。在本文中，我们将学习一种特殊形式的二叉树:BinarySortTree，也称为BinarySearchTree。树），也称为二进制搜索树。二进制排序树是具有以下属性的空树或二进制树:也就是说，二进制排序树中的左子树节点值小于根节点值，右子树节点值大于跟随者节点值，左右子树也满足上述约定如下所示，它是一个二进制排序树:从二叉树的定义中可以知道二叉排序树查找算法，通过以中间顺序遍历二叉树，我们可以按降序排列二叉树中的所有元素。

如上所示，顺序遍历的结果是:35、40、42、45、50、67在这里，我们通过Java代码在二进制排序树中实现了几种核心方法我们首先来看一下每个节点类的定义:1classTreeNode{2privateintdata;3privateTreeNodeleftChild;4privateTreeNoderigHTChild;5privateTreeNodeparent;67publicTreeNode(intdata){8this。

data=data;9this。leftChild=null;10this。rigHTChild=null;11this。parent=null;12}13}这很简单。每个节点记录有关其自身，其子代及其父代的信息。

HTC

创建二进制排序树是在其中添加元素。总体思路是:源代码:1publicTreeNodeput(intdata){2TreeNodenode=root;3TreeNodeparent=null;4//判断二叉排序树根结点是否存在，不存在则创建5if(root==null){6root=newTreeNode(data);7returnroot;8}9//查找其父类10while(node!=null){11parent=node;//记录其父亲节点12if(data>node。

data){13node=node。rigHTChild;14}elseif(data<node。data){15node=node。leftChild;16}else{17//已经存在则直接返回18returnnode;19}20}21//创建新节点并插入原有树中22node=newTreeNode(data);23if(data<parent。

data){24parent。leftChild=node;25}else{26parent。rigHTChild=node;27}28node。parent=parent;29returnnode;30}在二元排序树中搜索相对简单，想法是:源代码:1publicTreeNodesearchNode(intdata){2TreeNodenode=root;3if(node==null){4returnnull;5}else{6while(node!=null&&data!=node。

data){7if(data<node。data){8node=node。leftChild;9}else{10node=node。rigHTChild;11}12}13}14returnnode;15}二进制排序树的删除操作分为4种情况:源代码:在这里，我们选择右子树的最小节点1publicvoiddeleteNode(intdata){2TreeNodenode=searchNode(data);3if(node==null){4thrownewRuntimeException("未找到要删除的节点");5}else{6delete(node);7}8}910privatevoiddelete(TreeNodenode){11if(node==null){12thrownewRuntimeException("未找到要删除的节点");13}else{14TreeNodeparent=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!=null26&&node。

rigHTChild==null){27if(parent。leftChild==node){28parent。leftChild=node。leftChild;29}else{30parent。rigHTChild=node。

leftChild;31}32return;33}34//删除的节点有右无左35if(node。leftChild==null36&&node。rigHTChild!=null){37if(parent。

leftChild==node){38parent。leftChild=node。rigHTChild;39}else{40parent。rigHTChild=node。rigHTChild;41}42return;43}44//删除的结点左右都有45TreeNoderightMinNode=getRightMinNode(node。

rigHTChild);46delete(rightMinNode);47node。data=rightMinNode。data;48}49}5051//获取右子树最小的结点52privateTreeNodegetRightMinNode(TreeNodenode){53TreeNodeminNode=node;54while(minNode!=null&&minNode。

leftChild!=null){55minNode=minNode。leftChild;56}57System。out。println("minNode"+minNode。data);58returnminNode;59}测试代码:1SearchBinaryTreess=newSearchBinaryTree();2int[]array={77,88,34,55,66,2,34,67,78};3for(intdata:array){4ss。

put(data);5}6ss。midIter(ss。getRoot());7System。out。println();8SearchBinaryTree。TreeNodenode=ss。searchNode(66);9System。

out。println("findnode:"+node。getData());10ss。deleteNode(66);11SearchBinaryTree。TreeNodednode=ss。searchNode(66);12if(dnode!=null){13System。

out。println("findnode:"+node。getData());14}else{15System。out。println("notfindnode");16}17ss。midIter(ss。getRoot());打印信息如下:12345566677778882findnode:663notfindnode42345567777888在最佳情况下，二元排序树的搜索性能最佳，这与二元搜索方法相近。

但是在某些情况下，构造的二进制排序树类似于链表，其搜索性能为O（n）二叉排序树查找算法，如下所示:绝对不是我们想要建造这样的树。您需要调整此树以达到平衡的效果。在这里，您需要一个二进制平衡树（AVL树）。AVL树将在后续章节中介绍。树有这个问题。

本文主要介绍二进制平衡树和Java代码实现其核心的核心方法。希望您能理解它与普通二叉树之间的区别以及存在的问题。好吧，这部电影到此结束。

二进制排序树，也称为二叉排序树或二叉查找树（Binary Search Tree, BST），是一种特殊的二叉树。它满足以下性质：每个节点的左子树中的所有节点的值都小于该节点的值，而每个节点的右子树中的所有节点的值都大于该节点的值。这种性质使得二叉排序树在查找、插入和删除操作上都非常高效。

在Android开发中，二叉排序树可以用于实现高效的搜索功能。例如，在实现一个需要频繁查找、插入和删除的集合时，使用二叉排序树可以提高程序的性能。此外，二叉排序树还可以用于实现一些其他的数据结构，如平衡二叉排序树（Balanced Binary Search Tree），包括AVL树和红黑树，这些树在插入和删除操作后能够自动保持平衡，从而保证树的高度不会过高，操作的时间复杂度能够保持在O(log n)级别。

需要注意的是，二叉排序树的效率在很大程度上取决于树的平衡性。如果插入的元素是有序的，那么二叉排序树可能会退化成一个链表，使得查找、插入和删除操作的时间复杂度达到O(n)。因此，在实际应用中，通常会使用自平衡的二叉排序树来避免这种情况。