孩子兄弟表示法:
能够表示任意的属性结构每个结点中有且仅有三个指针域
数据指针、孩子结点指针、兄弟结点指针每个结点的结构简单
只有孩子结点指针和兄弟结点指针构成了“树杈”
二叉树是最多只有两个孩子的树
定义:
二叉树是由n(n >= 0)个结点组成的有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成
满二叉树:
二叉树中所有分支结点的度数都是2,且叶结点都在同一个层次上
完全二叉树:
一棵n个结点的高度为k的二叉树,它的每一个结点都与高度为k的满二叉树编号为1到n的结点一一对应
叶结点仅出现在最下面两层;最下层的叶节点一定出现在左边倒数第二层的叶结点一定出现在右边度为1 的结点只有左孩子
性质:
在二叉树的第i层最多有2的(i-1)次方个结点
深度为k的二叉树最多有2的k次方减一个结点
对任何一棵二叉树,如果叶结点有n0个,度为2的非叶结点有n2个,则有n0=n2+1;
具有n个结点的完全二叉树的高度为[log2 (n)]+1.
一棵有n个结点的二叉树(高度为[log2 (n)]+1),按层次对结点进行编号(从上到下,从左到右),对任意结点i有:
如果i =1,则结点i是二叉树的根如果i >1,则其双亲结点为[i/2]如果2i <=n,则结点i的左孩子为2i如果2i >1,则结点i无左孩子如果2i+1<=n,则结点i的右孩子为2i+1如果2i+1 >n,则结点i无右孩子