二叉树

发表于 | 分类于
字数统计: 1k | 阅读时长 ≈ 4

树结构提高了数据的存储、读取速度。

二叉树基本概念

每个节点最多只能有两个子节点，分别为左节点，右节点。

满二叉树：节点数=2^n-1，n为层数。

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

二叉树的遍历

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

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

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
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建二叉树
        BinaryTree tree = new BinaryTree();
        // 创建节点
        Node root = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4 );
        // 在树中添加节点
        tree.setRoot(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        System.out.println("前序遍历：");
        tree.preOrder();// 1243
        System.out.println("中序遍历：");
        tree.midOrder();// 4213
        System.out.println("后序遍历：");
        tree.lastOrder();// 4231
    }

}

// 创建二叉树
class BinaryTree {
    private Node root; // 根节点

    public BinaryTree() {
    }

    public Node getRoot() {
        return root;
    }

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

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

    // 中序遍历
    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("当前二叉树为空！");
        }
    }

    // 后序遍历
    public void lastOrder() {
        if (root != null) {
            root.lastOrder();
        } else {
            System.out.println("当前二叉树为空！");
        }
    }

}


// 创建节点
class Node {
    private int no;// 存储的数据
    private Node left; // 左节点
    private Node right; // 右节点

    public Node(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

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

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

    // 前序遍历
    public void preOrder() {
        // 打印根节点(当前节点)
        System.out.println(this);
        // 递归遍历左子树
        if (this.left != null) {
            this.left.preOrder();
        }
        // 递归遍历右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void midOrder() {
        // 递归遍历左子树
        if (this.left != null) {
            this.left.midOrder();
        }
        // 打印根节点(当前节点)
        System.out.println(this);
        // 递归遍历右子树
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    // 后续遍历
    public void lastOrder() {
        // 递归遍历左子树
        if (this.left != null) {
            this.left.lastOrder();
        }
        // 递归遍历右子树
        if (this.right != null) {
            this.right.lastOrder();
        }
        // 打印根节点
        System.out.println(this);
    }
}

二叉树查找指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 前序遍历查找节点
public Node preOrderSearch(int no) {
    Node node = null;
    // 判断是否是当前节点
    if (no == this.no) {
        return this;
    }
    // 判断当前节点的左子节点是否为空，不为空则递归查找
    if (this.left != null) {
        node = this.left.preOrderSearch(no);
    }
    // 找到后直接返回
    if (node != null) {
        return node;
    }
    // 判断当前节点的右子节点是否为空，不为空则递归查找
    if (this.right != null) {
        this.right.preOrderSearch(no);
    }
    return node;
}
1
2
3
4
5
6
7
8
9
// 前序遍历查找节点
public Node preOrderSearch(int no) {
    if (root != null) {
        return root.preOrderSearch(no);
    } else {
        System.out.println("当前二叉树为空！");
        return null;
    }
}

删除指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 删除指定节点
public void delete(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;
    }
    // 如果左子节点不是该节点，则对左子树进行递归删除
    if(this.left!=null){
        this.left.delete(no);
    }
    // 如果右子节点不是该节点，则对右子树进行递归删除
    if(this.right!=null){
        this.right.delete(no);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
// 删除指定节点
public void delete(int no) {
    if (root != null) {
        if (root.getNo() == no) {
            root = null;
        } else {
            root.delete(no);
        }
    } else {
        System.out.println("当前二叉树为空！");
    }
}