二叉树的基本概念

二叉树的定义

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

完全二叉树

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

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

树的基本术语

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

二叉树的性质

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

二叉树的基本运算

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

二叉树的存储结构

顺序存储结构

  1. typedef ElemType SqBinTree[MaxSize]

链式存储结构

  1. #define MaxSize 100
  2. #define MaxWidth 40
  3. typedef char ElemType;
  4. typedef struct tnode
  5. {
  6. ElemType data;
  7. struct tnode *lchild,*rchild;
  8. } BTNode;