【数据结构】树

一：树

1.1 概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 根结点：根节点没有前驱结点。
• 除根节点外，其余结点被分成是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
• 因此，树是递归定义的。

1.2 定义

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点可以有零个或多个后继。因此n个结点的树中有n-1条边。

1.3 基本术语

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为2
• 叶节点：度为0的节点称为叶节点； 如上图：G、H、I节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：B、D、C、E、F节点为分支节点
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为2
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m棵互不相交的树的集合称为森林；

1.4 树的遍历

遍历表达法有4种方法：先序遍历（前序遍历）、中序遍历、后序遍历、层次遍历。

• 先序遍历：对树按照根、左、右的规律进行访问。上图的遍历结果为ABCDEFG。
• 中序遍历：对树按照左、根、右的规律进行访问。上图的遍历结果为DBAGECF。
• 后序遍历：对树按照左、右、根的规律进行访问。上图的遍历结果为DBGEFCA。
• 层次遍历：对树按照从上到下、从左到右的规律进行访问。上图的遍历结果为ABCDEFG。

1.5 存储结构

由于树中每个结点的孩子可以有多个，所以简单的顺序存储结构无法满足树的实现要求。下面介绍三种常用的表示树的方法：双亲表示法、孩子表示法和孩子兄弟表示法。

1.5.1 双亲表示法

由于树中每个结点都仅有一个双亲结点（根节点没有），我们可以使用指向双亲结点的指针来表示树中结点的关系。这种表示法有点类似于前面介绍的静态链表的表示方法。具体做法是以一组连续空间存储树的结点，同时在每个结点中，设一个「游标」指向其双亲结点在数组中的位置。代码如下：

public class PTree<E> {
    private static final int DEFAULT_CAPACITY = 100;
    private int size;
    private Node[] nodes;

    private class Node() {
        E data;
        int parent;

        Node(E data, int parent) {
            this.data = data;
            this.parent = parent;
        }
    }

