目录
  1. 1. 节点:节点内容、左子孩子、右子孩子、父亲。
  2. 2. 二叉树构造和操作
  3. 3. 测试
算法-二叉树操作

二叉树的具体特性和细节知识点,自行百度,直接上代码。

节点:节点内容、左子孩子、右子孩子、父亲。

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
class Node {
private int data;
private Node leftChild;
private Node rightChild;
private Node parent;

public Node getParent() {
return parent;
}

public void setParent(Node parent) {
this.parent = parent;
}

public Node(int data, Node leftChild, Node rightChild, Node parent) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;

}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getLeftChild() {
return leftChild;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getRightChild() {
return rightChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}

}

二叉树构造和操作

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
public class BinaryTree {
private Node root;//根节点
//插入节点
public void insertNode(Node root, Node node) {

Node current = root;
while (true) {
if (node.getData() < current.getData()) {
if (current.getLeftChild() == null) {
node.setParent(current);
current.setLeftChild(node);
break;
} else {
current = current.getLeftChild();
}
} else {
if (current.getRightChild() == null) {
node.setParent(current);
current.setRightChild(node);
break;
} else {
current = current.getRightChild();
}

}
}
}
//删除节点
public void deleteNode(Node node) {
if (node.equals(root)) {
root = null;
} else if (node.getParent() != null) {
if (node == node.getParent().getLeftChild()) {
node.getParent().setLeftChild(null);
} else {
node.getParent().setRightChild(null);

}
}
}

//获取某节点的高度
public int geHeight(Node node) {
if (node == null) {
return 0;
} else {
int leftHeight = geHeight(node.getLeftChild());
int rightHeight = geHeight(node.getRightChild());
int max = Math.max(leftHeight, rightHeight);
return max + 1;
}
}

//获取某节点的子节点个数
public int getChildNodes(Node node) {
if (node == null) {
return 0;
} else {
int leftNodes = getChildNodes(node.getLeftChild());
int rightNodes = getChildNodes(node.getRightChild());
return leftNodes + rightNodes + 1;
}
}

//先序遍历树
public void PreOrder(Node root) {
if (root == null)
return;
System.out.print(root.getData() + " ");
PreOrder(root.getLeftChild());
PreOrder(root.getRightChild());
}

//中序
public void MidOrder(Node root) {
if (root == null) return;
MidOrder(root.getLeftChild());
System.out.print(root.getData() + " ");
MidOrder(root.getRightChild());
}

//后序
public void LastOrder(Node root) {
if (root == null) return;
LastOrder(root.getLeftChild());
LastOrder(root.getRightChild());
System.out.print(root.getData() + " ");

}

public BinaryTree() {

}

public BinaryTree(Node root) {
this.root = root;
}

public Node getRoot() {
return root;
}

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

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
public static void main(String[] args) {
BinaryTree bt = new BinaryTree(new Node(1, null, null, null));
int a[] = {5, 3, 2, 7, 4, 9, 8};
for (int i = 0; i < 7; i++) {
bt.insertNode(bt.getRoot(), new Node(a[i], null, null, null));
}
// System.out.println(bt.geHeight(root));//高度
// bt.PreOrder(root);
// System.out.println();
// bt.MidOrder(root);
// System.out.println();
// bt.LastOrder(root);
// System.out.println();
// bt.deleteNode(bt.getRoot());
// bt.PreOrder(bt.getRoot());
// System.out.println(bt.getChildNodes(bt.getRoot()));//子节点数

}
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-二叉树操作/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论