数据结构笔记—树和二叉树

树和二叉树

定义

树是n个结点的有限集

基本术语

1
2
3
4
5
6
7
            A
/ | \
B C D
/ \ | / | \
E F G H I J
/ \ |
K L M
  • 根:即根结点(没有前驱)
  • 叶子:即终端结点(没有后继)
  • 森林:指m棵不相交的树的集合(例如删除A后的子树个数)
  • 有序树:结点各子树从左至右有序,不能互换(左为第一)
  • 无序树:结点各子树可互换位置
  • 双亲:即上层的那个结点(直接前驱)
  • 孩子:即下层结点的子树的根(直接后继)
  • 兄弟:同一双亲下的同层结点(孩子之间互称兄弟)
  • 堂兄弟:即双亲位于同一层的结点(但并非同一双亲)
  • 祖先:即从根到该结点所经分支的所有结点
  • 子孙:即该结点下层子树中的任一结点
  • 结点:即树的数据元素
  • 结点的度:结点拥有的子树数
  • 结点的层次:从根到该结点的层数(根结点算第一层)
  • 终端结点:即度为0的结点,即叶子
  • 分支结点:即度不为0的结点(也称为内部结点)
  • 树的度:所有结点度中的最大值
  • 树的深度(或高度):指所有结点中最大的层数

树的实现

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
    构造如下的树

1
/ \
2 3
/|\ | \
4 5 6 10 11
/|\ / | \
7 8 9 12 13 14


/// 树的结点定义
public class TreeNode<T> {

public var value:T

public weak var parent:TreeNode? // 父节点 只有一个

public var children = [TreeNode<T>]()// 有多个

init(value:T) {
self.value = value
}

public func addChild(_ node:TreeNode<T>) {
children.append(node)
node.parent = self
}


}

extension TreeNode: CustomStringConvertible {
public var description: String {
var s = "\(value)"
if !children.isEmpty {
s += " {" + children.map {
$0.description
}.joined(separator: ", ") + "}"
}
return s
}
}


extension TreeNode where T:Equatable {
//搜索
public func search(_ value:T) ->TreeNode? {
if value == self.value {
return self
}
for child in children {
if let found = child.search(value) {
return found
}
}
return nil
}
}

二叉树

二叉树基本特点:
结点的度小于等于2
有序树(子树有序,不能颠倒)

二叉树的性质

  1. 在二叉树的第i层上至多有2i-1个结点,至少有1个结点
  2. 深度为k的二叉树至多有2k-1个结点,至少有 k 个结点
  3. 对于任何一棵二叉树,若2度的结点数有n2个,则叶子数n0必定为n2+1 (即n0=n2+1)
  4. 性质4: 具有n个结点的完全二叉树的深度必为log2n+1 (log2n向下取整)
  5. 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2 (i/2向下取整)。
特殊形态的二叉树
  1. 满二叉树:一棵深度为k 且有2k -1个结点的二叉树。(特点:每层都“充满”了结点)

满二叉树

2.完全二叉树:深度为k 的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应

完全二叉树

满二叉树和完全二叉树的区别

 满二叉树是叶子一个也不少的树,而完全二叉树虽然前n-1层是满的,但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。

  • 注意:从存储形式来讲适合顺序存储。如果其他形式的二叉树用顺序存储结点间关系蕴含在其存储位置中必将浪费空间

二叉树的实现

定义结点

1
2
3
4
5
6
public indirect enum BinaryTree<T> {
//左子树 / 值 / 右子树
case node(BinaryTree<T>,T,BinaryTree<T>)
case empty

}

求结点数

1
2
3
4
5
6
7
8
9
//计算结点数
public var count: Int {
switch self {
case let .node(left, _, right):
return left.count + 1 + right.count //递归
case .empty:
return 0
}
}

二叉树构造过程

 构造二叉树

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

1
/ \
2 3
/ \ /
4 5 6


//二叉树的构造过程
先从叶子结点开始

let node5 = BinaryTree.node(.empty, "5", .empty)
let node6 = BinaryTree.node(.empty, "6", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)

let node2 = BinaryTree.node(node4, "2", node5)
let node3 = BinaryTree.node(node6, "3", .empty)
let node1 = BinaryTree.node(node2, "1", node3)


print(node1)

结果:
value: 1, left = [value: 2, left = [value: 4, left = [], right = []], right = [value: 5, left = [], right = []]], right = [value: 3, left = [value: 6, left = [], right = []], right = []]

print(node1.count)
结果: 6

遍历二叉树和线索二叉树

