数据结构—树和二叉树

树：

度：多少个叉，针对的是结点

深度：一共多少层，针对的是整棵树

A的度为3，B的度为2

这棵树的深度为：4

树只有一个根

 

二叉树

完全二叉树是路径长度最短的二叉树

特点：每个结点下面最多有两棵叉，子树有左右之分，其次序不能任意颠倒

性质：

:性质1：第i层上最多有个结点（i大于等于1）

:性质2：深度为k的二叉树最多有个结点，

性质3：终端节点数为n。，度为2的结点数为n2，则n。=n2+1

性质4：具有n个结点的完全二叉树的深度为（取整数部分的数即为深度）

性质5：n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），则对任一结点i(1小于等于i小于等于n)，有

（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点i/2.

（2）如果2i>n，则结点i无左孩子（结点i为叶子节点）；否则其做孩子是结点2i

（3）如果2i+1>n,则结点i无右孩子。否则其右孩子是结点2i+1

 

遍历二叉树

先序：根左右

中序：左根右

后序：左右根

 

普通树的3种存储方法：

1.双亲表示法——线性存储（数组）

2.孩子表示法——顺序表+链表

3.孩子兄弟表示法——链表

规则为树的右兄弟为右孩子

树和森林

森林：多个树之间没有关系的称为森林

1.树转换成二叉树（右兄弟为右孩子）

 

2.森林转换成二叉树（右兄弟为右孩子）

反过来将二叉树转成树，二叉树转成森林可以根据右孩子为右兄弟可以转换

森林也可以根据先续、中序、后序进行遍历

例如上述的森林

先序：ABCDEFGHIJ

中序：CDAFEHJIG

 

树与等价问题

规则：两个集合做并集，只要将一棵子集树的根指向另一棵子集树的根即可

并假设每次都是含成员多的根结点指向含成员少的根结点