龙空技术网

数据结构|二叉树的创建和深度优先遍历

小智雅汇 464

前言:

此刻小伙伴们对“c语言二叉树的创建与遍历”大体比较关注,小伙伴们都想要知道一些“c语言二叉树的创建与遍历”的相关内容。那么小编在网上收集了一些对于“c语言二叉树的创建与遍历””的相关内容,希望我们能喜欢,你们一起来了解一下吧!

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树、二叉堆、和哈夫曼树。

二叉树的遍历是指依照某种顺序逐一访问二叉树的所有结点。这里的“访问”可以是输出结点中的数据,也可以是对结点进行某种处理或操作。遍历操作本着“不重不漏”的原则,即每个结点只能访问一次,且全部结点都能访问到。

为什么需要二叉树遍历呢?线性数组或链表可以单向从头到尾遍历或反向遍历。二叉树是非线性数据结构,通过遍历可以将二叉树中的结点访问一次且仅一次,从而得到访问结点的顺序序列。从这个意义上说,遍历操作就是将二叉树中结点按一定规律线性化的操作,目的在于将非线性化结构变成线性化的访问序列。

二叉树遍历有深度优先遍历和广度优先遍历二种思想。

1 深度优先的递归遍历

从二叉树的定义可知,一棵二叉树宏观上由三部分组成:根结点、根结点的左子树和根结点的右子树。因此只要完整地遍历了这三部分,就等于遍历了整棵二叉树。二叉树的根结点可以通过指针直接访问到根结点的数据。但是如何遍历根结点的左子树和右子树呢?其实可以把根结点的左子树和右子树看作两棵独立的二叉树,以同样的方式来遍历左子树和右子树显然这是一种递归形式的遍历。

二叉树通常有3种遍历方法(先左后右):

先序(根)遍历(DLR,根左右)

中序(根)遍历(LDR,左根右)

后序(根)遍历(LRD,左右根)

其中D表示根节点、L表示左子树,R表示右子树。因为二叉树结构本身就是一种递归的结构,所以这3种遍历方式也都是递归形式定义的。先序遍历DLR表示D→L→R,如下:

void PreOrderTraverse(BiTreee T){

if(T){ //如果二叉树为空,递归遍历结束

visit(T); //访问根节点,可以是输出或其它处理

PreOrderTraverse(T->lchild); //先序遍历T的左子树

PreOrderTraverse(T->rchild); //先序遍历T的右子树

}

}

其它两种遍历只是visit(T);语句放置的位置不一样。所以三种递归遍历算法的搜索路线相同,只是访问各节点的时间不同。

具体线路为: 从根结点出发,逆时针沿着二叉树外缘移动,对每个结点均途径三次,最后回到根结点。(逆时钟方向,整体上是从左子树到右子树,从内到外)

(三种递归相同的搜索路线,类似于斐波那契的递归算法。是一种函数的递归调用,是一个调用栈对函数和参数在栈中的压入与弹出形成的路线,相关内容请参考:C|深入了解函数调用与递归调用(递推、回归))

任一节点都有三次访问的机会,如下图所示:

作为根节点被调用(在上图中用箭头↙或↘表示);

从左子树返回(如果是叶结点,则是从空左子树返回,用箭头↗表示);

从右子树返回(如果是叶结点,则是从空右子树返回,用箭头↖表示);

对于先序遍历来说,剪头第一次经过的结点(递归调用第一时间访问根节点),就是遍历的序列,以后再次经历就不算进去了。

对于中序遍历来说,剪头第二次经过的结点(左子树返回后访问根节点),就是遍历的序列,之前的和以后的再次经历就不算进序列里去了。

对于后序遍历来说,剪头第三次经过的结点(右子树返回后访问根节点),就是遍历的序列,之前经历的就不算进去了。

2 二叉树前序遍历的非递归实现

二叉树的遍历可以通过递归调用实现,也可以用非递归来实现。当用非递归来实现时,需要使用一个栈来辅助,用来记录尚待遍历的结点,以备以后访问。

二叉树的非递归前序遍历:对二叉树各结点的访问顺序是沿其左链一路访问下来,在访问结点的同时将其入栈,直到左链为空。然后结点出栈,对于每个出栈结点,即表示该结点和其左子树已被访问结束,应该访问该结点的右子树。具体步骤如下:

2.1 当前指针指向根结点;

2.2 打印当前结点,当前指针指向其右子树并进栈,重复操作,直到左子树为NULL;

2.3 依次退栈,将当前指针指向右子树;

2.4 苦栈非空或当前指针非NULL,执行2.2,否则结束。

