浏览 185
分享
二叉树的基本概念
二叉树的定义
树形结构是一种非线性结构,二叉树是度为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;
评论列表