10. 二叉树的下一个节点

问题描述:

给定一棵二叉树和其中一个节点，如何找出中序遍历序列的下一个节点？书中的节点除了有两个分别执行左、右节点的指针，还有一个执向父节点的指针。

例如：给定中序遍历的序列是{d, b,h,e,i,a,f,c,g}.

二叉树：

分析:

1. 前序遍历的结果是左根右
2. 如果给定的这个节点，没有右子树，那么它的下一个节点，必定要追溯到它的父节点去找
3. 如果给定的这个节点，有右子树，那么它的下一个节点一定是，右子树的一个节点，且肯定是右子树中的最左子节点
4. 我们循环2， 3， 步骤，只需要改变给定节点，就能找到我们所需要的结果
5. 举个例子，我们拿 b 节点做例子 假设为node
   • 它有右子树，那么它的下一个节点一定在它的右子树里面
   • 那么就有node = node.right,现在node就是 e 节点了
   • e节点有左子节点 h ，且h没有子节点，那么b的下一个节点就是h了

代码:

/**
 * Class day10 ...
 *
 * @author LiJun
 * Created on 2018/12/25
 */

// 二叉树的下一个节点
public class day10 {
    public static class BinaryTreeNode {
        public char value;
        public BinaryTreeNode left;
        public BinaryTreeNode right;
        public BinaryTreeNode parent;

        public BinaryTreeNode(char value) {
            this.value = value;
        }

        public BinaryTreeNode() {
        }
    }

    public static BinaryTreeNode nextNode(BinaryTreeNode tree) {
        // 参数有效性检查
        if (tree == null) {
            return null;
        }
        BinaryTreeNode next = null;
        if (tree.right != null) {
            next = tree.right;
            while (next.left != null) {
                next = next.left;
            }
        } else if (tree.parent != null) {

            while(tree.parent != null && tree == tree.parent.right){
                tree = tree.parent;
            }
            next = tree.parent;

        }
        return next;
    }

    public static void print(BinaryTreeNode node) {
        if (node != null) {
            print(node.left);
            System.out.print(node.value);
            print(node.right);
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode a = new BinaryTreeNode('a');
        BinaryTreeNode b = new BinaryTreeNode('b');
        BinaryTreeNode c = new BinaryTreeNode('c');
        BinaryTreeNode d = new BinaryTreeNode('d');
        BinaryTreeNode e = new BinaryTreeNode('e');
        BinaryTreeNode f = new BinaryTreeNode('f');
        BinaryTreeNode g = new BinaryTreeNode('g');
        BinaryTreeNode h = new BinaryTreeNode('h');
        BinaryTreeNode i = new BinaryTreeNode('i');
        a.left = b;     a.right = c;    a.parent = null;
        b.left = d;     b.right = e;    b.parent = a;
        c.left = f;     c.right = g;    c.parent = a;
        d.left = null;  d.right = null; d.parent = b;
        e.left = h;     e.right = i;    e.parent = b;
        f.left = null;  f.right = null; f.parent = c;
        g.left = null;  g.right = null; g.parent = c;
        h.left = null;  h.right = null; h.parent = e;
        i.left = null;  i.right = null; i.parent = e;

        System.out.println(nextNode(a) != null ? nextNode(a) : "null");
        System.out.println(nextNode(b) != null ? nextNode(b) : "null");
        System.out.println(nextNode(c) != null ? nextNode(c) : "null");
        System.out.println(nextNode(d) != null ? nextNode(d) : "null");
        System.out.println(nextNode(e) != null ? nextNode(e) : "null");
        System.out.println(nextNode(f) != null ? nextNode(f) : "null");
        System.out.println(nextNode(g) != null ? nextNode(g) : "null");
        System.out.println(nextNode(h) != null ? nextNode(h) : "null");
        System.out.println(nextNode(i) != null ? nextNode(i) : "null");
    }

}