java数据结构与算法 --- 第十章 数结构基础

第十章 树结构基础

I 引和基本概念

为什么需要树结构?
数组,查询快,增删慢
链表…
而树结构,同时提高查询和增删!

基本概念
术语: 有手就行

II 二叉树

1.概念:

二叉树:每个节点最多有两个子节点的数叫二叉树
满二叉树: 所有叶子节点都在最后一,结点的总数是2^n-1(n是层数)
完全二叉树:这个概念…怎么说呢,叶子几点只在最后或者倒数第二层,并且最后一层都是左边排列

完全二叉树看起来不完全,为什么叫做完全二叉树呢?
因为,涉及到顺序存储,空间充分利用

2.前中后序遍历,查找

前中后序,针对的是父节点的遍历时机(中序为例:左子节点遍历,父节点,右子结点遍历)

思路:
i 节点类里面完成前中后序遍历的具体操作操作
ii 创建二叉树类,完成操作管理,创建二叉树确定具体的根节点
iii 测试类,手动创建二叉树

上代码:

public class BinaryTreeDemo {
    @Test
    public void test() {
        Node root1 = new Node(1, "1");
        Node node2 = new Node(2, "2");
        Node node3 = new Node(3, "3");
        Node node4 = new Node(4, "4");
        Node node5 = new Node(5, "5");

        root1.setLeft(node2);
        root1.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);

        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setRoot(root1);

        binaryTree.preOrder();//1,2,3,5,4
        System.out.println();
//        binaryTree.infixOrder();//2,1,5,3,4
//        System.out.println();
//        binaryTree.postOrder();//2,5,4,3,1
//        binaryTree.preOrderSearch(2);
    }
}

//定义二叉树
class BinaryTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

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

    //前序
    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 void preOrderSearch(int no) {
        Node resnode = null;
        if (this.root != null) {
            resnode = this.root.preOrderSearch(no);
        }
        if (resnode != null) {
            System.out.println("查找结果-->" + resnode);
        } else {
            System.out.println("find nothings");
        }
    }
}

//创建结点
class Node {
    private int no;
    private String name;
    private Node left; //默认是null
    private Node right; //默认是null

    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 + '\'' +
                '}';
    }

    //编写前序遍历的方法
    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);
    }

    //前序遍历查找
    public Node preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        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

3.删除结点

叶子节点,删除结点;
非叶子结点,删除子树

