二叉树的创建与遍历算法-C语言

文章目录

1.实验要求2.代码3.结果展示4.分析

1.实验要求

实现二叉树的创建算法与中序列遍历算法。 步骤如下：

将二叉树模拟成完全二叉树，从根结点开始对所有结点进行编号，编号从1开始，在运行过程中输入结点对应的编号和值，最后以编号i=0，结点值x=’$’为循环结束条件；中序遍历已建立的二叉树，并输出遍历结果，中序遍历算法可选择递归和非递归方法。

2.代码

//Authors:xiaobei #include<stdio.h> #include<stdlib.h> typedef struct BiTNode{ int data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; //树节点的定义 ，采用二叉链表形式 void CreateBiTree(BiTree &T); void InOrderTraverse(BiTree T); void PrintMenu(); int main(){ int user; BiTree T = NULL; while (1){ PrintMenu(); scanf("%d",&user); if(user==1) CreateBiTree(T); else if(user==2) InOrderTraverse(T); else if(user==0) break; else printf("[输入错误!]\n"); } } //先序建立二叉树 void CreateBiTree(BiTree &T){ char ch; int i; printf("\n(请输入编号和值)\n>>>"); scanf("%d %c",&i,&ch); printf("%d %c",i,ch); if(i==0 && ch=='$'){ //递归结束条件 T = NULL; printf("\n[此分支结束!]"); } else{ T = (BiTree)malloc(sizeof(BiTNode));//分配空间 T->data = ch; CreateBiTree(T->lchild); //递归创建左子树 CreateBiTree(T->rchild); //递归创建右子树 } } //中序遍历二叉树 void InOrderTraverse(BiTree T){ if(T){ InOrderTraverse(T->lchild); //递归遍历左子树 printf("%c",T->data); //访问根节点 InOrderTraverse(T->rchild); //递归遍历右子树 } } //打印菜单 void PrintMenu(){ printf("\n------------------\n"); printf("1、先序建立二叉树\n"); printf("2、中序遍历二叉树\n"); printf("0、退出\n"); printf("------------------\n"); printf("(请输入选择)\n>>>"); }

3.结果展示

4.分析

先序递归创建二叉树(如上图)输入顺序：

1 A 2 B 3 C 0 $ 0 $ 4 D 0 $ 0 $ 5 E 6 F 0 $ 0 $ 7 G 0 $ 0 $

中序递归输出结果：

C->B->D->A->F->E->G

三种顺序 （前序、中序、后序） 递归遍历的操作，都类似，只要改变输出 （操作） 语句的顺序，即可实现。

如果去掉输出 （操作） 语句，从递归的角度看，三种遍历算法路径相同，只是访问的时机不同，每个节点都路过三次。