【数据结构】树_复习笔记总结
一、基本定义与性质
1. 基本定义
- 结点的度: 结点拥有的子树个数
- 树的度: 树内各结点度的最大值
- 叶子 / 终端结点: 度为0的结点
- 双亲和孩子: 结点的子树称为该结点的孩子,该结点叫做孩子的双亲
- 兄弟: 同一个双亲的孩子互称兄弟
- 祖先: 从根到该结点路径上的所有结点
- 子孙: 以某结点为根的子树中的任意结点
- 堂兄弟: 双亲在同一层的结点
- 层次: 根为第一层,孩子结点的层次等于双亲结点的层次加1
- 树的深度: 树中结点的最大层次数
- 森林: 互不相交的树的集合
二叉树的五种基本形态:
- 满二叉树: 深度为k,有2^k^ -1个结点
- 完全二叉树: 深度为k,有n个结点,每个结点编号都与深度为k的满二叉树中编号相同(说人话就是只有最后一层可能没放满,且从左到右不留空地放)
- 需要注意的是:二叉树不是树的特殊形态!二叉树不属于树!
2. 性质
- 性质1 在二叉树的第 i 层上至多有2 ^i-1^(i >= 1)个结点
- 性质2 深度为 k 的二叉树至多有2 ^k^ - 1(k>=1)个结点
- 性质3 对任何一颗二叉树T,如果其终端结点数为n~0~ ,度为2的结点数为n~2~ ,则n~0~ = n~2~ + 1
- 证明:设n~1~ 为度为1的结点个数,结点总数n = n~0~ + n~1~ + n~2~
设B为分支总数
除了根结点之外,每个结点都有一条分支进入,所以 n = B + 1
除了叶子结点的每个结点都会发出分支,所以 n = 2n~2~ + n~1~
所以有 n = n~1~ + 2n~2~ + 1
得 n~0~ = n~2~ + 1
- 证明:设n~1~ 为度为1的结点个数,结点总数n = n~0~ + n~1~ + n~2~
- 性质4 具有 n 个结点的完全二叉树深度为⌊log~2~ n⌋ + 1
- 性质5 如果对一棵有 n 个结点的完全二叉树按层序编号:
- 如果 i = 1,则结点 i 是二叉树的根
- 如果 2i > n,则结点 i 无左孩子,否则左孩子是结点 2i
- 如果 2i + 1 > n,则结点 i 无右孩子,否则右孩子是结点 2i + 1
二、存储、操作与算法
以下均以二叉树为例1. 二叉树的存储结构
(1) 顺序存储
这种存储结构仅适用于完全二叉树,因此我们大部分采用链式存储
typedef ElemType SqBiTree[MAXSIZE];
SqBiTree bt;(2) 链式存储
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;2. 遍历二叉树
由于考试范围里说不考非递归,复习时间紧,所以这个坑先放着啦,希望还记得来填上(1) 先序遍历 - 根左右
A. 递归算法
void InOrderTraverse(BiTree T)
{
if (T) // 若二叉树非空
{
cout << T->data;
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);
}
}(2) 中序遍历 - 左根右
A. 递归算法
void InOrderTraverse(BiTree T)
{
if (T) // 若二叉树非空
{
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
}(3) 后序遍历 - 左右根
A. 递归算法
void InOrderTraverse(BiTree T)
{
if (T) // 若二叉树非空
{
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);
cout << T->data;
}
}(4) 根据遍历序列确定二叉树
在二叉树的先序遍历、中序遍历、后序遍历中选两个确定二叉树,这两个中必须有一个是中序遍历
思路很简单啦就是根据先序遍历or后序遍历找到根,再在中序遍历中找到根的位置,在根前面的就是左子树,在根后面的就是右子树,然后返回先序遍历or后序遍历继续找两个子树的根,这样递归下去就能确定整个二叉树啦
还是因为考试原因留个代码的坑啦~(5) 计算二叉树的深度
思路: 分别递归计算一个结点左右子树的深度,这个结点的深度就是左右结点深度中较大的那个加1int Depth(BiTree T)
{
if (T == NULL) return 0;
else
{
m = Depth(T->lchild); // 递归计算左子树深度
n = Depth(T->rchild); // 递归计算右子树深度
if (m > n) return (m + 1);
else return (n + 1);
}
}(6) 计算二叉树结点的个数
思路: 空树返回0,不是空树就返回左子树个数加右子树个数加1int NodeCount(BiTree T)
{
if (T == NULL) return 0;
else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}3. 树和森林
(1) 树的存储结构
双亲表示法
每个结点存自身数值和双亲,求双亲和根很容易,但是求孩子很难孩子表示法
孩子数目多时,像单链表那样把孩子存起来孩子兄弟表示法
每个结点存自身数值、第一个孩子结点和下一个兄弟结点
在树的存储中应用较为普遍(2) 树(森林)与二叉树的转换
树转换成二叉树
- 在所有的兄弟结点之间加一条线
- 树中的每个结点只保留与第一个孩子的连线,删去其他的
- 调整整个树的结构,让兄弟转换一下变成右孩子
bingo~完成!二叉树转换成树
将二叉树左上到右下分层排列整齐
找到每层结点的父结点,加线
删掉兄弟之间的连线
完成~
二叉树转换成森林
- 从根节点开始,删去右孩子的连线
- 再看被删去的那一部分,继续删去右孩子的连线,直到全部删去为止
- 将得到的二叉树转换成树
4. 哈夫曼树(Huffman)
哈夫曼树又叫做最优树,是带权路径长度最短的树。
- 找到当前所有结点中最小的两个,将这两个结点作为兄弟,连在同一个双亲上,双亲的权值是两个结点权值之和
- 把这两个结点从点集中删去,把双亲结点加入点集
- 继续寻找目前点集中最小的两个,重复步骤12,直到点集中只剩下一个点
举个栗子
w = (5, 29, 7, 8, 14, 23, 3, 11) 构造哈夫曼树并计算带权路径长度
先在 w 里找到最小的两个点——3,5,然后构造:
现在点集变为 w = (8, 29, 7, 8, 14, 23, 11),找到最小的两个——7, 8,然后构造:
现在点集变为 w = (15, 29, 8, 14, 23, 11),找到最小的两个——8, 11,然后构造:
现在点集变为 w = (15, 29, 17, 14, 23),找到最小的两个——14, 15,然后构造:
现在点集变为 w = (29, 29, 17, 23),找到最小的两个——17, 23,然后构造:
现在点集变为 w = (29, 29, 40),找到最小的两个——29, 29,然后构造:
现在点集变为 w = (58, 40),找到最小的两个——40, 58,然后构造:
WPL = 8 x 3 + 11 x 3 + 23 x 2 + 29 x 2 + 14 x 3 + 7 x 4 + 3 x 5 + 5 x 5 = 271
(2) 算法实现
(挖坑~)
5. 哈夫曼编码
列出给定字母,字母出现的次数为权值,构造哈夫曼树
然后从根结点开始走,左0右1,得到的字串即为哈夫曼编码
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Texcavator 的秘密基地!
评论