总的思路就是从根结点开始,左子树遍历,并把左子结点推入栈中,然后出栈操作,同时遍历右子树。遍历的顺序上非递归遍历的顺序路线相同。通过双重循环实现。

3 编程实例

编程实现二叉树的创建和先序、中序、后序遍历及深度优先的非递归遍历:

代码:

运行结果:

需要注意的是,在CreatBiTree(BiTree *T)中,因为BiTree本身就是链表指针,所以*T中的T是一个指向指针的指针,T为指向BiTree类型的指针类型,也就是指向指针的指针,*T实质上是一个指针变量。故修改*T就修改了实参(根指针)本身 。

以上三种递归遍历的方法,如果将访问的语句去掉,也三种结构的语法相同,所以说,他们的路径是相同的,只是对根结点的访问时机不同。

深度优先的递归或非递归实现,都是从左往右,从外往内,遍历路线的顺序相同。递归在于编程语言使用了调用栈,非递归在于编程人员自己使用了一个辅助栈。

附源码:

#include "stdio.h"

#define MAX 20

typedef struct BiTNode{

char data;/*结点的数据域*/

struct BiTNode *lchild , *rchild;/*指向左孩子和右孩子*/

} BiTNode , *BiTree;

void CreatBiTree(BiTree *T){/*按先序序列创建一棵二叉树*/

char c;

scanf("%c",&c);

if(c == ' ') *T = NULL;

else{

*T = (BiTNode * )malloc(sizeof(BiTNode));/*创建根结点*/

(*T)->data = c;/*向根结点中输入数据*/

CreatBiTree(&((*T)->lchild));/*递归地创建左子树*/

CreatBiTree(&((*T)->rchild));/*递归地创建右子树*/

}

}

void PreOrderTraverse(BiTree T ){/*先序遍历二叉树*/

if(T){/*递归结束条件,T为空*/

printf("%3c",T->data);/*访问根结点,将根结点内容输出*/

PreOrderTraverse(T->lchild);/*先序遍历T的左子树*/

PreOrderTraverse(T->rchild);/*先序遍历T的右子数*/

}

}

void InOrderTraverse(BiTree T){/*中序遍历二叉树*/

if(T){/*如果二叉树为空,递归遍历结束*/

InOrderTraverse(T->lchild);/*中序遍历T的左子树*/

printf("%3c",T->data);/*访问根结点*/

InOrderTraverse(T->rchild);/*中序遍历T的右子数*/

}

}

void PosOrderTraverse(BiTree T){/*后序遍历二叉树*/

if(T){/*如果二叉树为空,递归遍历结束*/

PosOrderTraverse(T->lchild);/*后序遍历T的左子树*/

PosOrderTraverse(T->rchild);/*后序遍历T的右子数*/

printf("%3c",T->data);/*访问根结点*/

}

}

void PreOrder_NR(BiTree T)//深度优先非递归前序遍历

{

BiTree Ptr;

BiTree Stack[MAX];//栈定义

int top=0;//栈顶指针

Ptr = T;

do

{

while(Ptr!=NULL)//树结点非空,遍历其左子树

{

printf("%3c",Ptr->data);//操作结点

Stack[top]=Ptr;//树结点进栈

top++;

Ptr=Ptr->lchild;//查看左子树

}

if(top>0)//栈非空,出栈

{

top--;

Ptr=Stack[top];

Ptr=Ptr->rchild;//取栈顶点结点右子树

}

} while(top>0 || Ptr!=NULL);

}

main()

{

BiTree T = NULL;/*最开始T指向空*/

printf("需要创建和遍历的二叉树:\n");

printf(" A\n");

printf(" / \\\n");

printf(" B E\n");

printf(" / \\ \\\n");

printf(" C D F\n");

printf("Input some characters to create a binary tree\n");

printf("(按先序序列建立)\n");

printf("例如,ABC##D##E#F##↙,#表示空格,↙表示回车\n");

CreatBiTree(&T);/*创建二叉树*/

printf("The squence of preorder traversaling(先序遍历) binary tree\n");

PreOrderTraverse(T);/*先序遍历二叉树*/

printf("\nThe squence of inorder traversaling(中序遍历) binary tree\n");

InOrderTraverse(T);/*中序遍历二叉树*/

printf("\nThe squence of posorder traversaling(后序遍历) binary tree\n");

PosOrderTraverse(T);/*后序遍历二叉树*/

printf("\n深度优先非递归前序遍历二叉树\n");

PreOrder_NR(T);

getchar(); getchar();

}

-End-

标签: #c语言二叉树的创建与遍历 #二叉树遍历技巧与方法 #二叉树的层次遍历流程图 #二叉树的创建与遍历算法思想 #二叉树遍历左子树