Quartz 5

第五章 二叉树

Properties1
tags基础知识, 数据结构

3 min read

5.2 二叉树的概念

基础概念

相关提炼内容见 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 个空链域

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

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

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

Graph View

Backlinks