二叉树

二叉树是N个节点的有限集合,该集合或者为空集称为二叉树,或者由一个根节点和两课互不相交的.分别称为根节点的左子树和右子树的二叉树组成.
二叉树的特点:
1.每个节点最多有两课子树,故二叉树中的节点最大为2,也可以没有或者为1



2.左子树和右子树是有顺序的,次序不能任意颠倒.
3.即使某一结点只有一颗树,也会区分左子树和右子树
故如果有三个结点的二叉树共有五种形态





斜树:所有的结点都只有二叉树叫做左斜树,所有节点只有右二叉树叫做右斜树


满二叉树:就是所有的节点都有两个子树,并且所有的叶子都在同一层上

二叉树的性质:
1.在二叉树的第i层有最多2的(n-1)次方个结点
2.深度为i的二叉树最多有2的(n-1)次方个结点
3.对于任意一颗二叉树,其终端结点数为n,度为2 的节点数为m,则 n = m +1
4.具有n个节点的完全二叉树的深度为log以2为低的n次方的值加1(通过n = 2的k次方的值减1来推到,第二个性质)
5.如果对一棵树有n个结点的完全二叉树的结点按照层序编号,对于任一结点i有:
(1):i = 1,则结点i是二叉树的根,无双亲,其双亲是结点i/2:
(2):2i>n,结点i污孩子,负责其做孩子是结点2i
(3):2i+1>n,则结点i无孩子,否则其右孩子是结点2i + 1
参考于大话设计模式

若有差错,还望指正,共勉