【尚硅谷】Java数据结构与算法笔记10 - 树结构的基础部分_java数据结构及算法尚硅谷

---

一、二叉树

1.1 为什么需要树结构

1.1.1 数组存储方式的分析

优点: 通过下标方式访问元素, 速度快。对于有序数组, 还可使用二分查找提高检索速度。

缺点: 如果要检索具体某个值, 或者揷入值(按一定顺序)会整体移动, 效率较低

画出操作示意图:

1.1.2 链式存储方式的分析

优点: 在一定程度上对数组存储方式有优化(比如: 揷入一个数值节点, 只需要将揷入节点, 链接到链表中即可, 删除效率也很好)。

缺点: 在进行检索时, 效率仍然较低, 比如(检索某个值, 需要从头节点开始遍历)

画出操作示意图:

1.1.3 树存储方式的分析

优点：能提高数据存储, 读取的效率, 比如利用 二叉排序树(Binary Sort Tree), 既可以保证数据的检索速度, 同时也 可以保证数据的揷入, 删除, 修改的速度。

案例: $[7,3,10,1,5,9,12]$

1.2 树示意图

树的常用术语(结合示意图理解):

1）节点
2）根节点
3）父节点
4）子节点
5）叶子节点（没有子节点的节点)
6）节点的权(节点值)
7）路径(从 root 节点找到该节点的路线)
8）层
9）子权
10）树的高度(最大层数)
11）森林:多颗子树构成森林

1.3 二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树

二叉树的子节点分为左节点和右节点

如果该二叉树的所有叶子节点都在最后一层，并且结点总数为 $2^{n-1}$ ，$n$ 为层数，则我们称其为满二叉树

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

1.4 二叉树 - 遍历节点

前序遍历：先输出当前节点，再遍历左子树和右子树

中序遍历：先遍历左子树，再输出当前节点，再遍历右子树

后序遍历：先遍历左子树和右子树，最后输出当前节点

public class BinaryTreeErgodic {

    public static void main(String[] args) {
        // 先需要创建一颗二叉树
        BinaryTreeNode root = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        // 说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.left = node2;
        root.right = node3;
        node3.right = node4;
        node3.left = node5;
        // 测试前中后序遍历
        System.out.println("前序遍历");
        root.preOrderErgodic();
        System.out.println("中序遍历");
        root.infixOrderErgodic();
        System.out.println("后序遍历");
        root.postOrderErgodic();
    }

    static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;


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

        // 前序遍历：先输出当前节点，再遍历左子树和右子树
        public void preOrderErgodic() {
            System.out.println(value);
            if (left != null) {
                left.preOrderErgodic();
            }
            if (right != null) {
                right.preOrderErgodic();
            }
        }

        // 中序遍历：先遍历左子树，再输出当前节点，再遍历右子树
        public void infixOrderErgodic() {
            if (left != null) {
                left.infixOrderErgodic();
            }
            System.out.println(value);
            if (right != null) {
                right.infixOrderErgodic();
            }
        }

