树
树(Tree)形结构是一种重要的非线性结构。树形结构反映了数据元素之间的层次关系和分支关系。
基本术语
一个结点的子树个数称为该结点的度(degree)，一棵树中结点度的最大值称为该树的度。度为0的结点称为叶子结点或者终端结点。
树中结点的后继结点称为儿子结点，结点的前趋结点称为儿子的父亲结点。
结点的层数使从根开始算起的。设根节点的层数为1，其他结点的层数等于父亲结点的层数加1.
若把树中每个结点的各子树看成从左到右有次序的(即不可互换的)，则称该树使有序树。
树中任一结点都可以有零个或者多个后继结点。但至多有一个前趋结点。树中只有根节点无前趋结点，叶子结点无后继结点。
二叉树
二叉树是由n结点组成的有限集合。此集合或者为空，或者有一个根节点加上两颗左右子树。
二叉树的性质：
1、二叉树第i(i>0)层上的结点最多为
$$
2^{i-1}
$$
2、高度为k的二叉树最多有的节点数
$$
2^k-1
$$
3、对任何二叉树T，n0 ，n1 ，n2 分别表示度数为0、1、2的结点个数。则n0 =n2 +1；
4、具有n个结点的完全二叉树(包括满二叉树)的高度为
$$
\lfloor \log n \rfloor + 1 或者 \lceil \log （n+1） \rceil
$$
5、满二叉树原理:非空满二叉树的叶结点数等于其分支结点数加1
二叉树的实现
通过链表来实现二叉树
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
|
class Node{
private int no;
private String name;
private Node left;
private Node right;
public Node() {
}
public Node(int no, String name, Node left, Node right) {
this.no = no;
this.name = name;
this.left = left;
this.right = right;
}
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;
}
}
class BinaryTree{
private Node root;
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
| public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
Node node3 = new Node(3, "3", null, null);
Node node1 = new Node(1, "1", node3, null);
Node node2 = new Node(2, "2", null, null);
Node root = new Node(0, "0", node1, node2);
binaryTree.setRoot(root);
System.out.println(root.getLeft().getLeft().getName());
}
|
创建树的结构：
二叉树的遍历
二叉树的遍历分成前序，中序，后序和层次遍历。
前序，中序，后序遍历需要用到递归的思想；
而层次遍历，需要借助队列来实现；类似图的广度优先遍历算法
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
|
class Node{
private int no;
private String name;
private Node left;
private Node right;
public void preOrderNode(){
System.out.println("结点名字是" + this.getName() + ",值是" + this.getNo());
if(this.left != null){
this.left.preOrderNode();
}
if(this.right != null){
this.right.preOrderNode();
}
}
public void infixOrderNode(){
if(this.left != null){
this.left.infixOrderNode();
}
System.out.println("结点名字是" + this.getName() + ",值是" + this.getNo());
if (this.right != null){
this.right.infixOrderNode();
}
}
public void postOrderNode(){
if (this.left != null){
this.left.postOrderNode();
}
if (this.right != null){
this.right.postOrderNode();
}
System.out.println("结点名字是" + this.getName() + ",值是" + this.getNo());
}
}
|
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
| class BinaryTree{
private Node root;
public void preOrder(){
if(this.root != null){
this.root.preOrderNode();
}else{
System.out.println("二叉树为空");
}
}
public void infixOrder(){
if(this.root != null){
this.root.infixOrderNode();
}else{
System.out.println("二叉树为空");
}
}
public void postOrder(){
if(this.root != null){
this.root.postOrderNode();
}else{
System.out.println("二叉树为空");
}
}
public void LevelOrder(){
ArrayQueue<Node> queue = new ArrayQueue<Node>(10);
queue.add(root);
while(queue.size() != 0){
Node node = queue.remove(0);
System.out.println("结点名字是" + node.getName() + ",值是" + node.getNo());
if(node.getLeft() != null){
queue.add(node.getLeft());
}
if (node.getRight() != null){
queue.add(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
27
28
29
30
| public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
Node node3 = new Node(3, "3", null, null);
Node node1 = new Node(1, "1", node3, null);
Node node2 = new Node(2, "2", null, null);
Node root = new Node(0, "0", node1, node2);
binaryTree.setRoot(root);
binaryTree.preOrder();
System.out.println("********************************************************");
binaryTree.infixOrder();
System.out.println("********************************************************");
binaryTree.postOrder();
System.out.println("********************************************************");
binaryTree.LevelOrder();
}
|
结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 结点名字是0,值是0
结点名字是1,值是1
结点名字是3,值是3
结点名字是2,值是2
********************************************************
结点名字是3,值是3
结点名字是1,值是1
结点名字是0,值是0
结点名字是2,值是2
********************************************************
结点名字是3,值是3
结点名字是1,值是1
结点名字是2,值是2
结点名字是0,值是0
********************************************************
结点名字是0,值是0
结点名字是1,值是1
结点名字是2,值是2
结点名字是3,值是3
|