二叉树的基本概念

二叉树的定义

树形结构是一种非线性结构，二叉树是度为2，即子结点的个数最多为2的有序树（左右子树是有次序的）。最重要，应用最广泛的一种树。

完全二叉树

在一个二叉树中，除了最后一层外，其余的其他层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则该树称为完全二叉树。

满二叉树是一种特殊的完全二叉树，即所有的层的结点都是满的。

树的基本术语

• 结点的度：该节点的后继节点的个数
• 树的度：所有节点的度的最大值
• 分支结点
• 叶子结点
• 孩子结点
• 双亲结点
• 子孙结点
• 祖先结点
• 兄弟结点
• 结点层数
• 树的深度（高度）：树中结点的最大的层数
• 有序树：左右子树是有次序的
• 无序树：左右子树是无次序的
• 森林：不同树的集合

二叉树的性质

• 二叉树上叶子节点的个数等于度为2的结点的个数加1
• 二叉树上第i层上至多有2^(i-1)个结点（i>1）
• 深度为h的二叉树至多有2^h-1个结点

二叉树的基本运算

• 创建二叉树
• 求二叉树的高度
• 求二叉树结点的个数
• 求二叉树叶子结点的个数
• 用括号表示法输出二叉树
• 用凹入表示法输出二叉树

二叉树的存储结构

顺序存储结构

typedef ElemType SqBinTree[MaxSize]

链式存储结构

#define MaxSize 100
#define MaxWidth 40
typedef char ElemType;
typedef struct tnode
{
    ElemType data;
    struct tnode *lchild,*rchild;
} BTNode;