二叉树的性质以及满二叉树,完全二叉树
性质一:在二叉树的第i层,最多有2的(i-1)次方个结点i>.=1
性质二:深度为k的二叉树上最多有含有2的k次方-1个结点
k>=1
性质三:对于任何一个二叉树,若它含有n0个叶子结点,n2个度为2的结点,则必存在关系式:n0=n2+1
满二叉树:指的是深度为k且含有2的k次方-1个结点的二叉树。即每一层都是最多节点数
完全二叉树:树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。(顺序是从上到下,从左到右进行编号,然后一一对应)按照顺序形成的树
性质四:
具有n个结点的完全二叉树的深度为
向下取整+1
性质五:
针对完全二叉树,顺序是从上到下,从左到右进行编号1至n,则对二叉树中任意一个编号为i的结点:
(1)若 i=1 ,则该结点为二叉树的根 无双亲。 否则编号为[i/2]向下取整的结点为其双亲节点。
(2)若2i>n,则该节点无左孩子,否则编号为2i的结点为其右孩子。
(3)若2i+1>n,则该节点无右孩子,否则编号为2i+1的结点为其右孩子。