思路:
因为二叉树是单向的,所以判断当前节点的子节点是否是需要删除的结点(而不是判断当前节点是不是需要删除的结点
i 针对左子节点(非空且是待删除),this.left = null;右子节点同理;
ii 如果没有删除结点,则左/右子树递归
iii 在节点类里面加入删除方法,没考虑根节点,要在二叉树类里面单独写一段判断root是否是待删除的条件

上代码:
节点类中的删除方法:

    //删除结点
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {//左子结点是待删除结点
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {//右子节点 是待删除结点
            this.right = null;
            return;
        }

        //如果左右子结点都不是待删除结点,遍历左右子树
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树类中的方法:

    //删除结点
    public void delNode(int no) {
        if (root != null && root.getNo() == no) {//判断root结点是否是待删除结点(节点类的删除没把root包含进去)
            root = null;
        }
        root.delNode(no);
    }
1
2
3
4
5
6
7

4.顺序存储二叉树

概念: 数组可以转化成树, 数可以转换成数组

顺序存储二叉树特点: (n是数组下标 对应二叉树的下标
i 通常只考虑完全二叉树
ii 第n个元素的左子节点:2*n+1 ;右子节点:2*n+2
iii 第n个元素是父节点: (n-1)/2

上代码:

public class ArrBinaryTreeDemo {
    @Test
    public void test() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);

        arrBinaryTree.preOrder();//1,2,4,5,3,6,7

    }
}

class ArrBinaryTree {
    private int[] arr;

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

    //方法重载,(针对第一步下标是0的,
    public void preOrder(){
        preOrder(0);
    }

    /**
     * 顺序存储-前序遍历
     *
     * @param index 数组下标
     */
    public void preOrder(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空,不能进行二叉树的前序遍历");
            return;
        }
        //输出当前的元素
        System.out.println(arr[index]);

        //左递归
        if ((index * 2 + 1) < arr.length) {
            preOrder((index * 2 + 1));
        }
        //右递归
        if ((index * 2 + 2) < arr.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

个人小结:
顺序存储二叉树,并没有实际创建结点. 而是先接受数组,按照二叉树的遍历方式输出.

5.线索化二叉树

引:二叉树的叶子结点,存在指针的浪费

基本介绍:
n个结点的二叉树有 n+1 个空指针域
利用二叉树的空指针域指向该结点的在某次遍历次序下的前驱或者后继结点的指针,叫做线索化二叉树(分,前中后序线索化二叉树)
如图:

实现思路:
线索化二叉树后,node结点的left和right存在两种情况:
i left可能指向左子树,也可能指向前驱
ii rigth…
传入一个node结点,定义一个pre结点(指向的是node的前驱)
如果传入的node的left是空,则让他指向前驱;同时每次线索化一个节点后,让pre指向node(记录下一个传入node参数的前驱结点),以此通过pre操作后继结点的指向!

上核心代码:
ndoe结点类:(在原来的基础上,加上了leftType和rightType,用来一个结点的left/right是指向左子树还是前驱/…
binaryTree创建二叉树类:(在原来的基础上,加入前驱结点pre,加入线索化的方法

//定义二叉树
class BinaryTree {
    
    //中序遍历
	....

	//前驱节点 ！！！ 注意每次线索化结点后更新...
    private Node pre = null;

    //线索化二叉树--中序
    public void threadedNodes(Node node) {
        if (node == null) {//不能线索化
            return;
        }

        //(一)线索化左子树
        threadedNodes(node.getLeft());

        //(二)线索化当前结点 -- 中序结果:(8,3,10,1,14,6)
        //处理当前节点的前驱节点 (以8 为例 8.left->null, 8.leftType = 1(前驱)
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针类型为1(指向的前驱节点)
            node.setLeftType(1);
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        //处理每个结点后,让当前结点是下一个结点的前驱节点
        pre = node;

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

    }
    //线索化重载
    public void threadedNodes(){
        threadedNodes(root);
    }
}

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

//结点类  :在基础上增加一个判断线索化相关的变量
class Node {

	....

    //中序线索化二叉树 说明:
    // --如果leftType/rightType为 0,表示指向左/右子树;为 1,则表示指向 前驱/后继结点
    private int leftType;
    private int rightType;

    //中序遍历
	....
	
	....
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

编程小结:
1.线索化二叉树,判断是否是叶子结点,很关键
2.每次线索化一个结点后,一定要把他设置为pre;因为需要通过pre设置后继节点
另外,关于线索化画出连线:只看叶子结点,根据中序遍历结果查看10,14等,可以发现和1的画线关系(只看叶子结点!!) 如下图:

6.遍历线索化二叉树

1.分析:
因为线索化之后,各个节点的指向有变化的,原来的遍历方法(判断左右子节点是否是空)不能使用了. 需要新的遍历方式遍历线索化二叉树,各个节点通过线性的方式遍历,提高了遍历的效率.…

2.上代码:
思路: – 循环
i 从根结开始找到第一个 leftType == 1的
ii 打印
iii 当前结点的右指针指向的是 后继节点(rightType==1 ),就一直输出
iiii 更新这次遍历的结点 (tempNode = tempNode.getRight();)

//线索化遍历二叉树 -- 中序(8,3,10,1,14,6)
public void threadedList() {
    Node tempNode = root;//从root开始遍历
    while (tempNode != null) {
        //循环,找到第一个为leftType==1的 -->8
        while (tempNode.getLeftType() == 0) {
            tempNode = tempNode.getLeft();
        }

        //打印
        System.out.println(tempNode);

        while (tempNode.getRightType() == 1) {
        //如果当前结点的右指针指向的是 后继节点,就一直输出
            tempNode = tempNode.getRight();
            System.out.println(tempNode);
        }

        //替换这个遍历的结点
        tempNode = tempNode.getRight();
    }
}

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