数据结构与算法分析(二)树

预备知识

graph TB
A((A))
B((B))
C((C))
D((D))
E((E))
F((F))
G((G))
H((H))
I((I))
J((J))
K((K))
L((L))
M((M))
N((N))
P((P))
Q((Q))
A---B
A---C
A---D
A---E
A---F
A---G
D---H
E---I
E---J
F---K
F---L
F---M
G---N
J---P
J---Q

一棵树是N个节点和N-1条边的集合

没有子节点的节点称为叶节点

两节点之间路径的长为该路径上边的条数

任意节点的深度为根节点到该节点路径的长

任意节点的高为该节点到一个叶结点的最长路径的长

数的实现

一般使用一个链表存储子节点

下图为上图的兄弟表示法

树的遍历及应用

先序遍历

考察到一个节点后，即刻输出该节点的值，并继续遍历其左右子树。(根左右)

中序遍历

考察到一个节点后，将其暂存，遍历完左子树后，再输出该节点的值，然后遍历右子树。(左根右)

后序遍历

考察到一个节点后，将其暂存，遍历完左右子树后，再输出该节点的值。(左右根)

二叉树

二叉树(binary tree)是一棵树，其中每个节点都不能有多于两个的子节点。

二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小得多。其平均深度为$O(\sqrt{N})$，而对于特殊类型的二叉树，即二叉查找树(binary search tree)，其深度的平均值为$O(\log N)$

实现

因为一个二叉树节点最多有两个子节点，所以我们可以保存直接链接到它们的链

表达式树

查找树ADT——二叉查找树

性质：对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项

平均深度：$O(\log N)$