算法与数据结构 --- 二叉树的性质和存储结构

第一部分 --- 二叉树的性质

 

 

 

 

 1.从下往上看我们可以发现，每多一个结点，除了增加的是树的根结点时总边数不变，增加其它的结点都会导致总边数 + 1，设总结点为n，则我们就会有左边那个求总边数的公式

2.从上往下看，我们会发现每增加一个度数为2的结点则增加总边数 +2，增加一个度数为1的结点则总边数 + 1，设度数为2的结点总数为n2，度数为1的结点总数为n1，则我们就有右边那个求总边数的公式

3.结合上面我们得到的公式和总结点数 n = n0 + n1 + n2（n0是叶子的总数 --- 度数为0的结点），我们就能够解出上面这个性质了

 

 1.满二叉树就是具有最大结点数的二叉树（二叉树具有最大结点数的充要条件就是二叉树的所有内部节点都是度数为2的结点）

1.完全二叉树是满二叉树的子集（具有特定限制的子集 --- 元素按照编号一一对应的关系，不用相等但是能够对应的上）

 

1.完全二叉树其实就是满二叉树按照编号顺序从大到小连续的删除结点得到的结果

（如果不删除结点的话，满二叉树本身也符合完全二叉树的定义，所以满二叉树也是完全二叉树）

2.第二个特点的出现原因是：满二叉树是按照编号从大到小连续的删除结点，所以这就相当于从右向左删除元素

 

 

---

第二部分 --- 二叉树的存储结构

 

1.binary : adj 二分的

1.对于非完全二叉树我们也要按照完全二叉树的方式给所有结点编号，如果出现了结点缺失的话，我们也要给缺失的结点编上号，存储到顺序表的时候如果对应编号有结点的话那就存这个结点的数据，如果没结点的话那就存个0

 

1.顺序存储法对于满二叉树核完全二叉树是最使适用的，存储它们时数组的密度为1

1.在二叉链表中每个结点有一个数据和两个指针域，数据域是用来存储结点本身的数据的，两个指针域分别指向结点的左孩子和右孩子

1.二叉链表中的头指针指向根结点，二叉链表中没有头结点

 

1.假设当前具有n个结点的二叉链表中没有空指针域，也就是说这种假设下的链域（结点与结点之间的连线）为 2n ，而实际上具有n个结点的二叉树的总链域树等于 n - 1

则 2n - ( n - 1 ) 就能够得到我们假想出来的，但实际却没有的链域（空指针）

1.三叉链表：链表中的结点多了一个指针域，这个指针域指向结点的双亲