遍历二叉树

 遍历定义——指按某条搜索路线遍访每个结点且不重复(又称周游)。

 遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。

遍历规则

  1. DLR—先序遍历,即先根再左再右
  2. LDR—中序遍历,即先左再根再右
  3. LRD—后序遍历,即先左再右再根

如下:

1
2
3
4
5
6
7
8
9
10
11
          A
/ \
B C
/ \
D E

先序遍历:A B D E C

中序遍历:D B E A C

后序遍历:D E B C A

代码实现

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
/*
DLR—先序遍历,即先根再左再右
LDR—中序遍历,即先左再根再右
LRD—后序遍历,即先左再右再根


//先序遍历
func traverseDLR(process:(T)->Void) {
if case let .node(left, value, right) = self{
process(value)
left.traverseDLR(process: process)
right.traverseDLR(process: process)
}
}

//中序遍历
func traverseLDR(process:(T)->Void) {
if case let .node(left, value, right) = self{
left.traverseLDR(process: process)
process(value)
right.traverseLDR(process: process)
}
}
// 后续遍历

func traverseLRD(process:(T)->Void) {
if case let .node(left, value, right) = self{
left.traverseLRD(process: process)
right.traverseLRD(process: process)
process(value)
}
}


1
/ \
2 3
/ \ /
4 5 6

以遍历此树为例:

//先序遍历
var s1 = ""
tree.traverseDLR { (value) in
s1 += " -> " + "\(value)"
print(s1)
}

遍历过程打印:
-> 1
-> 1 -> 2
-> 1 -> 2 -> 4
-> 1 -> 2 -> 4 -> 5
-> 1 -> 2 -> 4 -> 5 -> 3
-> 1 -> 2 -> 4 -> 5 -> 3 -> 6

//中序
var s2 = ""
node1.traverseLDR { (value) in
s2 += " -> " + "\(value)"
print(s2)
}

遍历过程打印:
-> 4
-> 4 -> 2
-> 4 -> 2 -> 5
-> 4 -> 2 -> 5 -> 1
-> 4 -> 2 -> 5 -> 1 -> 6
-> 4 -> 2 -> 5 -> 1 -> 6 -> 3

//后序遍历
var s3 = ""
node1.traverseLRD { (value) in
s3 += " -> " + "\(value)"
print(s3)
}

遍历过程打印:
-> 4
-> 4 -> 5
-> 4 -> 5 -> 2
-> 4 -> 5 -> 2 -> 6
-> 4 -> 5 -> 2 -> 6 -> 3
-> 4 -> 5 -> 2 -> 6 -> 3 -> 1

遍历算法的分析

 从递归的角度看,三种算法是完全相同的,或说这三种算法的访问路径是相同的,只是访问结点的时机不同。

时间效率:O(n) //每个结点只访问一次

空间效率:O(n) //栈占用的最大辅助空间

线索二叉树

 普通二叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得
若将遍历后对应的有关前驱和后继预存起来,则从第一个结点(++可能是根、或最左(右)叶子++)开始就能很快“顺藤摸瓜”而遍历整个树

 例如中序遍历结果:B D C E A F H G,实际上已将二叉树转为线性排列,显然具有唯一前驱和唯一后继!

术语

  • 线索:指向结点前驱和后继的指针
  • 线索链表:加上线索二叉链表
  • 线索二叉树:加上线索的二叉树(图形式样)
  • 线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程

线索化规则

  1. 若结点有左子树,则lchild指向其左孩子;否则, lchild指向其直接前驱(即线索);
  2. 若结点有右子树,则rchild指向其右孩子;否则, rchild指向其直接后继(即线索) 。

代码实现

霍夫曼树

术语

1
2
3
4
5
      A
/ \
B C
/ \ / \
D E F G
  • 路径:由一结点到另一结点间的分支所构成- 路径长度:路径上的分支数目。 如:A→E 的路径长度=2

  • 带权路径长度:结点到根的路径长度与结点上权的乘积

  • 树的带权路径长度:树中所有叶子结点的带权路径长度之和
  • ==霍夫曼树==:带权路径长度最小的树

霍夫曼树的构造过程

基本思想:使权大的结点靠近根

操作要点:对权值的合并、删除与替换,总是合并当前值最小的两个

  1. 根据给定的n个权值{w1,w2,……wn},构造n棵只有根结点的二叉树。
  2. 在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和。
  3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中。
  4. 重复上述两步,直到只含一棵树为止,这棵树即霍夫曼树。

算法实现

坚持原创,您的支持将鼓励我继续创作!