    public PTree() {
        nodes = new PTree.Node[DEFAULT_CAPACITY];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

由于根结点没有双亲结点，我们约定根节点的parent域值为-1。树的双亲表示法如下所示：

这样的存储结构，我们可以根据结点的parent域在O(1)的时间找到其双亲结点，但是只能通过遍历整棵树才能找到它的孩子结点。一种解决办法是在结点结构中增加其孩子结点的域，但若结点的孩子结点很多，结点结构将会变的很复杂。

1.5.2 孩子表示法

由于树中每个结点可能有多个孩子，可以考虑用多重链表，即每个结点有多个指针域，每个指针指向一个孩子结点，我们把这种方法叫多重链表表示法。它有两种设计方案：
方案一：指针域的个数等于树的度。其结点结构可以表示为：

class Node() {
    E data;
    Node child1;
    Node child2;
    ...
    Node childn;
}

1
2
3
4
5
6
7
8

对于上一节中的树，树的度为3，其实现为：

显然，当树中各结点的度相差很大时，这种方法对空间有很大的浪费。

方案二，每个结点指针域的个数等于该结点的度，取一个位置来存储结点指针的个数。其结点结构可以表示为：

class Node() {
    E data;
    int degree;
    Node[] nodes;
    Node(int degree) {
        this.degree = degree;
        nodes = new Node[degree];
    }
}

1
2
3
4
5
6
7
8
9
10

对于上一节中的树，这种方法的实现为：

这种方法克服了浪费空间的缺点，但由于各结点结构不同，在运算上会带来时间上的损耗。

为了减少空指针的浪费，同时又使结点相同。我们可以将顺序存储结构和链式存储结构相结合。具体做法是：把每个结点的孩子结点以单链表的形式链接起来，若是叶子结点则此单链表为空。然后将所有链表存放进一个一维数组中。这种表示方法被称为孩子表示法。其结构为：

代码表示：

public class CTree<E> {
    private static final int DEFAULT_CAPACITY = 100;
    private int size;
    private Node[] nodes;

    private class Node() {
        E data;
        ChildNode firstChild;
    }
    
    //链表结点
    private class ChildNode() {
        int cur; //存放结点在nodes数组中的下标
        ChildNode next;
    }

    public CTree() {
        nodes = new CTree.Node[DEFAULT_CAPACITY];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这种结构对于查找某个结点的孩子结点比较容易，但若想要查找它的双亲或兄弟，则需要遍历整棵树，比较麻烦。可以将双亲表示法和孩子表示法相结合，这种方法被称为双亲孩子表示法。其结构如下：

其代码和孩子表示法的基本相同，只需在Node结点中增加parent域即可。

1.5.3 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在则是唯一的，它的右兄弟如果存在也是唯一的。因此，我们可以使用两个分别指向该结点的第一个孩子和右兄弟的指针来表示一颗树。其结点结构为：

class Node() {
    E data;
    Node firstChild;
    Node rightSib;
}

1
2
3
4
5
6

其结构如下：

这个方法，可以方便的查找到某个结点的孩子，只需先通过firstChild找到它的第一个孩子，然后通过rightSib找到它的第二个孩子，接着一直下去，直到找到想要的孩子。若要查找某个结点的双亲和左兄弟，使用这个方法则比较麻烦。

这个方法最大的好处是将一颗复杂的树变成了一颗二叉树。这样就可以使用二叉树的一些特性和算法了。

1.6 为什么需要树这种数据结构

1.6.1 数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

1.6.2 链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

1.6.3 树存储方式的分析

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

二：二叉树

2.1 定义

二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0)，n=0时为空树，n>0时为非空树。对于非空树T：

• 有且仅有一个根结点；
• 除根结点外的其余结点又可分为两个不相交的子集TL和TR ，分别称为T的左子树和右子树，且TL 和TR本身又都是二叉树。

很明显该定义属于递归定义，所以有关二叉树的操作使用递归往往更容易理解和实现。从定义也可以看出二叉树与一般树的区别主要是两点，一是每个结点的度最多为2；二是结点的子树有左右之分，不能随意调换，调换后又是一棵新的二叉树。

2.2 形态

2.2.1 五种基本形态

从上面二叉树的递归定义可以看出，二叉树或为空，或为一个根结点加上两棵左右子树，因为两棵左右子树也是二叉树也可以为空，所以二叉树有5种基本形态：

2.2.2 三种特殊形态

2.3 存储

存的目的是为了取，而取的关键在于如何通过父结点拿到它的左右子结点，不同存储方式围绕的核心也就是这。

2.3.1 顺序存储

使用一组地址连续的存储单元存储，例如数组。为了在存储结构中能得到父子结点之间的映射关系，二叉树中的结点必须按层次遍历的顺序存放。具体是：

• 对于完全二叉树，只需要自根结点起从上往下、从左往右依次存储。
• 对于非完全二叉树，首先将它变换为完全二叉树，空缺位置用某个特殊字符代替（比如#），然后仍按完全二叉树的存储方式存储。

假设将一棵二叉树按此方式存储到数组后，左子结点下标=2倍的父结点下标+1，右子节点下标=2倍的父结点下标+2（这里父子结点间的关系是基于根结点从0开始计算的）。若数组某个位置处值为#，代表此处对应的结点为空。可以看出顺序存储非常适合存储接近完全二叉树类型的二叉树，对于一般二叉树有很大的空间浪费，所以对于一般二叉树，一般用下面这种链式存储。

2.3.2 链式存储

对每个结点，除数据域外再多增加左右两个指针域，分别指向该结点的左孩子和右孩子结点，再用一个头指针指向根结点。对应的存储结构。

2.4 遍历

二叉树由三个基本单元组成：根结点，左子树，右子树，因此存在6种遍历顺序，若规定先左后右，则只有以下3种：

2.4.1 先序遍历

若二叉树为空，则空操作；否则：
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树

2.4.2 中序遍历

若二叉树为空，则空操作；否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树

2.4.3 后序遍历

若二叉树为空，则空操作；否则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点

下面是将以下二叉树的顺序存储[A,B,C,D,E,F,G,#,#,H,#,#,I]转换为链式存储的代码，结点不存在用字符#表示，并分别遍历。

对于下面这棵二叉树，其遍历顺序：
先序：ABDEHCFIG
中序：DBHEAFICG
后序：DHEBIFGCA

三：二叉树遍历、查找、删除

3.1 二叉树的遍历

3.1.1 编写节点实体类

/**
 * 创建node节点
 */
class Node {

    /**
     * 编号
     */
    private int no;

    /**
     * 姓名
     */
    private String name;

    /**
     * 左节点
     * 默认为null
     */
    private Node left;

    /**
     * 右节点
     * 默认为null
     */
    private Node right;

    /**
     * 含参构造
     *
     * @param no   编号
     * @param name 姓名
     */
    public Node(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 Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

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

}
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

3.1.2 前序遍历

/**
     * 前序遍历方法
     */
    public void preOrder() {
        //先输出父节点，this指的是当前父节点
        System.out.println(this);
        //向左子树递归前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        //向右子树递归前序遍历
        if (this.right != null) {
            this.right.preOrder();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.1.3 中序遍历

 /**
     * 中序遍历
     */
    public void infixOrder() {
        //递归向左子树中序遍历
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出父节点
        System.out.println(this);
        //向右子树递归中序遍历
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.1.4 后序遍历

/**
     * 后序遍历
     */
    public void postOrder() {
        //递归向左子树后序遍历
        if (this.left != null) {
            this.left.postOrder();
        }
        //向右子树递归后序遍历
        if (this.right != null) {
            this.right.postOrder();
        }
        //输出父节点
        System.out.println(this);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.1.5 定义二叉树

class BinaryTree {

    /**
     * 二叉树的根节点
     */
    private Node root;

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

    /**
     * 前序遍历
     */
    public void preOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.postOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

}
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

3.1.6 测试二叉树

public class BinaryTreeDemo {

    public static void main(String[] args) {
       //先创建一颗二叉树
        BinaryTrees binaryTrees = new BinaryTrees();
        //创建需要的节点
        Node root = new Node(1, "葛羽");
        Node node2 = new Node(2, "张意涵");
        Node node3 = new Node(3, "黑小色");
        Node node4 = new Node(4, "钟锦亮");
        Node node5 = new Node(5, "黎泽剑");
        Node node6 = new Node(6, "陈泽彬");
        //说明我们先手动创建二叉树，随后使用递归创建
        root.setLeft(node2);
        node2.setLeft(node3);
        root.setRight(node4);
        node4.setRight(node5);
        node4.setLeft(node6);
        binaryTrees.setRoot(root);
        //前序遍历
        System.out.println("前序遍历");
        binaryTrees.preOrder();
        //中序遍历
        System.out.println("中序遍历");
        binaryTrees.infixOrder();
        //后序遍历
        System.out.println("后序遍历");
        binaryTrees.postOrder();
    }
}
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

3.2 二叉树查找

3.2.1 思路分析

前序查找

1. 先判断当前节点的no是否为需要查找的，如果相等，则返回当前节点
2. 如果不等，则判断当前节点的左子节点是否为为空，如果不为空，则递归进行查找
3. 如果左子节点前序递归，找到了则返回。找不到的话则判断右子节点是否为空，如果不为空，则继续向右递归

中序查找

1. 判断左子节点是否为空，如果不为空，则递归中序查找。如果找到则返回，找不到的话
2. 判断当前节点是否相等，如果相等则直接返回，不相等的话
3. 判断右子节点是否为空，如果不为空，则递归中序查找。如果找到则返回，找不到的话则返回null

后续查找

1. 判断左子节点是否为空，如果不为空，则递归中序查找。如果找到则返回，找不到的话
2. 判断右子节点是否为空，如果不为空，则递归中序查找。如果找到则返回，找不到的话
3. 判断当前节点是否相等，如果相等则直接返回，不相等的话，则返回null

3.2.2 前序，中序，后续查找代码实现

注：写到Node类里面

/**
     * 前序遍历查找方法
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node preOrderSearch(int no) {
        //判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1如果不为空，则递归进行查找
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断当前节点的右子节点是否为空
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        //向右找，不管找没找到直接返回。因为最后只需要判断node是否为空就可以判断找没找到
        return resNode;
    }

    /**
     * 中序遍历查找方法
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node infixOrderSearch(int no) {
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1 如果不为空则中序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        //3.判断右子节点是否为空，如果不为空，则递归中序查找。如果找到则返回
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找方法
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node postOrderSearch(int no) {
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1 如果不为空则后序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断右子节点是否为空，如果不为空，则递归后序查找。如果找到则返回
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        if (resNode != null) {
            //2.1 满足当前条件就说明找到了，就返回
            return resNode;
        }
        //3.判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        return null;

    }
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

3.2.3 二叉树中前序，中序，后续查找代码实现

注：写到BinaryTrees类中

	/**
     * 前序遍历查找
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    /**
     * 中序遍历查找
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    /**
     * 后序遍历查找
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
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

3.2.4 测试前序，中序，后续查找

public class BinaryTreeDemo {

    public static void main(String[] args) {
        //先创建一颗二叉树
        BinaryTrees binaryTrees = new BinaryTrees();
        //创建需要的节点
        Node root = new Node(1, "葛羽");
        Node node2 = new Node(2, "张意涵");
        Node node3 = new Node(3, "黑小色");
        Node node4 = new Node(4, "钟锦亮");
        Node node5 = new Node(5, "黎泽剑");
        //说明我们先手动创建二叉树，随后使用递归创建
        root.setLeft(node2);
        node2.setLeft(node3);
        root.setRight(node4);
        node4.setRight(node5);
        binaryTrees.setRoot(root);
        //前序遍历
        System.out.println("前序遍历");
        binaryTrees.preOrder();
        //中序遍历
        System.out.println("中序遍历");
        binaryTrees.infixOrder();
        //后序遍历
        System.out.println("后序遍历");
        binaryTrees.postOrder();

        System.out.println("前序遍历查找");
        Node preOrderNode = binaryTrees.preOrderSearch(5);
        if (preOrderNode != null) {
            System.out.printf("找到了，信息为no=%d,name=%s", preOrderNode.getNo(), preOrderNode.getName());
        } else {
            System.out.printf("没有找到no=%d的英雄", 5);
        }

        System.out.println("中序遍历查找");
        Node infixOrderNode = binaryTrees.infixOrderSearch(5);
        if (infixOrderNode != null) {
            System.out.printf("找到了，信息为no=%d,name=%s", infixOrderNode.getNo(), infixOrderNode.getName());
        } else {
            System.out.printf("没有找到no=%d的英雄", 5);
        }

        System.out.println("后序遍历查找");
        Node postOrderNode = binaryTrees.postOrderSearch(5);
        if (postOrderNode != null) {
            System.out.printf("找到了，信息为no=%d,name=%s", postOrderNode.getNo(), postOrderNode.getName());
        } else {
            System.out.printf("没有找到no=%d的英雄", 5);
        }
    }
}
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

3.3 二叉树删除

3.3.1 要求

1. 如果删除的节点是叶子节点，则删除该节点
2. 如果删除的节点是非叶子节点，则删除该子树.

3.3.2 思路分析

1. 二叉树是单向的，所以我们判断当前节点的子节点是否需要删除节点，而不是判断当前节点是否需要删除节点。
2. 如果当前节点的左子树不为空，并且左子节点就是需要删除的节点。此时我们将this.left置空就行了，并且结束递归删除。
3. 如果当前节点的右子树不为空，并且右子节点就是需要删除的节点。此时我们将this.right置空就行了，并且结束递归删除。
4. 如果第二步和第三步没有删除节点，那么我们就需要对左子树进行递归删除。
5. 如果删除左子树没有成功，那么我们就需要对右子树进行递归删除。
6. 如果树本身只有一个root节点，则等价于将整个二叉树置空。

3.3.3 代码实现

在node类中添加

    /**
     * 要求：
     * 1.如果删除的节点是叶子节点，则删除该节点
     * 2.如果删除的节点是非叶子节点，则删除该子树
     * 

     * 思路：
     * 1.二叉树是单向的，所以我们判断当前节点的子节点是否需要删除节点，而不是判断当前节点是否需要删除节点。
     * 2.如果当前节点的左子树不为空，并且左子节点就是需要删除的节点。此时我们将this.left置空就行了，并且结束递归删除。
     * 3.如果当前节点的右子树不为空，并且右子节点就是需要删除的节点。此时我们将this.right置空就行了，并且结束递归删除。
     * 4.如果第二步和第三步没有删除节点，那么我们就需要对左子树进行递归删除。
     * 5.如果删除左子树没有成功，那么我们就需要对右子树进行递归删除。
     * 6.如果树本身只有一个root节点，则等价于将整个二叉树置空。
     *
     * @param no 需要删除的编号
     */
    public void deleteNode(int no) {
        //判断当前节点的左子树不为空，并且左子节点就是需要删除的节点。此时我们将this.left置空就行了，并且结束递归删除。
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        //判断当前节点的右子树不为空，并且右子节点就是需要删除的节点。此时我们将this.right置空就行了，并且结束递归删除。
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //向左子树递归删除
        if (this.left != null) {
            this.left.deleteNode(no);
        }
        //向右子树递归删除
        if (this.right != null) {
            this.right.deleteNode(no);
        }

    }
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

在BinaryTrees类中添加

/**
     * 删除节点
     *
     * @param no 需要删除的节点编号
     */
    public void deleteNode(int no) {
        if (root != null) {
            if(root.getNo() == no) {
                root = null;
            } else {
                root.deleteNode(no);
            }
        } else {
            System.out.println("二叉树为空，无法删除");
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.3.4 测试删除节点

在BinaryTreeDemo的main方法中添加

		System.out.println("删除节点之前");
        binaryTrees.infixOrder();
        binaryTrees.deleteNode(6);
        System.out.println("删除节点之后");
        binaryTrees.infixOrder();
1
2
3
4
5

四：二叉树的顺序存储

4.1 基本说明

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。

4.2 要求

1. 以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]
2. 遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历

4.3 顺序存储二叉树特点

1. 顺序二叉树通常只考虑完全二叉树
2. 第n个元素的左子节点为 2 * n + 1
3. 第n个元素的右子节点为 2 * n + 2
4. 第n个元素的父节点为 (n-1) / 2
5. n : 表示二叉树中的第几个元素

4.4 代码实现

需求：给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7

package com.sysg.dataStructuresAndAlgorithms.tree;

/**
 * 以数组的形式存储二叉树
 */
public class ArrayBinaryTreeDemo {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
        //从根节点的下标开始遍历，也就是0
        //前序遍历的结果就是1,2,4,5,3,6,7
        arrayBinaryTree.preOrder();
    }


}

/**
 * 顺序存储二叉树遍历
 */
class ArrayBinaryTree {

    /**
     * 存储二叉树节点的数组
     */
    private int[] array;

    /**
     * 重载preOrder这个方法
     */
    public void preOrder() {
        this.preOrder(0);
    }

    /**
     * 含参构造
     *
     * @param array 数组
     */
    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }


    /**
     * 顺序存储二叉树的前序遍历
     * 特点：
     * 1. 顺序二叉树通常只考虑完全二叉树
     * 2. 第n个元素的左子节点为  2 * n + 1
     * 3. 第n个元素的右子节点为  2 * n + 2
     * 4. 第n个元素的父节点为  (n-1) / 2
     * 5. n : 表示二叉树中的第几个元素
     *
     * @param index 表示数组的下标，也就是 n
     */
    public void preOrder(int index) {
        if (array.length == 0) {
            System.out.println("数组为空，不能遍历");
        }
        //输出当前元素
        System.out.println(array[index]);
        //向左递归遍历
        if ((index * 2 + 1) < array.length) {
            preOrder(index * 2 + 1);
        }
        //向右递归遍历
        if ((index * 2 + 2) < array.length) {
            preOrder(index * 2 + 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
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

五：线索化二叉树

5.1 先看一个问题

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7

问题分析:

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

5.2 基本介绍

1. n个结点的二叉链表中含有n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
3. 一个结点的前一个结点，称为前驱结点
4. 一个结点的后一个结点，称为后继结点

5.3 思路分析

思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}

说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:

1. left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
2. right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.

5.4 线索化二叉树代码实现

中序线索化二叉树代码实现

5.4.1 创建Node节点

package com.sysg.dataStructuresAndAlgorithms.tree;

/**
 * node节点
 */
public class Node {

    /**
     * 编号
     */
    private int no;

    /**
     * 姓名
     */
    private String name;

    /**
     * 左节点
     * 默认为null
     */
    private Node left;

    /**
     * 右节点
     * 默认为null
     */
    private Node right;

    /**
     * leftType = 0，则说明指向的是左子树
     * leftType = 1，则说明指向的是前驱节点
     */
    private int leftType;

    /**
     * rightType = 0，则说明指向的是右子树
     * rightType = 1，则说明指向的是后继节点
     */
    private int rightType;

    /**
     * 含参构造
     *
     * @param no   编号
     * @param name 姓名
     */
    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    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 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 Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

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

    /**
     * 前序遍历方法
     */
    public void preOrder() {
        //先输出父节点，this指的是当前父节点
        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 Node preOrderSearch(int no) {
        //判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1如果不为空，则递归进行查找
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断当前节点的右子节点是否为空
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        //向右找，不管找没找到直接返回。因为最后只需要判断node是否为空就可以判断找没找到
        return resNode;
    }

    /**
     * 中序遍历查找方法
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node infixOrderSearch(int no) {
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1 如果不为空则中序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        //3.判断右子节点是否为空，如果不为空，则递归中序查找。如果找到则返回
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找方法
     *
     * @param no 需要查找的no
     * @return 找到就返回该node，找不到就返回null
     */
    public Node postOrderSearch(int no) {
        //1.判断当前节点的左子节点是否为为空
        Node resNode = null;
        //1.1 如果不为空则后序查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            //1.2满足当前条件就说明找到了，就返回
            return resNode;
        }
        //2.判断右子节点是否为空，如果不为空，则递归后序查找。如果找到则返回
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        if (resNode != null) {
            //2.1 满足当前条件就说明找到了，就返回
            return resNode;
        }
        //3.判断当前节点是否相等，如果相等则直接返回
        if (this.no == no) {
            return this;
        }
        return null;

    }

    /**
     * 要求：
     * 1.如果删除的节点是叶子节点，则删除该节点
     * 2.如果删除的节点是非叶子节点，则删除该子树
     * 

     * 思路：
     * 1.二叉树是单向的，所以我们判断当前节点的子节点是否需要删除节点，而不是判断当前节点是否需要删除节点。
     * 2.如果当前节点的左子树不为空，并且左子节点就是需要删除的节点。此时我们将this.left置空就行了，并且结束递归删除。
     * 3.如果当前节点的右子树不为空，并且右子节点就是需要删除的节点。此时我们将this.right置空就行了，并且结束递归删除。
     * 4.如果第二步和第三步没有删除节点，那么我们就需要对左子树进行递归删除。
     * 5.如果删除左子树没有成功，那么我们就需要对右子树进行递归删除。
     * 6.如果树本身只有一个root节点，则等价于将整个二叉树置空。
     *
     * @param no 需要删除的编号
     */
    public void deleteNode(int no) {
        //判断当前节点的左子树不为空，并且左子节点就是需要删除的节点。此时我们将this.left置空就行了，并且结束递归删除。
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        //判断当前节点的右子树不为空，并且右子节点就是需要删除的节点。此时我们将this.right置空就行了，并且结束递归删除。
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //向左子树递归删除
        if (this.left != null) {
            this.left.deleteNode(no);
        }
        //向右子树递归删除
        if (this.right != null) {
            this.right.deleteNode(no);
        }

    }

}

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

5.4.2 中序线索化二叉树

/**
 * 定义一个二叉树 binaryTree
 */
class BinaryTrees {

    /**
     * 二叉树的根节点
     */
    private Node root;

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

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


    /**
     * 中序线索化二叉树
     *
     * @param node 需要线索化的节点
     */
    public void threadNodes(Node node) {
        //如果node节点为空，则无法进行线索化
        if (node == null) {
            return;
        }
        //1.线索化左子树
        threadNodes(node.getLeft());
        //2.线索化当前节点
        //2.1 处理当前节点的前驱节点
        //以8这个节点来理解
        //8节点的left = null,8节点的leftType = 1
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针类型,指向前驱节点
            node.setLeftType(1);
        }
        //2.2 处理当前节点的后继节点
        //后继节点是下一次递归操作时才会进行
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }

        //每处理一个节点，让当前节点是下一个节点的前驱节点
        pre = node;
        //3.线索化右子树
        threadNodes(node.getRight());

    }

    /**
     * 前序遍历
     */
    public void preOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder() {
        //判断根节点是否为空
        if (this.root != null) {
            //调用root节点里面的preOrder方法
            this.root.postOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }


}
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

5.4.3 测试中序线索化二叉树

public class BinaryTreeDemo {

    public static void main(String[] args) {
        //先创建一颗二叉树
        BinaryTrees binaryTrees = new BinaryTrees();
        //创建需要的节点
        Node root = new Node(1, "葛羽");
        Node node2 = new Node(3, "张意涵");
        Node node3 = new Node(6, "黑小色");
        Node node4 = new Node(8, "钟锦亮");
        Node node5 = new Node(10, "黎泽剑");
        Node node6 = new Node(14, "吴九阴");
        //说明我们先手动创建二叉树，随后使用递归创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        binaryTrees.setRoot(root);
        binaryTrees.threadNodes();

        //以10号节点进行测试
        Node leftNode = node5.getLeft();
        Node rightNode = node5.getRight();
        System.out.println("10号节点的前驱节点是=" + leftNode);
        System.out.println("10号节点的后继节点是=" + rightNode);
    }
}
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

5.5 线索化遍历二叉树

/**
     * 遍历线索化二叉树
     */
    public void threadList() {
        //定义一个变量，存储当前遍历的节点，从root开始
        Node node = root;
        while (node != null) {
            //循环找到leftType == 1的节点，第一个找到的就是8这个节点
            //后面会随着遍历的变化而变化，说明该节点是按照线索化
            //处理后的有效节点
            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();
        }

    }
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