数据结构—树和二叉树
树:
度:多少个叉,针对的是结点
深度:一共多少层,针对的是整棵树
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
树与等价问题
规则:两个集合做并集,只要将一棵子集树的根指向另一棵子集树的根即可
并假设每次都是含成员多的根结点指向含成员少的根结点