        // 后序遍历：先遍历左子树和右子树，最后输出当前节点
        public void postOrderErgodic() {
            if (left != null) {
                left.postOrderErgodic();
            }
            if (right != null) {
                right.postOrderErgodic();
            }
            System.out.println(value);
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

输出：

前序遍历
1
2
3
5
4
中序遍历
2
1
5
3
4
后序遍历
2
5
4
3
1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.5 二叉树 - 查找指定节点

public class BinaryTreeSearch {

    public static void main(String[] args) {
        // 先需要创建一颗二叉树
        BinaryTreeNode root = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        // 说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.left = node2;
        root.right = node3;
        node3.right = node4;
        node3.left = node5;
        // 测试前中后序遍历
        System.out.println("前序遍历查找");
        System.out.println(root.preOrderSearch(5));
        System.out.println("中序遍历查找");
        System.out.println(root.infixOrderSearch(5));
        System.out.println("后序遍历查找");
        System.out.println(root.postOrderSearch(5));
    }

    static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;


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

        // 前序遍历：先输出当前节点，再遍历左子树和右子树
        public BinaryTreeNode preOrderSearch(int num) {
            if (value == num) {
                return this;
            }
            if (left != null) {
                BinaryTreeNode node = left.preOrderSearch(num);
                if (node != null) {
                    return node;
                }
            }
            if (right != null) {
                return right.preOrderSearch(num);
            }
            return null;
        }

        // 中序遍历：先遍历左子树，再输出当前节点，再遍历右子树
        public BinaryTreeNode infixOrderSearch(int num) {
            if (left != null) {
                BinaryTreeNode node = left.infixOrderSearch(num);
                if (node != null) {
                    return node;
                }
            }
            if (value == num) {
                return this;
            }
            if (right != null) {
                return right.infixOrderSearch(num);
            }
            return null;
        }

        // 后序遍历：先遍历左子树和右子树，最后输出当前节点
        public BinaryTreeNode postOrderSearch(int num) {
            if (left != null) {
                BinaryTreeNode node = left.postOrderSearch(num);
                if (node != null) {
                    return node;
                }
            }
            if (right != null) {
                return right.postOrderSearch(num);
            }
            if (value == num) {
                return this;
            }
            return null;
        }

        @Override
        public String toString() {
            return "BinaryTreeNode{" +
                    "value=" + value +
                    '}';
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

输出：

前序遍历查找
BinaryTreeNode{value=5}
中序遍历查找
BinaryTreeNode{value=5}
后序遍历查找
BinaryTreeNode{value=5}
1
2
3
4
5
6

1.6 二叉树 - 删除节点

public class BinaryTreeRemove {

    public static void main(String[] args) {
        // 先需要创建一颗二叉树
        BinaryTreeNode root = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        // 说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
        root.left = node2;
        root.right = node3;
        node3.right = node4;
        node3.left = node5;
        // 测试前中后序遍历
        System.out.println("删除节点");
        root = BinaryTreeNode.removeNode(root, 5);
        if (root == null) {
            System.out.println("root = null");
        } else {
            root.preOrderErgodic();
        }
    }

    static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;


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

        // 前序遍历：先输出当前节点，再遍历左子树和右子树
        public static BinaryTreeNode removeNode(BinaryTreeNode node, int num) {
            if (node.value == num) {
                return null;
            }
            node.removeNode(num);
            return node;
        }

        private void removeNode(int num) {
            // 1. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
            if (this.left != null && this.left.value == num) {
                this.left = null;
                return;
            }
            // 2.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
            if (this.right != null && this.right.value == num) {
                this.right = null;
                return;
            }
            // 3.我们就需要向左子树进行递归删除
            if (this.left != null) {
                this.left.removeNode(num);
            }
            // 4.则应当向右子树进行递归删除
            if (this.right != null) {
                this.right.removeNode(num);
            }
        }

        // 前序遍历：先输出当前节点，再遍历左子树和右子树
        public void preOrderErgodic() {
            System.out.println(value);
            if (left != null) {
                left.preOrderErgodic();
            }
            if (right != null) {
                right.preOrderErgodic();
            }
        }

        @Override
        public String toString() {
            return "BinaryTreeNode{" +
                    "value=" + value +
                    '}';
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

输出：

删除节点
1
2
3
4
1
2
3
4
5

---

二、顺序存储二叉树

2.1 顺序存储二叉树的概念

从数据存储来看, 数组存储方式和树的存储方式可以相互转换, 即数组可以转换成树, 树也可以转换成数组, 看下面的示意图。

2.2 顺序存储二叉树遍历

public class ArrayBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        //创建一个 ArrBinaryTree
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        System.out.println("前序遍历");
        arrayBinaryTree.preOrder(); // 1,2,4,5,3,6,7
    }

    // 编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
    static class ArrayBinaryTree {
        private int[] arr;//存储数据结点的数组

        public ArrayBinaryTree(int[] arr) {
            this.arr = arr;
        }

        //重载preOrder
        public void preOrder() {
            this.preOrder(0);
        }

        //编写一个方法，完成顺序存储二叉树的前序遍历

        /**
         * @param index 数组的下标
         */
        public void preOrder(int index) {
            //如果数组为空，或者 arr.length = 0
            if (arr == null || arr.length == 0) {
                System.out.println("数组为空，不能按照二叉树的前序遍历");
            }
            //输出当前这个元素
            System.out.println(arr[index]);
            //向左递归遍历
            if ((index * 2 + 1) < arr.length) {
                preOrder(2 * index + 1);
            }
            //向右递归遍历
            if ((index * 2 + 2) < arr.length) {
                preOrder(2 * index + 2);
            }
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

三、线索化二叉树

3.1 先看一个问题

问题分析：

1. 当我们对上面的二叉树进行中序遍历时，数列为：[8，3，10，1，6，14]
2. 但是 6，8，10，14 这几个节点的左右指针，并没有完全的利用上
3. 如果我们希望充分利用各个节点的左右指针，让各个节点可以指向自己的前后节点怎么办？
4. 解决方案就是：线索二叉树

3.2 线索二叉树基本介绍

3.3 线索二叉树应用案例

3.4 遍历线索化二叉树

说明：对前面的中序线索化二叉树，进行遍历
分析：因为线索化后，各个节点指向有变化，因此原来的遍历方式不能使用，这是需要使用新的方式遍历线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。遍历的次序应当和中序遍历保持一致。

public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        // 测试一把中序线索二叉树的功能
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "mary");
        HeroNode node5 = new HeroNode(10, "king");
        HeroNode node6 = new HeroNode(14, "dim");

        // 二叉树，后面我们要递归创建, 现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        // 测试中序线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        // 测试: 以10号节点测试
        HeroNode leftNode = node5.getLeft();
        HeroNode rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点是 =" + leftNode); //3
        System.out.println("10号结点的后继结点是=" + rightNode); //1

        // 当线索化二叉树后，能在使用原来的遍历方法
        // threadedBinaryTree.infixOrder();
        System.out.println("使用线索化的方式遍历 线索化二叉树");
        threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6

    }

    // 定义ThreadedBinaryTree 实现了线索化功能的二叉树
    static class ThreadedBinaryTree {
        private HeroNode root;

        // 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
        // 在递归进行线索化时，pre 总是保留前一个结点
        private HeroNode pre = null;

        public void setRoot(HeroNode root) {
            this.root = root;
        }

        // 重载一把threadedNodes方法
        public void threadedNodes() {
            this.threadedNodes(root);
        }

        // 遍历线索化二叉树的方法
        public void threadedList() {
            // 定义一个变量，存储当前遍历的结点，从root开始
            HeroNode node = root;
            while (node != null) {
                // 循环的找到leftType == 1的结点，第一个找到就是8结点
                // 后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
                // 处理后的有效结点
                while (node.getLeftType() == 0) {
                    node = node.getLeft();
                }

                // 打印当前这个结点
                System.out.println(node);
                // 如果当前结点的右指针指向的是后继结点,就一直输出
                while (node.getRightType() == 1) {
                    // 获取到当前结点的后继结点
                    node = node.getRight();
                    System.out.println(node);
                }
                // 替换这个遍历的结点
                node = node.getRight();

            }
        }

        // 编写对二叉树进行中序线索化的方法

        /**
         * @param node 就是当前需要线索化的结点
         */
        public void threadedNodes(HeroNode node) {

            // 如果node==null, 不能线索化
            if (node == null) {
                return;
            }

            // (一)先线索化左子树
            threadedNodes(node.getLeft());
            // (二)线索化当前结点[有难度]

            // 处理当前结点的前驱结点
            // 以8结点来理解
            // 8结点的.left = null , 8结点的.leftType = 1
            if (node.getLeft() == null) {
                // 让当前结点的左指针指向前驱结点
                node.setLeft(pre);
                // 修改当前结点的左指针的类型,指向前驱结点
                node.setLeftType(1);
            }

            // 处理后继结点
            if (pre != null && pre.getRight() == null) {
                // 让前驱结点的右指针指向当前结点
                pre.setRight(node);
                // 修改前驱结点的右指针类型
                pre.setRightType(1);
            }
            // 每处理一个结点后，让当前结点是下一个结点的前驱结点
            pre = node;

            // (三)在线索化右子树
            threadedNodes(node.getRight());


        }

        // 删除结点
        public void delNode(int no) {
            if (root != null) {
                // 如果只有一个root结点, 这里立即判断root是不是就是要删除结点
                if (root.getNo() == no) {
                    root = null;
                } else {
                    // 递归删除
                    root.delNode(no);
                }
            } else {
                System.out.println("空树，不能删除~");
            }
        }

        // 前序遍历
        public void preOrder() {
            if (this.root != null) {
                this.root.preOrder();
            } else {
                System.out.println("二叉树为空，无法遍历");
            }
        }

        // 中序遍历
        public void infixOrder() {
            if (this.root != null) {
                this.root.infixOrder();
            } else {
                System.out.println("二叉树为空，无法遍历");
            }
        }

        // 后序遍历
        public void postOrder() {
            if (this.root != null) {
                this.root.postOrder();
            } else {
                System.out.println("二叉树为空，无法遍历");
            }
        }

        // 前序遍历
        public HeroNode preOrderSearch(int no) {
            if (root != null) {
                return root.preOrderSearch(no);
            } else {
                return null;
            }
        }

        // 中序遍历
        public HeroNode infixOrderSearch(int no) {
            if (root != null) {
                return root.infixOrderSearch(no);
            } else {
                return null;
            }
        }

        // 后序遍历
        public HeroNode postOrderSearch(int no) {
            if (root != null) {
                return this.root.postOrderSearch(no);
            } else {
                return null;
            }
        }
    }

    // 先创建HeroNode 结点
    static class HeroNode {
        private int no;
        private String name;
        private HeroNode left; // 默认null
        private HeroNode right; // 默认null
        // 说明
        // 1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
        // 2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点
        private int leftType;
        private int rightType;


        public int getLeftType() {
            return leftType;
        }

        public void setLeftType(int leftType) {
            this.leftType = leftType;
        }

        public int getRightType() {
            return rightType;
        }

        public void setRightType(int rightType) {
            this.rightType = rightType;
        }

        public HeroNode(int no, String name) {
            this.no = no;
            this.name = name;
        }

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public HeroNode getLeft() {
            return left;
        }

        public void setLeft(HeroNode left) {
            this.left = left;
        }

        public HeroNode getRight() {
            return right;
        }

        public void setRight(HeroNode right) {
            this.right = right;
        }

        @Override
        public String toString() {
            return "HeroNode [no=" + no + ", name=" + name + "]";
        }

        // 递归删除结点
        // 1.如果删除的节点是叶子节点，则删除该节点
        // 2.如果删除的节点是非叶子节点，则删除该子树
        public void delNode(int no) {

            //思路
		/*
		 * 	1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
			2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
			3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
			4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
			5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.

		 */
            // 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
            if (this.left != null && this.left.no == no) {
                this.left = null;
                return;
            }
            // 3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
            if (this.right != null && this.right.no == no) {
                this.right = null;
                return;
            }
            // 4.我们就需要向左子树进行递归删除
            if (this.left != null) {
                this.left.delNode(no);
            }
            // 5.则应当向右子树进行递归删除
            if (this.right != null) {
                this.right.delNode(no);
            }
        }

        // 编写前序遍历的方法
        public void preOrder() {
            System.out.println(this); // 先输出父结点
            // 递归向左子树前序遍历
            if (this.left != null) {
                this.left.preOrder();
            }
            // 递归向右子树前序遍历
            if (this.right != null) {
                this.right.preOrder();
            }
        }

        // 中序遍历
        public void infixOrder() {

            // 递归向左子树中序遍历
            if (this.left != null) {
                this.left.infixOrder();
            }
            // 输出父结点
            System.out.println(this);
            // 递归向右子树中序遍历
            if (this.right != null) {
                this.right.infixOrder();
            }
        }

        // 后序遍历
        public void postOrder() {
            if (this.left != null) {
                this.left.postOrder();
            }
            if (this.right != null) {
                this.right.postOrder();
            }
            System.out.println(this);
        }

        // 前序遍历查找

        /**
         * @param no 查找no
         * @return 如果找到就返回该Node ,如果没有找到返回 null
         */
        public HeroNode preOrderSearch(int no) {
            System.out.println("进入前序遍历");
            // 比较当前结点是不是
            if (this.no == no) {
                return this;
            }
            // 1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
            // 2.如果左递归前序查找，找到结点，则返回
            HeroNode resNode = null;
            if (this.left != null) {
                resNode = this.left.preOrderSearch(no);
            }
            if (resNode != null) { // 说明我们左子树找到
                return resNode;
            }
            // 1.左递归前序查找，找到结点，则返回，否继续判断，
            // 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
            if (this.right != null) {
                resNode = this.right.preOrderSearch(no);
            }
            return resNode;
        }

        // 中序遍历查找
        public HeroNode infixOrderSearch(int no) {
            // 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
            HeroNode resNode = null;
            if (this.left != null) {
                resNode = this.left.infixOrderSearch(no);
            }
            if (resNode != null) {
                return resNode;
            }
            System.out.println("进入中序查找");
            // 如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
            if (this.no == no) {
                return this;
            }
            // 否则继续进行右递归的中序查找
            if (this.right != null) {
                resNode = this.right.infixOrderSearch(no);
            }
            return resNode;

        }

        // 后序遍历查找
        public HeroNode postOrderSearch(int no) {

            // 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
            HeroNode resNode = null;
            if (this.left != null) {
                resNode = this.left.postOrderSearch(no);
            }
            if (resNode != null) { // 说明在左子树找到
                return resNode;
            }

            // 如果左子树没有找到，则向右子树递归进行后序遍历查找
            if (this.right != null) {
                resNode = this.right.postOrderSearch(no);
            }
            if (resNode != null) {
                return resNode;
            }
            System.out.println("进入后序查找");
            // 如果左右子树都没有找到，就比较当前结点是不是
            if (this.no == no) {
                return this;
            }
            return resNode;
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417

输出：

10号结点的前驱结点是 =HeroNode [no=3, name=jack]
10号结点的后继结点是=HeroNode [no=1, name=tom]
使用线索化的方式遍历 线索化二叉树
HeroNode [no=8, name=mary]
HeroNode [no=3, name=jack]
HeroNode [no=10, name=king]
HeroNode [no=1, name=tom]
HeroNode [no=14, name=dim]
HeroNode [no=6, name=smith]
1
2
3
4
5
6
7
8
9