二叉树搜索树中顺序遍历的前驱节点和后继节点

前身节点

前任节点的值小于该节点的值，这是该节点的左子树中的最大值

后续节点

后继节点的值大于该节点的值，这是该节点的右子树中的最小值

因为二叉搜索树遍历的结果是一棵树的节点上的值的升序，所以一个数字的前任节点的值是一个小于它的数字，并且后继节点小于它的较大节点

查找前驱节点有以下情况:

（1）此节点有一个左子树，因此该节点的前任节点是其左子树中最大的子树. 例如，10有一个左孩子，而其前任是左孩子中最大的孩子，即8.

（2）节点没有左子树，因此有两种情况: 1.节点是其父节点的右子节点，然后其前任节点是其父节点；例如17的前身是16

2. 该节点是其父节点的左子节点，因此它必须搜索其祖先，直到发现其祖先是左子节点. 如果找不到，则表示该节点没有前驱节点. 例如，8是左孩子，所以它的前任不是父亲，所以他必须抬头，

它的父亲是他爷爷的正直孩子，所以8的前任应该是他的爷爷7.

查找后继节点具有以下情况:

（1）该节点具有一个右子树，则该节点的后继节点是其右子树中最小的. 例如，10具有一个正确的子树，其后继是最小的正确的子树.

（2）此节点没有右子树，因此也必须在其祖先中找到其后继节点，并且有两种情况: 1.该节点是其父节点的左子树二叉排序树中序遍历，然后是其后继节点是他的父亲； 2.该节点是父节点的左子树，

然后查找，直到您发现该节点的祖先是左子节点. 如果找不到它，则该节点没有后继. 例如二叉排序树中序遍历，图中的17是父亲的正确孩子. 向上看，发现父亲也是其祖父的正直子女，并且其祖父没有父母，因此该节点也没有继任者.

具体的Java实现代码如下:

 1 /**
 2      * 找给定节点的后继节点
 3      * @param  node 给定树中的节点
 4      * @return  返回该节点存在中序遍历顺序下的后继节点，有则返回后继节点，无则返回null
 5      *
 6      */
 7     public TreeNode successor(TreeNode node){
 8         if(node==null){ return null;}
 9         //若该节点的右子树不为空，则后继节点就是右子树中的最小关键字节点
10         if(node.rightChild!=null){
11             try {
12                 return  minElemNode(node.rightChild);
13             } catch (Exception e) {
14                 e.printStackTrace();
15             }
16         }
17         //若该节点右子树为空
18         TreeNode parentNode=node.parent;
19         while(parentNode !=null && node==parentNode.rightChild){
20             node=parentNode;
21             parentNode=parentNode.parent;
22         }
23         return parentNode;
24     }
25 
26     /**
27      *  找出给定节点的后继节点
28      * @param node 给定节点
29      * @return  后继节点
30      */
31     public  TreeNode precessor(TreeNode node) throws Exception {
32         if(node==null){ return null;}
33         //若该节点有左子树，则前驱节点就是左子树中最大的那个
34         if(node.leftChild!=null){return maxElemNode(node.leftChild);}
35         //若该节点没有左子树
36         TreeNode parentNode=node.parent;
37         if(parentNode!=null&&node==parentNode.leftChild){
38             node=parentNode;
39             parentNode=parentNode.parent;
40         }
41         return  parentNode;
42     }

原始来源:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-194959-1.html