为什么需要树这种结构
数组和链式存储都有各自的优缺点，数组查找效率高，增删效率低，链式存储查找效率低，增删效率高。树可以提高数据存储、读取的效率，比如二叉排序树，既可以保证数据的查找速度，也可以保证数据的插入、删除、修改速度。
树的相关术语
- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点：没有子节点的节点
- 节点的权：节点的值
- 路径：从root节点找到该节点的路线
- 层
- 子树
- 树的高度：最大层数
- 森林：多颗子树构成森林
二叉树概念
- 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
- 二叉树的子节点分为左节点和右节点
- 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
- 如果一棵具有n个结点的二叉树与满二叉树的前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
|
package com.eh.ftd.dsa.ds;
/**
* 二叉树
*
* @author David Li
* @create 2020/06/27 14:27
*/
public class BinaryTree {
/**
* 定义节点
*
* @param <T>
*/
static class Node<T> {
T data;
Node left;
Node right;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
/**
* 初始化一个二叉树,如图1所示
*
* @return
*/
static Node init() {
Node<Integer> n1 = new Node(1);
Node<Integer> n2 = new Node(2);
Node<Integer> n3 = new Node(3);
Node<Integer> n4 = new Node(4);
Node<Integer> n5 = new Node(5);
Node<Integer> n6 = new Node(6);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.right = n6;
return n1;
}
/**
* 前序遍历
*
* @param node
*/
static void preOrder(Node node) {
// 1. 输出当前节点
System.out.print(node + " ");
// 2. 如果左节点不为空则遍历左子树
if (node.left != null) {
preOrder(node.left);
}
// 3. 如果右节点不为空则遍历右子树
if (node.right != null) {
preOrder(node.right);
}
}
/**
* 中序遍历
*
* @param node
*/
static void inOrder(Node node) {
// 1. 如果左节点不为空则遍历左子树
if (node.left != null) {
inOrder(node.left);
}
// 2. 输出当前节点
System.out.print(node + " ");
// 3. 如果右节点不为空则遍历右子树
if (node.right != null) {
inOrder(node.right);
}
}
/**
* 后序遍历
*
* @param node
*/
static void postOrder(Node node) {
// 1. 如果左节点不为空则遍历左子树
if (node.left != null) {
postOrder(node.left);
}
// 2. 如果右节点不为空则遍历右子树
if (node.right != null) {
postOrder(node.right);
}
// 3. 输出当前节点
System.out.print(node + " ");
}
public static void main(String[] args) {
inOrder(init());
}
}
|
