跳到主要内容

5.2 二叉树的概念

[!info] 基础概念 相关提炼内容见 binary-tree。

二叉树的定义​

每个结点至多只有两棵子树，且子树有左右之分

几个特殊的二叉树​

满二叉树：假设高度为 3，那么满二叉树的结点数就是（1+2+4=7）7 个，每层都是满的

     1
    / \
   2   3     <== 这就是满二叉树
  / \ / \
 4  5 6  7

完全二叉树：其实就是满二叉树删除最后 x 个结点，比如一颗完全二叉树的高度是 3，下图都是完全二叉树

     1           1           1
    / \         / \         / \
   2   3       2   3       2   3
  / \ /       / \         /
 4  5 6      4  5        4

二叉排序树：对于任何一个结点，左子树比它小，右子树比它大

     5           5             5
    /           / \           / \
   3           3   7         3   7   ......好多好多
  /           /     \       /   /
 1           1       10    1   6

平衡二叉树：可以理解为更加严格的二叉排序树

     5       👈这是二叉排序树😋                3
    /        但不是平衡二叉树                  / \
   3         你可以理解为左轻右重             1   5
  /          很不美观，调整后👉
 1

关于平衡二叉树其实有更加严格的定义，请自行查阅

二叉树的性质​

TODO 之前的笔记晦涩难懂，要重新写一下

二叉树的存储结构​

  • 顺序存储结构
    • 完全二叉树和满二叉树采用顺序存储比较合适
    • 对于一般的二叉树，需要添加并不存在的空结点
    • 结点类型定义
#define MAXSIZE 100
typedef TElemType SqBiTree[MAXSIZE];
SqBiTree bt;
  • 链式存储结构

二叉链表

二叉链表的结点类型定义

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;

思考：在含有 n 个结点的二叉链表中，含有多少个空链域？?→n+1 个空链域

{1n0+1n1+1n2=n结点数之和0n0+1n1+2n2=n−1度和结点关系2n0+1n1+0n2=?求空链域\begin{cases} 1n_0+1n_1+1n_2=n&结点数之和\\ 0n_0+1n_1+2n_2=n-1&度和结点关系\\ 2n_0+1n_1+0n_2=?&求空链域\\ \end{cases}

再来看看三叉链表，它的结点类型定义如下

typedef struct TriNode{
  TElemType data;
  struct TriNode *lchild,*rchild,*parent;
}TriNode, *TriTree;

看着很吓人，其实仔细阅读并不难