数据结构

大话数据结构：二叉树

Posted by Viletyy on 2020-06-17 10:01

二叉树

比如开和关、0和1、真和假、上和下、对与错，正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。

二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

  • 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。注意不是只有两棵子树，而是最多有，没有子树或者有一棵子树都是可以的。
  • 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有五种基本形态：

  1. 空二叉树。
  2. 只有一个根结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

特殊二叉树

斜树

所有的结点都是只有左子树的二叉树叫左斜树。

所有的结点都是只有右子树的二叉树叫右斜树。

这两种统称为斜树。

斜树有明显的特点，就是每一层只有一个结点，结点的个数与二叉树的深度相同

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

满二叉树的特点：

  1. 叶子只能出现在最下层。出现在其他层就不能达成平衡
  2. 非叶子结点的度一定是2.否则就是“缺胳膊少腿”了。
  3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为 i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

完全二叉树的特点：

  1. 叶子结点 只能出现在最下两层
  2. 最下层的叶子一定集中在左部连续位置
  3. 倒数二层，若有叶子结点，一定都在右部连续位置
  4. 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
  5. 同样结点树的二叉树，完全二叉树的深度最小。

二叉树的性质

  • 二叉树性质1:在二叉树的第i层上至多有2^(i-1)个结点（i>=1)

  • 二叉树性质2:深度为k的二叉树至多有2^k-1个结点（k>=1）
  • 二叉树性质3:对任何一棵二叉树T，如果其终端结点数为n0，度为2的的结点数为n2，则n0 = n2 + 1
  • 二叉树性质4:具有n个结点的完全二叉树的深度为[log2^n]=1()([x]表示不大于x的最大整数)
  • 二叉树性质5:如果对一棵有n个结点的完全二叉树（其深度为[log2^n]+1）的结点按层序编号（从第1层到第[log2^n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：
    1. 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
    2. 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i；
    3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

二叉树的存储结构

顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲和孩子的关系，左右兄弟的关系等。

二叉链表

二叉树莓哥结点最多有两个孩子，座椅为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

二叉链表的结点结构定义代码：

1
2
3
4
5
6

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode /* 结点结构 */
{
  TElemType data; /* 结点数据 */
  struct BiTNode *lchild, *rchild; /* 左右孩子指针 */
} BiTNode, *BiTree;

遍历二叉树

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

image-20210810111018807

前序遍历算法：

1
2
3
4
5
6
7
8
9

/* 二叉树的前序遍历递归算法 */
void PreOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  printf("%c", T->data); /* 显示结点数据，可以更改为其他对结点操作 */
  PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
  PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。

image-20210810111029162

1
2
3
4
5
6
7
8
9

/*二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  InOrderTraverse(T->lchild); /*中序遍历左子树*/
  printf("%c", T->data); /* 显示结点数据，可以更改为其他对结点操作 */
  InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

image-20210810111159592

1
2
3
4
5
6
7
8
9

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
  if(T==NULL)
    return;
  PostOrderTraverse(T->lchild); /* 先后续遍历左子树 */
  PostOrderTraverse(T->rchild); /* 再后续遍历右子树 */
  printf("%c", T->data); /* 显示结点数据，可以更改为其他对结点操作 */
}

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

image-20210810111311617

推导遍历结果

已知前序和后序遍历，是不能确定一棵二叉树的。

二叉树的建立

按照前序输入二叉树中结点的值，算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/* 按前序输入二叉树中结点的值（一个字符）*/
/* #表示空树，构造二叉链表表示二叉树T */
void CreateBiTree(BiTree *T) 
{
  TElemType ch;
  scanf("%c", &ch);
  if (ch == '#')
    	*T=NULL;
  else  
  {
    *T=(BiTree)malloc(size(BiTNode));
    if(!*T)
      exit(OVERFLOW);
    (*T)->data=ch; /* 生成根结点 */
    CreateBiTree(&(*T)->lchild); /* 构造左子树 */
    CreateBiTree(&(*T)->rchild); /* 构造右子树 */
  }
}

线索二叉树

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）

对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化

  • ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
  • rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

线索二叉树结构实现

二叉树的线索存储结构定义代码如下：

1
2
3
4
5
6
7
8
9
10

/* 二叉树的二叉线索存储结构定义 */
typedef enum {Link, Thread} PointerTag; /* Link==0 表示指向左右孩子指针 */
/* Thread==1 表示指向前驱或后继的线索 */
typedef struct BiThrNode /* 二叉线索存储结点结构 */
{
  TElemType data; /* 结点数据 */
  struct BiThrNode *lchild, *rchild; /* 左右孩子指针 */
  PointerTag LTag;
  PointerTag RTag; /* 左右标志 */
} BiThrNode, *BiThrTree;

线索化的过程就是在遍历的过程中修改空指针的过程

中序遍历线索化的递归函数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p) 
{
  if(p)
  {
    InThreading(p->lchild); /* 递归左子树线索化 */
    if(!p->lchild){
      p->LTag=Thread; /* 前驱线索 */
      p->lchild=pre; /* 左孩子指针指向前驱 */
    }
    if(!pre->rchild){
      pre->RTag=Tread; /* 后继线索 */
      pre->rchild=p; /* 前驱有孩子指针指向后继（当前结点p）*/
    }
    pre=p; /* 保持pre指向p的前驱 */
    InThreading(p->rchild); /* 递归右子树线索化 */
  }
}

中序遍历的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。中序遍历二叉线索链表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
  BiThrTree p; 
  p = T->lchild; /* p指向根结点 */
  while (p != T)
  {
    while (p->LTag==Link) /*当LTag==0时循环到中序序列第一个结点*/
      p = p->lchild;
    printf("%c", p->data); /*显示结点数据，可以更改为其他对结点操作*/
    while(p->RTag==Thread && p->rchild!=T)
    {
      p = p->rchild;
      printf("%c", p->data);
    }
    p = p->rchild; /* p进至其右子树根 */
  }
  return OK;
}

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择

参考资料：

CATALOG
    FEATURED TAGS
    Rails Linux Golang 数据结构 包 Shell 代码安全 Git