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

二叉树结构

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

在树中,按照结点的“继承”关系可以分为父结点和子结点; 按照结点的位置关系可以分为根结点,中间结点和叶结点。 其中叶结点没有子结点。 我们用结点中的数字代表结点,那么在上图中: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 条评论
登录 后参与评论

相关文章

来自专栏电光石火

java获取当前时间和前一天日期

String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

2228
来自专栏书山有路勤为径

二叉树-路径之和

给定一个二叉树与整数sum,找出所有从根节点到叶结点的路径,这些路径上的节点值累加和为sum。

632
来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3514
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题23从上往下打印二叉树

本题的详细分析过程均在代码注释中: import java.util.Queue; import java.util.concurrent.LinkedBloc...

2888
来自专栏电光石火

java获取当前时间和前一天日期

String basePath = request.getScheme()+"://"+request.getServerName()+":"+request....

2215
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

本题详细的分析过程均在代码注释中: import java.util.Iterator; import java.util.Stack; /** * 题目:...

2845
来自专栏恰同学骚年

剑指Offer面试题:25.二叉搜索树与双向链表

  首先,我们知道:在二叉树中,每个结点都有两个指向子结点的指针。在双向链表中,每个结点也有两个指针,它们分别指向前一个结点和后一个结点。

921
来自专栏深度学习与计算机视觉

算法-重建二叉树

题目: 输入某二叉树的前序遍历与中序遍历结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果均无重复数字,前序遍历序列为{},中序遍历序列为{},则重...

18510
来自专栏机器学习实践二三事

二叉树的建立和各种遍历(java版)

这是个常见的面试题,比如说通过二叉树的先序和中序遍历,得到二叉树的层序遍历等问题 先序+中序 ->建树 假设现在有个二叉树,如下: ? 此时遍历顺序是: ...

2235
来自专栏aCloudDeveloper

算法导论第十二章 二叉搜索树

一、二叉搜索树概览   二叉搜索树(又名二叉查找树、二叉排序树)是一种可提供良好搜寻效率的树形结构,支持动态集合操作,所谓动态集合操作,就是Search、Max...

20510

扫码关注云+社区