java实现二叉树查找树

1、二叉树(binary)是一种特殊的树。二叉树的每个节点最多只能有2个子节点：二叉树由于二叉树的子节点数目确定，所以可以直接采用上图方式在内存中实现。每个节点有一个左子节点(left children)和右子节点(right children)。左子节点是左子树的根节点，右子节点是右子树的根节点。 如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：每个节点都不比它左子树的任意元素小，而且不比它的右子树的任意元素大。(如果我们假设树中没有重复的元素，那么上述要求可以写成：每个节点比它左子树的任意节点大，而

2、且比它右子树的任意节点小)二叉搜索树，注意树中元素的大小二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候，我们可以将x和根节点比较:1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)2. 如果x小于根节点，那么搜索左子树3. 如果x大于根节点，那么搜索右子树二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)。 下面是用java实现的二叉搜索树，并有搜索，插入，删除，寻找最大最小节点的操作。删除节点相对比较复杂。删除节点后，有时需要进行一定的调整，以恢复二叉搜索树的性质(每个节点都不比它左子树的任意元素小，而且不比它的右

3、子树的任意元素大)。· 叶节点可以直接删除。· 删除非叶节点时，比如下图中的节点8，我们可以删除左子树中最大的元素(或者右树中最大的元素)，用删除的节点来补充元素8产生的空缺。但该元素可能也不是叶节点，所以它所产生的空缺需要其他元素补充 直到最后删除一个叶节点。上述过程可以递归实现。删除节点删除节点后的二叉搜索树 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768

4、697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781

5、791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782

6、79280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366import java.util.ArrayList;import jav

7、a.util.List; public class BinarySearchTree      / 树的根结点    private TreeNode root = null;     / 遍历结点列表    private List<TreeNode> nodelist = new ArrayList<TreeNode

8、>();     private class TreeNode          private int key;        private TreeNode leftChild;        private TreeNode

9、rightChild;        private TreeNode parent;         public TreeNode(int key, TreeNode leftChild, TreeNode rightChild,              

10、;  TreeNode parent)             this.key = key;            this.leftChild = leftChild;            this.rightCh

11、ild = rightChild;            this.parent = parent;                 public int getKey()          

