二叉树的基本操作完整版,包含二叉树的所有操作,凡是你想要的都在

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#include "math.h"

typedef char TElemType; //定义结点数据为字符型

typedef int Status; //定义函数类型为int型

#define ERROR 0

#define OK 1

typedef struct BiTNode{ //定义结构体

TElemType data; //结点数值 struct BiTNode *lchild; //左孩子指针 struct BiTNode *rchild; //右孩子指针 struct BiTNode *next; //下一结点指针

}BiTNode, *BiTree;

Status NumJudge(char ch[20]){

//限制输入数据必须为大于零的整形

char ch1[20]; int num; while(1){ } scanf("%s",ch); num=atoi(ch); //将字符串转换为整型 itoa(num,ch1,10); //将整型转换为字符串型 if(strcmp(ch,ch1)==0&&num>0)break; else{printf("请输入一个大于零的整数: ");}

return num;

}//NumJudge

Status InitBiTree(BiTree &T){

//构造空二叉树T

if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); //若申请空间失败则退出 T->next=NULL; printf("\n\t空二叉树构建成功!\n\n"); return OK;

}//InitBiTree

Status DestroyTree(BiTree &T,BiTree t){

//销毁二叉树

if(T){ } free(T);T=NULL; printf("\t二叉树销毁成功!\n");

if(t){

DestroyTree(T,t->lchild);

DestroyTree(T,t->rchild);

free(t);

}

return OK;

}//DestroyTree

Status ClearBiTree(BiTree &T,int sum,int &i){

//清空二叉树

if(T){

ClearBiTree(T->lchild,sum,i);

ClearBiTree(T->rchild,sum,i); free(T); i++; } if(i==sum){printf("\t二叉树清空成功!\n");T=NULL;}

return OK;

}//ClearBiTree

Status CreateBiTree(BiTree &T,int i,int j,TElemType ch){

//按先序次序输入二叉树中结点的值(一个字符),空格字符表示该结点为空

//构造二叉链表示的二叉树T

TElemType ch1; int k; char str[20]; if(i==0){printf("\n 按先序顺序建立二叉树:请按提示输入相应的数据(一个字符)，若提示结点数值为空，\n 请输入空格\n\n");

printf("%5s请输入树根: "," ");}

if(i!=0&&i>=j){printf("%5s请输入%c的左孩子: "," ",ch);}

if(j!=0&&j>i){printf("%5s请输入%c的右孩子: "," ",ch);}

while(1){ //限制输入数据必须为字符型,否则重新输入

fflush(stdin); for(k=0;k<20;k++){ str[k]=getchar(); if(str[k]=='\n')break; } if(k==0)printf("%5s请输入一个字符后再按Enter键: "," "); if(k==1)break; if(k>1)printf("%5s您只能输入一个字符: "," "); } ch1=str[0]; //获取输入的准确字符型数据 if(ch1==' '){T=NULL;return ERROR;} //输入空格则为根结点为空 if(ch1!=' '){

if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(ERROR); T->data=ch1; //生成根结点 ch=T->data; i++; CreateBiTree(T->lchild,i,j,ch); //构造左子树 j=i;j++; CreateBiTree(T->rchild,i,j,ch); //构造右子树 } i=0;j=0; return OK;

}//CreateBitree

Status TreeDepth(BiTree T,int l,int &h){

//若二叉树存在,返回其深度

if(T){ l=l+1; } return h; if(l>h)h=l; TreeDepth(T->lchild,l,h); TreeDepth(T->rchild,l,h);

}//TreeDepth

Status GetRootElem(BiTree T){

//获取根结点值

printf("该二叉树的根结点值为: %c\n\n",T->data); return OK;

}//GetRootElem

Status SaveElem(BiTree T,BiTree *Q,int i){

//根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法 //保存二叉树的有效结点至指针数组Q特定的位置

if(T){ Q[i]=T;

SaveElem(T->lchild,Q,2*i);

SaveElem(T->rchild,Q,2*i+1);

}

return OK;

}//SaveElem

Status Lev_Traverse(BiTree T,int h){

//按层次从上到下,每层从左到右的顺序显示树状二叉树

if(T==NULL){printf("\n\t\t二叉树目前为空树\n\n");return ERROR;}

BiTree *Q;

if(!(Q=(BiTree *)malloc(int(pow(2,h)+1) * sizeof(BiTNode))))exit(ERROR);

int i,j,n=1,k=h;

for(i=1;i<=int(pow(2,h)+1);i++){

Q[i]=NULL;}

SaveElem(T,Q,n); //将目前有效结点按照满二叉树的序号存储

printf(" 提示:规定下图中的有效结点的位置序号从1开始按从上到下,从左到右的顺序依次递增\n");

for(i=1;i<=(pow(2,h)+1);i++){ //树形显示二叉树 if(int(pow(2,h))%i==0){ } } printf("\n"); printf("\t\t"); for(j=0;j<pow(2,k-1)-1;j++){ } k--; printf(" "); if(Q[i])printf("%c",Q[i]->data); if(!Q[i])printf(" "); for(j=0;j<pow(2,k+1)-1;j++){ printf(" ");}

printf("\n\n");

i=0;j=0;

return OK;

}//Lev_Traverse

Status FirstPrint(BiTree T,int i){

//按先序次序(递归)访问二叉树

if(i==0)printf("\n先序(递归)遍历结果如下:\n");

if(T){ i++;printf("%-5c",T->data); //访问T } i=0; return OK; FirstPrint(T->lchild,i); //递归遍历左子树 FirstPrint(T->rchild,i); //递归遍历右子树

}//FirstPrintBiTree

Status MiddlePrint(BiTree T,int i){

//按中序次序(递归)访问二叉树

if(i==0)printf("\n中序(递归)遍历结果如下:\n"); if(T){ i++;

} i=0; MiddlePrint(T->lchild,i); //递归遍历左子树 printf("%-5c",T->data); //访问T MiddlePrint(T->rchild,i); //递归遍历右子树 return OK;

}//MiddlePrint

Status LastPrint(BiTree T,int i){

//按后序次序(递归)访问二叉树

Status PreOrderTraverse(BiTree T){

//按先序(非递归)遍历二叉树T

BiTree p,S,q; int flag=0; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); S->next=NULL; //建立空栈S if(i==0)pr …… 此处隐藏：3393字，全部文档内容请下载后查看。喜欢就下载吧 ……