数据结构-树-选择题专题总结

【持续更新ing】

一、各种树和它的别名

  • 吐槽：这些题目，没事干，取这么多名字干嘛。

0）二元树——二叉树
1）二叉排序树——排序二叉树——二叉查找树——二元查找树
2）最优二叉树——哈弗曼树（一般指哈弗曼二叉树）-霍夫曼树
二元查找树=二叉查找树=二叉搜索树=BST=binery search tree=binery sort tree

  • 我们做招聘+考研，都是认为哈弗曼树是二叉树（但是有论文表明，霍夫曼树也有多叉的）

3）单支树指的是只有一个孩子并且方向一致
4）二叉树的节点的对称序列（中序序列）

二、选择题常考知识点

（1）树的节点和边的关系（常考）

从<stron>和线，两个角度考虑，这种做法真的不错，可以成为方法论</stron>

设二叉树的叶子节点为n0，度为1的节点为n1，度为2的节点为n2.则n0 = n2 + 1。

证明（这才是重点）：

一、节点关系的方程

设二叉树的总节点数为n。
则n = n0 + n1 + n2（式1）

二、边关系的方程

左边：
从二叉树每个节点的线来看，除了根节点，每个节点都有一条线（从下往上看，配图如下），所以线的总数为n-1。
图片说明

右边：
而每个度为2的节点则放出两条线，度为1的节点放出一条线，叶子节点则没有放出线（从上往下看，配图如下）。
图片说明
所以：n-1 = 2*n2 + n1 （式2）

最后，由第二条公式减去第一条公式得：n0 = n2 + 1。
显然，这个方法可以推广到多叉树

（2）等比数列求和

看题目规定第一层叫第0层还是第1层
求Sn-1=20+21+22+...2n
也有可能是
求Sn=20+21+22+...2n

三、一些潜在的规定？

1）二叉排序树

大小似乎在招聘+考研默认：

  • 左 <= 根 <= 右
    （左小右大）

四、做题方法

  • 做这些题目，无非就是要考虑完全，单枝树，完全二叉树等各种各样的情况，然后就是要耐心去推导公式。（心静）

树的存储结构包括: 顺序，链式(二叉链表，三叉链表)，(双亲，孩子，孩子兄弟)表示法。