【数据结构】二叉树及其各种遍历

关于树的定义和存储结构可以查看上一篇文章树的定义和树的三种存储结构

一、二叉树的定义

二叉树的定义

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者是由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。（官方概念，不是很直观，直接上图）

二叉树

二叉树的特点

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。（注意不是只有两颗子树，是最多有）
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某个结点只有一棵树，也要区分它是左子树还是右子树。

二叉树的五中基本形态

• 空二叉树。
• 只有一个根节点。
• 根结点只有左子树。
• 根结点只有右子树。
• 根结点既有左子树又有右子树。

特殊二叉树

斜树

• 左斜树：所有的结点都只有左子树的二叉树。
• 右斜树：所有的结点都只有右子树的二叉树。

满二叉树

所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树。

满二叉树的特点

• 叶子结点只能出现在最下一层。出现在其他层就不可能达到平衡。
• 非叶子结点的度一定是2。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最少。

完全二叉树

对于一颗具有n个结点的二叉树按层序编号，如果编号为i(1<=i&&i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同的二叉树。（概念难理解，直接上图）

完全二叉树

完全二叉树的特点

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

区分满二叉树和完全二叉树

• 满二叉树一定是完全二叉树。
• 完全二叉树不一定是满二叉树。

---

二、二叉树的性质

• 性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
• 性质2：深度为k的二叉树至多有2^k - 1个结点(k>=1)。（注意是2^k后再减去1）
• 性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点树为n2,则n0 = n2+1.
• 性质4：具有n个结点的完全二叉树的深度为：向下取整log2n+1;(注意，对x的向下取整就是取不大于x的最大整数)
• 性质5：如果对一颗有n个结点的完全二叉树的结点按层序编号（从第1层到第（向下取整log2n+1），每层从左到右）层，对任一结点i(1<=i&&i<=n)有：
  • 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点：向下取整i/2;
  • 如果2i>n，则结点i无左孩子（结点i为叶子结点）;否则其左孩子是结点2i;
  • 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1；

三、二叉树的存储结构

树的存储结构可以查看前一篇文章：
由于二叉树是特殊的树树的定义和树的三种存储结构

由于二叉树是一种特殊的树，所以一般采用二叉链表来存储二叉树。将二叉树的结点的最多有两个孩子，所以为它设计一个数据域和两个指针域。

lchild	data	rchild
指向左孩子的指针	数据域	指向右孩子的指针

代码实现：

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

二叉链表

---

四、二叉树的遍历

二叉树的遍历定义

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

二叉树的遍历方式有很多，如果我们限制了从左到右的习惯方式，那么主要分为四种：

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

前序遍历

• 若二叉树为空，则空操作返回；
• 若不为空，则先访问根结点，然后前序遍历左子树，在前序遍历右子树。

• 下图的前序遍历结果为：ABDGHCEIF

  
  前序遍历

中序遍历

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

• 下图的中序遍历结果是：GDHBAEICF

  
  中序遍历

后序遍历

• 若二叉树为空，则空操作返回；
• 若不为空，则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根节点。

• 下图的后序遍历结果为：

  
  

层序遍历

• 若二叉树为空，则空操作返回；
• 若不为空，则从树的第一层(也就是根结点)开始访问，从上到下逐层遍历，在同一层中，从左到右的顺序对结点逐个访问。

• 下图的层序遍历结果为：ABCDEFGHI

  
  层序遍历

代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100 

typedef char ElemType;

typedef struct BiTNode{
    
    char data;  // 数据域
    struct BiTNode * lchild;  // 指向左孩子的指针
    struct BiTNode * rchild; // 指向右孩子的指针
}BiTNode, *BiTree;

/**
 * 按照前序输入的方式构造二叉树
 */
void CreatBitree(BiTree *T){
    
    char c = '\0';
    
    scanf("%c", &c);
    
    if (c == '#') {  // 空结点
        *T = NULL;
        
    }else{
        
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (!T)
            exit(0);
        (*T)->data = c;  // 生成根节点
        CreatBitree(&(*T)->lchild);  // 构造左子树
        CreatBitree(&(*T)->rchild);  // 构造右子树
    }
}


/**
 * 二叉树的前序递归遍历
 */
void PreOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空树
        return;
    printf("%c", T->data);  // 显示结点数据
    
    PreOrderTraverse(T->lchild);  // 先序遍历左子树
    PreOrderTraverse(T->rchild);  // 再先序遍历右子树
}

/**
 * 二叉树的中序递归遍历
 */
void InOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空树
        return;
    InOrderTraverse(T->lchild);  // 中序遍历左子树
    
    printf("%c", T->data);  // 显示结点数据
    
    InOrderTraverse(T->rchild); // 最后中序遍历右子树
}

/**
 * 二叉树的后序递归遍历
 */
void PostOrderTraverse(BiTree T){
    
    if (T == NULL)  // 空树
        return;
    
    PostOrderTraverse(T->lchild);  // 先后序遍历左子树
    PostOrderTraverse(T->rchild);  // 再后序遍历右子树
    printf("%c", T->data);  // 显示结点数据
}

测试代码

int main(int argc, const char * argv[]) {
    
    printf("请按照先序输入二叉树的结点，空结点用#表示, 回车结束\n");

    BiTree T = NULL;
    CreatBitree(&T);
    
    printf("该二叉树的前序遍历结果为：\n");
    PreOrderTraverse(T);
    printf("\n");
    
    printf("该二叉树的中序遍历结果为：\n");
    InOrderTraverse(T);
    printf("\n");
    
    printf("该二叉树的后序遍历结果为：\n");
    PostOrderTraverse(T);
    printf("\n");

    return 0;
}

---

扩展：遍历二叉树的同时输出该节点所在的层数

在二叉树的几种遍历方式的代码中，为了输出该节点的数据，会有一个printf，要输出该节点的层数 ，就可以改变这里的代码来实现，比如在前序递归遍历的同时输出节点所在层数，可以将这个打印代码写在一个封装在一个方法里面然后调用

代码实现

/**
 * 打印该节点所在层数
 */
void visit(char c, int level){
    printf("%c 位于第 %d 层\n", c, level);
}
/**
 * 二叉树的前序递归遍历
 */
void PreOrderTraverse(BiTree T, int level){
    
    if (T == NULL)  // 空树
        return;
//    printf("%c", T->data);  // 显示结点数据
    visit(T->data, level);  // 调用写好的打印方法
    
    PreOrderTraverse(T->lchild, level + 1);  // 先序遍历左子树
    PreOrderTraverse(T->rchild, level + 1);  // 再先序遍历右子树
}
int main(int argc, const char * argv[]) {
    
    printf("请按照先序输入二叉树的结点，空结点用#表示, 回车结束\n");

    int level = 1;
    BiTree T = NULL;
    CreatBitree(&T);
    
    printf("该二叉树的前序遍历结果为：\n");
    PreOrderTraverse(T, level);
    printf("\n");
    return 0;
}

结果输出