数据结构-二叉树遍历总结

二叉树结构

二叉树是一种特殊的树,每个父结点最多只能用有两个子结点。

在树中,按照结点的“继承”关系可以分为父结点和子结点; 按照结点的位置关系可以分为根结点,中间结点和叶结点。 其中叶结点没有子结点。 我们用结点中的数字代表结点,那么在上图中:10为根结点;6、14为中间结点;4、8、12、16为叶节点。

二叉树存储结构

二叉树结构可以使用链式和顺序两种方式实现,其中比较常用的链式存储结构:

链式结构

typedef char TElemType; 
typedef struct BiTNode  /* 结点结构 */
{
   TElemType data;      /* 结点数据 */
   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

也可以写成这样,更清晰一些:

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

顺序结构

#define LENGTH 100  
typedef char datatype;  
typedef struct node{  
    datatype data;  
    int lchild,rchild;  
    int parent;  
}Node;  

Node tree[LENGTH];  
int length;  
int root;  

本质上是一个结构体数组。

二叉树遍历

在二叉树中最重要的操作大概就是遍历,如链表这样的数据结构,遍历的方式是唯一的,因为我们只知道链表的头结点,遍历到一个结点时也只知道下一个结点(单链表),但是在树中却有多种遍历方式,通常有: 前序遍历:根结点—>左子结点—>右子结点,10、6、4、8、14、12、16; 中序遍历:左子结点—>根结点—>右子结点,4、6、8、10、12、14、16; 后序遍历:左子结点—>右子结点—>根结点,4、8、6、12、16、14、10; 层序遍历:第一层—>第二层—>第n层,10、6、14、4、8、12、16;

代码实现

遍历操作可以使用循环和递归的方式实现,其中递归可以使代码变的很简洁易懂,同样树的结构越复杂,递归的层数就会越深,但是总体上递归的方法更常用。

前序遍历:

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

以上三种遍历方式很相似,只是递归的输入不同,而这就决定着遍历的顺序,我们拿前序遍历举个例子:

还是上面这个图,此时函数的输入为树的根结点,这是一个BiTree 类型的变量,前面定义了它是一个指针,打印10,此时没有进入递归,深度为0:

执行PreOrderTraverse(T->lchild)递归两次后打印6、4,此时打印6的那次递归深度是1,打印4的递归深度是2:

此时执行PreOrderTraverse(T->lchild),但是4没有左子结点,进入一下第3层递归又退出回到第2层,执行PreOrderTraverse(T->rchild)但是4没有右子结点,进入一下第3层递归又退出回到第2层,此时结点4已经执行完了,返回第1层(结点6),执行PreOrderTraverse(T->rchild),打印8:

递归又到了第2层,显然又要退回到第1层,但是到了第1层发现第1层也执行完了,退回到第0层(结点10),执行PreOrderTraverse(T->rchild),打印14,于是后面就一样了,直到打印了16之后,从第2层开始退出,退到第0层之后发现第0层也执行完了:

最后,树的层序遍历与上面三种遍历方式不同,而且也不仅仅能用在二叉树,这个在本博客中先不涉及,后面补上。

其他操作

二叉树除了遍历外,还有一些其他的基本操作:

构建空二叉树:

typedef int Status; 
Status InitBiTree(BiTree *T)
{ 
    *T=NULL;
    return OK;
}

销毁二叉树:

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

创建二叉树:

void CreateBiTree(BiTree *T)
{ 
    TElemType ch;

    ch=str[index++];

    if(ch=='#') 
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch; /* 生成根结点 */
        CreateBiTree(&(*T)->lchild); /* 构造左子树 */
        CreateBiTree(&(*T)->rchild); /* 构造右子树 */
    }
}

判断二叉树是否存在:

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;
    return i>j?i+1:j+1;
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏撸码那些事

【图解数据结构】 线性表

1242
来自专栏与神兽党一起成长

前序遍历树

代码来自:pickle and cPickle – Python object serialization 首先树的结构,如图

812
来自专栏数据结构与算法

177. [USACO Jan07] 有限制的素数

177. [USACO Jan07] ★   输入文件:qprime.in   输出文件:qprime.out   简单对比 时间限制:1 s   内存限制:...

3329
来自专栏架构说

132. 分割回文串 II

  str = “ABA”,str本身就是回文串,返回0.   str = “A|CDCDC|DAD”,最少需要切两次变成3个回文子串,所以 返回2.

932
来自专栏王硕

原 B树C语言代码实现

4799
来自专栏desperate633

LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

713
来自专栏趣学算法

数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位...

693
来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

1898
来自专栏nnngu

数据结构03 线性表之链表

上一篇总结完了顺序表,这一篇要总结的是线性表之中的链表。我将会从以下几点进行总结: 1、为什么要使用链表?  2、链表的存储结构?  3、链表的常用操作代码实现...

3197
来自专栏尾尾部落

[剑指offer] 二叉树中和为某一值的路径

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

551

扫码关注云+社区