数据结构-第三节-树与二叉树

一、基本概念：

树：一种非线性结构，除了根外，每个节点有一个前趋，可以有多个后继。

根与子树：上级是根，根引申出来的是子树（子树不是某一个节点）。

节点的度：节点子树的个数。

叶子/分支节点：度为/不为0的节点。

节点层次：根节点层定义为0，其后每往下层加一。

树的高度：树的最大层次。

树的度：在树中所有节点，度的最大值。

森林：多个树的集合。

有序与无序：子树是否有顺序。

二、二叉树：

度为小于等于2的有序树。

满二叉树：对于高度为k，所有层节点数均为最大。

完全二叉树：除了最后一层，节点数均为最大，且最下层节点都集中在该层的最左端。

二叉树的存储：节点类存两个指针，指向左节点与右节点。串 

三、树的存储：

对于树，从上到下，从左到右进行编号和存储。

1.顺序存储：

会对于缺节点的非完全树，会造成空间浪费。

2.链式存储：

双亲表示法：一个节点存有一个指针，指向双亲。

孩子表示法：一个节点存有一个指针，指向孩子的头结点（所有孩子存为链表）
                     所有节点的孩子头结点，组成一个顺序表。

孩子-兄弟表示法：一个节点存有两个指针，指向第一个孩子和下一个兄弟。（好！）

四、树与森林、二叉树的转换：

树的孩子-兄弟表示法，就是二叉树。

森林中，第二棵树，视为第一棵树的兄弟，也可化为二叉树。

五、二叉树的遍历：

递归算法：分为先序，中序，后序（以根为基准的先中后）

六、树的遍历：

1.深度优先遍历：

（1）先根次序遍历：根 -> 第一次子树 -> 第二棵子树。。。

（2）后根次序遍历：第一次子树 -> 第二棵子树。。。 ->根 

2.广度优先遍历：

按层遍历：从左到右遍历完一层，再进入下一层。

七、二叉排序树：

左子树中所有节点值，小于根节点值。

右子树中所有节点值，大于根节点值。

1.查找：小的往左找，大的往右找

2.插入：查找到最后，插入在那里。

注：对二叉树进行中序遍历，得到有序序列。

3.删除：

（1）只有叶子节点：直接删

（2）只有左子树/右子树：下一节点接在自己位置。

（3）左右子树都有：（复杂）

中序遍历，用左/右子树中序遍历最后一个节点，代替自己，并删除那最后一个节点。

八、最优二叉树：霍夫曼编码

详见信息论。