【数据结构与算法】-(9)二叉树与顺序表实现


【数据结构与算法】-(1)基础篇

【数据结构与算法】-(2)线性表基础

【数据结构与算法】-(3)循环链表(单向)

【数据结构与算法】-(4)双向链表和双向循环链表

【数据结构与算法】-(5)链表面试题解析

【数据结构与算法】-(6)栈

【数据结构与算法】-(7)队列

【数据结构与算法】-(8)栈之算法题

【数据结构与算法】-(8.1)字符串去重算法

【数据结构与算法】-(8.2)字符串搜索算法和RK&BP算法

【数据结构与算法】-(8.3)KMP算法

一、概念

1.1 树的定义

树是 n (n ≥ 0)个结点的有限集。n=0时称为空树。

在任意一棵非空树中:(1)有且仅有一个特定的成为根(Root)的结点;(2)当 n > 1 时,其余结点可分为m(m > 0)个互不相交的有限集 T1、 T2、…… Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如下图所示:

001

子树如下图所示:

1.2 树的其他特性

  • 度(Degree):结点拥有的子树数成为结点的度。
    • 度为0的结点成为叶子结点(Leaf)或终端结点
    • 度不为0的结点成为非终端结点或分枝结点。
  • 层次(Level):指从根开始定义起,结点所在的楼层。(按照根结点为1开始依次算起)
  • 深度(Depth):树中结点的最大层次成为树的深度或高度。
  • 子结点、双亲结点:结点的子树的根成为该结点的孩子(Child),相应地,该结点成为孩子的双亲结点(Parent)

1.3 二叉树的定义

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

因为二叉树最多只能由左结点和右结点,一个普遍的二叉树如图

1.4 二叉树的基本特点

1.4.1 特点

  • 每个结点最多有两棵子树,所以二叉树中不存在度大于2度结点。
  • 左子树和右子树顺序不可颠倒。
  • 即使树中某结点只有一棵子树,也要区分他是左子树还是右子树。

1.4.2 基本形态

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

1.5 特殊的二叉树

1.5.1 斜树

顾名思义,所有的结点都只有左子树或右子树。所有结点只有左子树的叫左斜树,只有右子树的成为右斜树,两者统称为斜树。

1.5.2 满二叉树

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

1.5.3 完全二叉树

对一颗具有n个结点的二叉树按层序编号,如果编号为i(1≤ i ≤ n)的结点与同样深度的满二叉树中编号为i 的结点在二叉树中的位置完全相同,这棵二叉树称为完全二叉树。

如下图所示,完全二叉树并不要求所有子结点全部填满,只需要子树树按顺序排列。

换句通俗的话说,哥哥一家没生满二胎,弟弟一家不允许要孩子……🐶,否则就不是完全二叉树。

如下图中,11节点丢失的情况下,不可以称为完全二叉树

二、二叉树的存储结构

2.1 顺序存储结构

通常用数组来存储二叉树,先看看存储完全二叉树的情况

可以看到,二叉树中的元素按照顺序依次放入开辟好的数组内存空间里。

但是,凡事都有但是,在某些极端情况下,某一棵树,缺胳膊少腿儿,导致空间大大浪费,比如下图:

这棵树只有4个有效的结点,但是却不得不开辟从A~M一共13个结点的内存空间,这种情况的树,使用数组结构来存储,对内存空间是一种浪费。

2.2 二叉链表

鉴于上文中数组结构无法更高效的表述二叉树,引入了链表的结构进行表述。

由于二叉树结构最多有两个孩子,所以引入的链表结点,结构分别为数据域、左孩子指针、右孩子指针

结点结构如下

左孩子 数据 右孩子
lChild data rChild

用代码来表述可以是这样的

struct BiTreeNode{
        int data;
        BiTreeNode *lChild;
        BITreeNode *rChild;
}BiTreeNode, *BiTree

把上文中较特殊的二叉树,用这样的结点表述的二叉树结构如下:

三、二叉树的遍历

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

二叉树的遍历方法,主要有四种:

3.1 前序遍历

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

如图示:

3.2 中序遍历

