数称为节点的度树中节点的最大度数称为树的度度大于0的节点称为分支节点度等于0的节点称为叶节点定义树根为第一层则树的深度高度为5二叉树定义树中的每个节点至多有两个孩子则该树被称为二叉树。

特殊的二叉树满二叉树高度为h的二叉树有2^h-1个节点则为满二叉树。

完全二叉树高度为h的树中每个节点都能与高度为h的满二叉树中的节点对应则该树为完全二叉树。

二叉排序树二叉搜索树左子树上的所有节点的关键字都小于根节点右子树上的所有节点的关键字都大于根节点的关键字且左子树和右子树也各为二叉排序树。

平衡二叉树树上任意一个节点的左子树深度和右子树深度相差不超过1。

二叉树的性质对于非空二叉树其分支数等于节点数-1一般树也是这样。

对于非空二叉树其叶节点数等于度为2的节点数加1。

证明设树中度为0,1,2的节点为n0,n1,n2树中分支总数为B可知Bn2*2n1又因为Bn0n1n2-1,所以n0n21;对于完全二叉树假设有n个节点对于编号大于n/2的都是叶子节点。

二叉树的表示对于链式存储结构我们用结构体来存储二叉树的每个节点每个节点保存该节点的数据以及左右孩子的指针。

代码如下typedef

struct

}BiTNode;二叉树的遍历二叉树有三种遍历方式如下先序前序遍历按照

根-左-右

的方式即先输出根再递归处理左边再递归处理右边。

代码如下void

get(BiTree

T){if(T!NULL){visit(T);//访问根get(T-lchild);//递归处理左边get(T-rclild);//递归处理右边}

}中序遍历按照

左-右-根的顺序。

由遍历序列还原二叉树根据二叉树的前序、后序和二叉树的中序遍历组合便可唯一的还原出二叉树。

由前序和中序还原已知前序遍历的第一个元素为树的根节点R我们在中序遍历中找出R则R的左边为左子树右边为右子树由左子树和右子树的节点数量我们也可以在前序遍历序列中找到左子树和右子树最后递归处理左右子树即可。