12、0;  return key;                 public String toString()             String leftkey = (leftChild = null ? ""&#

13、160;: String                    .valueOf(leftChild.key);            String rightkey = (rightChild = null ? "" 

14、: String                    .valueOf(rightChild.key);            return "(" + leftkey + " , " + key

15、+ " , " + rightkey + ")"                  /*     * isEmpty: 判断二叉查找树是否为空；若为空，返回 true ，否则返回 false .     *   

16、0; */    public boolean isEmpty()         if (root = null)             return true;         else  &#

17、160;          return false;                 /*     * TreeEmpty: 对于某些二叉查找树操作(比如删除关键字)来说，若树为空，则抛出异常。     */ 

18、;   public void TreeEmpty() throws Exception         if (isEmpty()             throw new Exception("树为空!");       &

19、#160;         /*     * search: 在二叉查找树中查询给定关键字     *     * param key     *            给定关键字 

20、0;   * return 匹配给定关键字的树结点     */    public TreeNode search(int key)         TreeNode pNode = root;        while (pNode != null &&am

21、p; pNode.key != key)             if (key < pNode.key)                 pNode = pNode.leftChild;         

22、0;   else                 pNode = pNode.rightChild;                         

23、;   return pNode;         /*     * minElemNode: 获取二叉查找树中的最小关键字结点     *     * return 二叉查找树的最小关键字结点     * throws Exception  

24、60;  *             若树为空，则抛出异常     */    public TreeNode minElemNode(TreeNode node) throws Exception         if (node = null)  

25、;           throw new Exception("树为空！");                TreeNode pNode = node;        while (pNode.l

26、eftChild != null)             pNode = pNode.leftChild;                return pNode;         /*  

27、;   * maxElemNode: 获取二叉查找树中的最大关键字结点     *     * return 二叉查找树的最大关键字结点     * throws Exception     *             若树为空，则抛出异常 

28、;    */    public TreeNode maxElemNode(TreeNode node) throws Exception         if (node = null)             throw new Exception("树

29、为空！");                TreeNode pNode = node;        while (pNode.rightChild != null)             pNode =

30、pNode.rightChild;                return pNode;         /*     * successor: 获取给定结点在中序遍历顺序下的后继结点     *   &#

31、160; * param node     *            给定树中的结点     * return 若该结点存在中序遍历顺序下的后继结点，则返回其后继结点；否则返回 null     * throws Exception     */   

32、; public TreeNode successor(TreeNode node) throws Exception         if (node = null)             return null;           

33、      / 若该结点的右子树不为空，则其后继结点就是右子树中的最小关键字结点        if (node.rightChild != null)             return minElemNode(node.rightChild);     

34、           / 若该结点右子树为空        TreeNode parentNode = node.parent;        while (parentNode != null && node = parentNode.rightChild)   

35、;          node = parentNode;            parentNode = parentNode.parent;                return parentNode

36、;         /*     * precessor: 获取给定结点在中序遍历顺序下的前趋结点     *     * param node     *            给定树中的结点

37、60;    * return 若该结点存在中序遍历顺序下的前趋结点，则返回其前趋结点；否则返回 null     * throws Exception     */    public TreeNode precessor(TreeNode node) throws Exception         if (nod

38、e = null)             return null;                 / 若该结点的左子树不为空，则其前趋结点就是左子树中的最大关键字结点        if (nod

39、e.leftChild != null)             return maxElemNode(node.leftChild);                / 若该结点左子树为空        TreeNod

40、e parentNode = node.parent;        while (parentNode != null && node = parentNode.leftChild)             node = parentNode;         

41、   parentNode = parentNode.parent;                return parentNode;         /*     * insert: 将给定关键字插入到二叉查找树中   

42、60; *     * param key     *            给定关键字     */    public void insert(int key)         

43、;TreeNode parentNode = null;        TreeNode newNode = new TreeNode(key, null, null, null);        TreeNode pNode = root;        if (root = 

44、null)             root = newNode;            return;                while (pNode != null)

45、            parentNode = pNode;            if (key < pNode.key)                 pNode = pNod

46、e.leftChild;             else if (key > pNode.key)                 pNode = pNode.rightChild;        &#

47、160;    else                 / 树中已存在匹配给定关键字的结点，则什么都不做直接返回                return;      

48、;                      if (key < parentNode.key)             parentNode.leftChild = newNode;     

49、       newNode.parent = parentNode;         else             parentNode.rightChild = newNode;          &#

50、160; newNode.parent = parentNode;                  /*     * insert: 从二叉查找树中删除匹配给定关键字相应的树结点     *     * param key   

51、  *            给定关键字     */    public void delete(int key) throws Exception         TreeNode pNode = search(key);   

52、0;    if (pNode = null)             throw new Exception("树中不存在要删除的关键字!");                delete(pNode); &

53、#160;       /*     * delete: 从二叉查找树中删除给定的结点.     *     * param pNode     *            要删除的结点   

54、  *     *            前置条件： 给定结点在二叉查找树中已经存在     * throws Exception     */    private void delete(TreeNode pNode) throws Exception &

55、#160;       if (pNode = null)             return;                if (pNode.leftChild = null &&am

56、p; pNode.rightChild = null)  / 该结点既无左孩子结点，也无右孩子结点            TreeNode parentNode = pNode.parent;            if (pNode = parentNode.leftChild)     

57、;            parentNode.leftChild = null;             else                 parentNode

58、.rightChild = null;                        return;                if (pNode.leftChild =

59、60;null && pNode.rightChild != null)  / 该结点左孩子结点为空，右孩子结点非空            TreeNode parentNode = pNode.parent;            if (pNode = parentNode.leftChild) &

60、#160;               parentNode.leftChild = pNode.rightChild;                pNode.rightChild.parent = parentNode;     &#

61、160;       else                 parentNode.rightChild = pNode.rightChild;                pNode.right

62、Child.parent = parentNode;                        return;                if (pNode.leftChild !=

63、 null && pNode.rightChild = null)  / 该结点左孩子结点非空，右孩子结点为空            TreeNode parentNode = pNode.parent;            if (pNode = parentNode.leftChild)

64、                 parentNode.leftChild = pNode.leftChild;                pNode.rightChild.parent = parentNode;     &

65、#160;       else                 parentNode.rightChild = pNode.leftChild;                pNode.right

66、Child.parent = parentNode;                        return;                / 该结点左右孩子结点均非空，则删除该结点的后继结点，

67、并用该后继结点取代该结点        TreeNode successorNode = successor(pNode);        delete(successorNode);        pNode.key = successorNode.key;        &#

68、160;/*     * inOrderTraverseList: 获得二叉查找树的中序遍历结点列表     *     * return 二叉查找树的中序遍历结点列表     */    public List<TreeNode> inOrderTraverseList()      

69、   if (nodelist != null)             nodelist.clear();                inOrderTraverse(root);       &

70、#160;return nodelist;         /*     * inOrderTraverse: 对给定二叉查找树进行中序遍历     *     * param root     *        

71、60;   给定二叉查找树的根结点     */    private void inOrderTraverse(TreeNode root)         if (root != null)             inOrderTraverse

72、(root.leftChild);            nodelist.add(root);            inOrderTraverse(root.rightChild);              

73、60;  /*     * toStringOfOrderList: 获取二叉查找树中关键字的有序列表     *     * return 二叉查找树中关键字的有序列表     */    public String toStringOfOrderList()      

74、60;  StringBuilder sbBuilder = new StringBuilder(" ");        for (TreeNode p : inOrderTraverseList()             sbBuilder.append(p.key);    

75、60;       sbBuilder.append(" ");                sbBuilder.append("");        return sbBuilder.toString();  

76、60;      /*     * 获取该二叉查找树的字符串表示     */    public String toString()         StringBuilder sbBuilder = new StringBuilder(" "); 

77、0;      for (TreeNode p : inOrderTraverseList()             sbBuilder.append(p);            sbBuilder.append(" ");   

78、60;            sbBuilder.append("");        return sbBuilder.toString();         public TreeNode getRoot()     

79、0;   return root;         public static void testNode(BinarySearchTree bst, TreeNode pNode)            throws Exception       

80、0; System.out.println("本结点: " + pNode);        System.out.println("前趋结点: " + bst.precessor(pNode);        System.out.println("后继结点: " + bst.successor(pNode);  &

81、#160;      public static void testTraverse(BinarySearchTree bst)         System.out.println("二叉树遍历：" + bst);        System.out.println("二叉查找树转换为有序列表: " + bst.toSt