遍历的规则是若二叉树为空,空操作返回;否则从根结点开始(但此时并不遍历根结点),先前序遍历左子树,先遍历访问根结点,再前序遍历右子树。

如图示:

3.3 后序遍历

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

如图示

3.4 层序遍历

遍历的规则是若二叉树为空,空操作返回;否则从树的第一层——也就是根结点开始访问,从上往下,在同一层时从左至右对结点逐个访问。

访问顺序如图示:

三、顺序存储下的实现

3.1 顺序存储的实现

3.1.1 二叉树基本操作

  • 初始化环境

    创建结点结构

    typedef struct {
        int level; //结点层
        int order; //本层的序号(按照满二叉树给定序号规则)
    }Position;

    以及其他辅助条件

    #define MAXSIZE 100 /* 存储空间初始分配量 */
    #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */
    
    typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef int CElemType;      /* 树结点的数据类型,目前暂定为整型 */
    typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点  */
    CElemType Nil = 0;   /*设整型以0为空 或者以 INT_MAX(65535)*/
  • 初始化一个二叉树T

    Status InitBiTree(SqBiTree T){
    
        for (int i = 0; i < MAX_TREE_SIZE; i++) {
            //将二叉树初始化值置空
            T[i] = Nil;
        }
    
        return OK;
    }
  • 创建二叉树(放入数据)

    Status CreateBiTree(SqBiTree T){
        int i = 0;
    
        //printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE);
        /*
         1      -->1
         2     3   -->2
         4  5  6   7 -->3
         8  9 10       -->4
    
         1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
         */
    
        while (i < 10) {
            T[i] = i+1;
            printf("%d ",T[i]);
    
            //结点不为空,且无双亲结点
            if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) {
                printf("出现无双亲的非根结点%d\n",T[i]);
                exit(ERROR);
            }
    
            i++;
    
        }
    
        //将空赋值给T的后面的结点
        while (i < MAX_TREE_SIZE) {
            T[i] = Nil;
            i++;
        }
    
        return OK;
    }
  • 清空二叉树

    清空一棵二叉树,与构造一棵二傻树一样,只需将每个结点值置空即可。

    可以直接定义一个新函数,将两个函数对等。

    #define ClearBiTree InitBiTree
  • 判断二叉树是否为空

    只需判断根结点是否为空

    Status BiTreeEmpty(SqBiTree T){
        //根结点为空,则二叉树为空
        return T[0] == Nil;
    }
  • 获取二叉树的深度

    计算深度,需要看从当前结点,到根结点经历的路径条数

    int BiTreeDepth(SqBiTree T){
    
        int j = -1;
        int i;
    
        //找到最后一个结点
        //MAX_TREE_SIZE -> 100 -> 10 目的找到最后一个结点10的位置
        for (i = MAX_TREE_SIZE-1 ; i>=0; i--) {
            if (T[i] != Nil)
                break;
        }
    
        do {
            j++;
        } while ( powl(2, j) <= i); //计算2的次幂
    
        return j;
    }

