淘先锋技术网

首页 1 2 3 4 5 6 7

树:

度:多少个叉,针对的是结点

深度:一共多少层,针对的是整棵树

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

 

树与等价问题

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

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