二叉树的遍历操作实现
发布网友
发布时间：2022-04-25 14:08
共2个回答
热心网友
时间：2022-04-16 02:43
//链表二叉树的定义和操作
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //最大节点个数
typedef struct node{
char data;
struct node *lchild,*rchild; //左边孩子的指针 和 右边孩子的指针
}BinTNode;
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum是结点数 leaf是叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点“#”以示空指针的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
scanf("%c",&ch);
if(ch=='#') //读入# 返回空指针
return(NULL);
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//DLR 先序遍历
//访问根节点 先序遍历左子树 先序遍历右子树
void Preorde(BinTree T){
if(T){
printf("%c",T->data); //访问结点 D
Preorde(T->lchild); //先序遍历左子树 L
Preorde(T->rchild); //先序遍历右子树 R
}
}
//LDR 中序遍历
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍历左子树 L
printf("%c",T->data); //访问结点 D
Inorder(T->rchild); //中序遍历右子树 R
}
}
//LRD 后序遍历
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //后序遍历左子树 L
Postorder(T->rchild); //后序遍历右子树 R
printf("%c",T->data); //访问结点 D
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr?hl:hr; //取最大深度
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) //若左右深度都为0 则为叶子
leaf=leaf+1;
return(max+1);
}else{
return(0);
}
}
//利用“先进先出”（FIFO）队列，按层次遍历二叉树
void Levelorder(BinTree T){
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear){
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BinTree root;
int i,depth; //最大深度
printf("\n创建二叉树;输入完全二叉树先序序列:");
//用#代表虚结点 如ABD###CE##F##
root=CreatBinTree(); //创建二叉树 返回根结点
printf("\n创建成功!\n");
do{ //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: 先序遍历\n");
printf("\t2: 中序遍历\n");
printf("\t3: 后序遍历\n");
printf("\t4: 求树的深度及叶子数\n");
printf("\t5: 按层次遍历\n"); //按层次遍历之前，先选择4，求出该树的结点数。
printf("\t0: 退出\n");
printf("\t*******************************\n请选择:");
scanf("%d",&i); //输入菜单选项 0-5
switch(i){
case 1:
//1: 先序遍历 Preorde
printf("先序遍历的结果是");
Preorde(root); //
printf("\n");
break;
case 2:
//2: 中序遍历 Inorder
printf("中序遍历的结果是");
Inorder(root); //
printf("\n");
break;
case 3:
//3: 后序遍历 Postorder
printf("后序遍历的结果是");
Postorder(root); //
printf("\n");
break;
case 4:
//4: 求树的深度及叶子数 TreeDepth
depth=TreeDepth(root); //
printf("数的深度=%d 结点数=%d",depth,NodeNum);
printf(" 叶子数=%d",leaf);
printf("\n");
break;
case 5:
//5: 按层次遍历 Preorde
printf("按层次遍历的结果是");
Levelorder(root); //
printf("\n");
break;
default:
printf("输入错误\n");
break;
}
}while(i!=0);
return 0;
}
是vs做的 有些地方需要改下 是C语言做的
热心网友
时间：2022-04-16 04:01