3.1.2 结点操作

  • 获取二叉树根结点的值

    只需计算数组T 首结点的值即可

    Status Root(SqBiTree T,CElemType *e){
        if (BiTreeEmpty(T)) {
            return ERROR;
        }
    
        *e = T[0];
        return OK;
    }
  • 返回结点位置为e 的值

    CElemType Value(SqBiTree T,Position e){
    
        /*
         Position.level -> 结点层.表示第几层;
         Position.order -> 本层的序号(按照满二叉树给定序号规则)
         */
    
        //pow(2,e.level-1) 找到层序
        printf("%d\n",(int)pow(2,e.level-1));
    
        //e.order
        printf("%d\n",e.order);
    
        //4+2-2;
        return T[(int)pow(2, e.level-1)+e.order-2];
    
    }
  • 修改结点位置e 的值

    Status Assign(SqBiTree T,Position e,CElemType value){
    
        //找到当前e在数组中的具体位置索引
        int i = (int)powl(2, e.level-1)+e.order -2;
    
        //叶子结点的双亲为空
        if (value != Nil &&  T[(i+1)/2-1] == Nil) {
            return ERROR;
        }
    
        //给双亲赋空值但是有叶子结点
        if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) {
            return  ERROR;
        }
    
        T[i] = value;
        return OK;
    }
  • 获取结点位置e 的双亲

    CElemType Parent(SqBiTree T, CElemType e){
    
        //空树
        if (T[0] == Nil) {
            return Nil;
        }
    
        for (int i = 1 ; i < MAX_TREE_SIZE; i++) {
            //找到e
            if (T[i] == e) {
                return T[(i+1)/2 - 1];
            }
        }
        //没有找到
        return Nil;
    }
  • 获取某结点的左孩子

    步骤为当前结点的

    CElemType LeftChild(SqBiTree T,CElemType e){
    
        //空树
        if (T[0] == Nil) {
            return Nil;
        }
        for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
            //找到e
            if (T[i] == e) {
                return T[i*2+1];
            }
        }
    
        //没有找到
        return Nil;
    
    }
  • 获取某结点的右孩子

    CElemType RightChild(SqBiTree T,CElemType e){
    
        //空树
        if (T[0] == Nil) {
            return Nil;
        }
        for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) {
            //找到e
            if (T[i] == e) {
                return T[i*2+2];
            }
        }
    
        //没有找到
        return Nil;
    
    }
  • 获取某结点的左兄弟

    CElemType LeftSibling(SqBiTree T,CElemType e)
    {
        /* 空树 */
        if(T[0]==Nil)
            return Nil;
    
        for(int i=1;i<=MAX_TREE_SIZE-1;i++)
        /* 找到e且其序号为偶数(是右孩子) */
            if(T[i]==e&&i%2==0)
                return T[i-1];
    
        return Nil; /* 没找到e */
    }
  • 获取某结点的右兄弟

    CElemType RightSibling(SqBiTree T,CElemType e)
    {
        /* 空树 */
        if(T[0]==Nil)
            return Nil;
    
        for(int i=1;i<=MAX_TREE_SIZE-1;i++)
        /* 找到e且其序号为奇数(是左孩子) */
            if(T[i]==e&&i%2==1)
                return T[i+1];
    
        return Nil; /* 没找到e */
    }

3.1.3 遍历二叉树

  • 前序遍历

    void PreTraverse(SqBiTree T,int e){
    
        //打印结点数据
        visit(T[e]);
    
        //先序遍历左子树
        if (T[2 * e + 1] != Nil) {
            PreTraverse(T, 2*e+1);
        }
        //最后先序遍历右子树
        if (T[2 * e + 2] != Nil) {
            PreTraverse(T, 2*e+2);
        }
    }
    
    Status PreOrderTraverse(SqBiTree T){
    
        //树不为空
        if (!BiTreeEmpty(T)) {
            PreTraverse(T, 0);
        }
        printf("\n");
        return  OK;
    }
  • 中序遍历

    void InTraverse(SqBiTree T, int e){
    
        /* 左子树不空 */
        if (T[2*e+1] != Nil)
            InTraverse(T, 2*e+1);
    
        visit(T[e]);
    
        /* 右子树不空 */
        if (T[2*e+2] != Nil)
            InTraverse(T, 2*e+2);
    }
    
    Status InOrderTraverse(SqBiTree T){
    
        /* 树不空 */
        if (!BiTreeEmpty(T)) {
            InTraverse(T, 0);
        }
        printf("\n");
        return OK;
    }
  • 后序遍历

    void PostTraverse(SqBiTree T,int e)
    {   /* 左子树不空 */
        if(T[2*e+1]!=Nil)
            PostTraverse(T,2*e+1);
        /* 右子树不空 */
        if(T[2*e+2]!=Nil)
            PostTraverse(T,2*e+2);
    
        visit(T[e]);
    }
    Status PostOrderTraverse(SqBiTree T)
    {
        if(!BiTreeEmpty(T)) /* 树不空 */
            PostTraverse(T,0);
        printf("\n");
        return OK;
    }
  • 层序遍历

    void LevelOrderTraverse(SqBiTree T){
    
        int i = MAX_TREE_SIZE-1;
    
        //找到最后一个非空结点的序号
        while (T[i] == Nil) i--;
    
        //从根结点起,按层序遍历二叉树
        for (int j = 0; j <= i; j++)
            //只遍历非空结点
            if (T[j] != Nil)
                visit(T[j]);
    
        printf("\n");
    }

