前言:
此刻小伙伴们对“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语言二叉树的创建与遍历 #二叉树遍历技巧与方法 #二叉树的层次遍历流程图 #二叉树的创建与遍历算法思想 #二叉树遍历左子树