在二分搜索树中查找下一个节点

一个，问题描述

给出二叉搜索树和一个节点的值. 查找节点的下一个节点. 如果节点最大，则返回null

对于二进制搜索树，将按顺序遍历它. 节点的下一个节点是: 中阶遍历输出的下一个节点.

第二，问题分析

假设您需要找到该节点的下一个节点，则需要考虑以下三种情况:

①节点有合适的孩子

下一个节点是子树中最左边的节点，该子树以该节点节点的右子节点为根. 如下所示: node = 8，它的下一个节点是12.

②当节点节点没有右子节点时，该节点节点为其父节点的左子节点. 如下所示，节点8的下一个节点是节点12

③当节点节点没有右子节点时，该节点节点为其父节点的右子节点. 如下图所示二叉排序树 查找，节点14的下一个节点是节点16

如何在二叉树中找到节点？

您可以使用先遍历的想法. 但是我们必须注意递归的实现-第11行的返回目标非常有意义.

在每个递归调用中二叉排序树 查找，每个方法都有其自己的目标局部变量. 如果在此方法中找到目标节点，如果没有返回，则在递归返回时将丢失“找到的目标节点”，也就是说，上一层的find方法中的目标变量仍为null（尽管目标节点已在下一级别的递归中找到

通过第11行的return语句，如果在某一层上未找到目标节点，则将继续递归调用它. 如果找到，则返回时，上一层的find方法的目标变量不是null. 它将为null，以便最终的find方法结束时，它返回找到的目标节点.

 1     //采用先序遍历查找值为ele的结点
 2     private BinaryNode find(BinaryNode root, int ele){
 3         if(root == null)
 4             return null;
 5         if(root.ele == ele)
 6             return root;
 7         BinaryNode target = null;
 8         target = find(root.left, ele);
 9         if(target == null)//如果左子树中没有值为ele的结点,if成立,在右子树中查找
10             target = find(root.right, ele);
11         return target;
12     }

①第3-4行用于查找叶节点

②第5-6行是成功找到指定节点的情况. （①②类似于遍历中的访问根节点）

③第8行表示首先搜索左子树（类似于先遍历左子树）

④如果第9-10行指示在左子树中找不到该节点，则搜索右子树⑤第11行，并返回到搜索到的节点. 如果返回null，则表示未找到

三，代码分析

①节点有合适的孩子

1 if(node.right != null)
2 {
3     BinaryNode current = node.right;
4     while(current.left != null)
5     {
6     current = current.left;
7     }
8     nextNode = current;
9  }

第3行，首先找到该节点的右子节点.

第4行while循环，找到最左边的节点

②当节点没有右子节点时，该节点是其父节点的左子节点

1 else if(node.parent != null){//node结点 是 parent 的孩子
2     if(node.parent.left != null && node.parent.left.equals(node))// node 是 parent 的左孩子
3         nextNode = node.parent;

如果节点节点是其父节点的左子节点，则下一个节点是该节点节点的父节点.

③当节点节点没有右子节点时，该节点节点为其父节点的右子节点

1 else{//node 是 parent的右孩子
2     BinaryNode current = node.parent;
3     //一直往着右孩子的父结点指针向上走
4     while(current.parent.right != null && current.parent.right.equals(current))
5     {
6         current = current.parent;
7     }
8     nextNode = current.parent;
9 }

请注意第4行while循环中的第一个条件: current.parent.right！ =空

为什么不判断当前父母？ =空？因为它是在前面的if语句中判断出来的（if（node.parent！= Null）

四个完整的代码实现

public class BSTNextNode {
    private class BinaryNode{
        int ele;
        BinaryNode left;
        BinaryNode right;
        BinaryNode parent;
        int hash;//cache hashCode
        
        public BinaryNode(int ele) {
            this.ele = ele;
            parent = left = right = null;
        }
        
        @Override
        public boolean equals(Object obj) {
            if(obj == null)
                return false;
            if(!(obj instanceof BinaryNode))
                return false;
            BinaryNode node = (BinaryNode)obj;
            return node.ele == this.ele;
        }
        
        @Override
        public int hashCode() {// 参考《effective java》中覆盖equals方法
            int result = hash;
            if(result == 0){
                result = 17;
                result = result*31 + ele;
                hash = result;
            }
            return result;
        }
        
        @Override
        public String toString() {
            return ele + " "; 
        }
    }
    
    private BinaryNode root;
    
    public void buildTree(int[] eles){
        if(eles == null || eles.length == 0)
            return;
        
        for (int ele : eles) {
            insert(ele);
        }
    }
    private void insert(int ele){
        root = insert(root, ele);
        root.parent = null;
    }
    private BinaryNode insert(BinaryNode root, int ele){
        if(root == null)
            return new BinaryNode(ele);
        if(root.ele > ele){
            root.left = insert(root.left, ele);
            root.left.parent = root;
        }else{
            root.right = insert(root.right, ele);
            root.right.parent = root;
        }
        return root;
    }
    
    //寻找值为ele的那个结点的 下一个结点
    public BinaryNode nextNode(int ele){
        BinaryNode node = find(ele);//找到Node值为ele的结点在BST中的位置
        if(node == null)
            throw new IllegalArgumentException(ele + " not in tree");
        BinaryNode nextNode = null;
        if(node.right != null)
        {
            BinaryNode current = node.right;
            while(current.left != null)
            {
                current = current.left;
            }
            nextNode = current;
        }else if(node.parent != null){//node结点 是 parent 的孩子
            if(node.parent.left != null && node.parent.left.equals(node))// node 是 parent 的左孩子
                nextNode = node.parent;
            else{//node 是 parent的右孩子
                BinaryNode current = node.parent;
                //一直往着右孩子的父结点指针向上走
                while(current.parent.right != null && current.parent.right.equals(current))
                {
                    current = current.parent;
                }
                nextNode = current.parent;
            }
        }else{//node 没有父结点.那它就是BST中的最大的结点---此时它的下一个结点视为null
//            nextNode = node;
            ;
        }
        return nextNode;
    }
    
    //查找二叉树中值为ele的结点,并返回该结点
    private BinaryNode find(int ele){
        if(root == null)
            throw new IllegalStateException("bst is null");
        return find(root, ele);
    }
    
    //采用先序遍历查找值为ele的结点
    private BinaryNode find(BinaryNode root, int ele){
        if(root == null)
            return null;
        if(root.ele == ele)
            return root;
        BinaryNode target = null;
        target = find(root.left, ele);
        if(target == null)//如果左子树中没有值为ele的结点,if成立,在右子树中查找
            target = find(root.right, ele);
        return target;
    }
    
    
    //hapjin test
    public static void main(String[] args) {
//        int[] eles = {20,10,30,15,18,26,22,8,40};
        int ele = 20;
        int[] eles = {20,10,15};
        BSTNextNode bstTree = new BSTNextNode();
        bstTree.buildTree(eles);//构造一棵二叉树查找树
        BinaryNode next = bstTree.nextNode(ele);//查找值为ele结点的下一个结点
        System.out.println(next);
    }
}

查看代码

五本参考资料

二叉树的构造

二叉搜索树的递归实现和递归分析

原文:

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