3.2 链式存储的实现

3.2.1 二叉树的基本操作

  • 数据类型及结点结构如下:

    typedef char CElemType;
    CElemType Nil=' '; /* 字符型以空格符为空 */
    typedef struct BiTNode  /* 结点结构 */
    {
        CElemType data;        /* 结点数据 */
        struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
    }BiTNode,*BiTree;
  • 初始化二叉树

    只需对当前二叉树赋值为空即可。

    Status InitBiTree(BiTree *T)
    {
        *T=NULL;
        return OK;
    }
  • 创建二叉树

    void CreateBiTree(BiTree *T){
    
        CElemType ch;
    
        //获取字符
        ch = str[indexs++];
    
        //判断当前字符是否为'#'
        if (ch == '#') {
            *T = NULL;
        }else
        {
            //创建新的结点
            *T = (BiTree)malloc(sizeof(BiTNode));
            //是否创建成功
            if (!*T) {
                exit(OVERFLOW);
            }
    
            /* 生成根结点 */
            (*T)->data = ch;
            /* 构造左子树 */
            CreateBiTree(&(*T)->lchild);
            /* 构造右子树 */
            CreateBiTree(&(*T)->rchild);
        }
    
    }
  • 清空二叉树

    这里的逻辑与数组存储树一样的,逻辑等于初始化二叉树,用新函数来等同于它。

    #define ClearBiTree DestroyBiTree
  • 销毁二叉树

    void DestroyBiTree(BiTree *T)
    {
        if(*T)
        {
            /* 有左孩子 */
            if((*T)->lchild)
                DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */
    
            /* 有右孩子 */
            if((*T)->rchild)
                DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */
    
            free(*T); /* 释放根结点 */
    
            *T=NULL; /* 空指针赋0 */
        }
    }
  • 判断二叉树是否为空

    Status BiTreeEmpty(BiTree T)
    {
        if(T)
            return FALSE;
        else
            return TRUE;
    }
  • 获取二叉树的深度

    int BiTreeDepth(BiTree T){
    
        int i,j;
        if(!T)
            return 0;
    
        //计算左孩子的深度
        if(T->lchild)
            i=BiTreeDepth(T->lchild);
        else
            i=0;
    
        //计算右孩子的深度
        if(T->rchild)
            j=BiTreeDepth(T->rchild);
        else
            j=0;
    
        //比较i和j
        return i>j?i+1:j+1;
    }

3.2.2 结点操作

  • 获取二叉树根结点的值

    CElemType Root(BiTree T){
        if (BiTreeEmpty(T))
            return Nil;
    
        return T->data;
    }
  • 获取指针p 指向的结点的值

    CElemType Value(BiTree p){
        return p->data;
    }
  • 给p 指向的结点赋值

    void Assign(BiTree p,CElemType value)
    {
        p->data=value;
    }

3.2.3 遍历操作

  • 前序遍历

    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);/* 显示结点数据,可以更改为其它对结点操作 */
    }

文章作者: 李佳
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 李佳 !
评论
 上一篇
【多线程】锁分析 【多线程】锁分析
一、概念1.1 同步为了避免多个线程同时读写同一个数据而产生不可预料的后果,我们要将各个线程对同一个数据的访问同步(Synchronization)。 所谓同步,即指在一个线程访问数据未结束的时候,其他线程不得对同一个数据进行访问。如此,对
2020-05-13 李佳
下一篇 
【数据结构与算法】-(8.3)KMP算法 【数据结构与算法】-(8.3)KMP算法
【数据结构与算法】-(1)基础篇 【数据结构与算法】-(2)线性表基础 【数据结构与算法】-(3)循环链表(单向) 【数据结构与算法】-(4)双向链表和双向循环链表 【数据结构与算法】-(5)链表面试题解析 【数据结构与算法】-(6)栈
2020-04-23 李佳
  目录