数据结构库VC实践实例_树与二叉树答案说明

此程序功能比课程设计要求的要多,可作为复习资料,测试用原始二叉树如左图,共有两次 行结果截图,每次所删除的子树不同,务必自行分析各步结果得到的过程注意最初输入时含有 的空格数(abc空d空空空ef空空g空h空空),附录中含有源码,务必认真阅读! 树B的先序输出序列为: abcdefgh 树B江的中序输 cdbafegh 叉树B后序输出为: dc bf hgea 叉树B讧树深 先序谝 树Bi叶子结点数为 求二又树B叶子结点数为 3 输入要查找的元素元素值前加一个空格:e 元素e在Bi中,e结点的双亲结点为a,是双亲的右孩子 g 下面重新读入x并删除以x为根的子树 h输入x元素值前 的子树后B讧的先序输出序列为:ahcd 删除Bi中以x为根的子树后B的中序输出序列为:cdba 删除BiT中以x为根的子树后Bi的后序输出序列为 以下根据二又树B构造相应的孩子兄弟法存储的树或森林r 四式输出为 由源二叉树转换得到的树或森林为: 沟造好的树的后跟输出序列或森林的中序输出序列为:cdba 构造好的树的深唐为:3 以下先复制B得到图,后将树x的各结点的左右孩子互换: 下进行结果测试 abdc 得X叶子结点数为:1 种方 谝历树B辽得:cdha 非递归第二种方法中序偏历树Bir得:cdba 段后的树先序输出为:

此程序功能比课程设计要求的要多，可作为复习资料，测试用原始二叉树如左图，共有两次运 行结果截图，每次所删除的子树不同，务必自行分析各步结果得到的过程.注意最初输入时含有 的空格数(abc 空 d 空空空 ef 空空 g 空 h 空空) ，附录中含有源码，务必认真阅读！ a b c d e f g h

树Bir 为: cdbafegh的 叉树Br的先序输出序列为: abcdef 树Br后序辅出为: dc bf hge 叉树Bi树深:4 a 叉树B辽结点总 求得二叉树B叶子结点数为:3 先序谝历求二叉树B辽叶子结点数为:3 输入要查找的元素 加一个空格:a 元素a在Bi中, 根结点,不存在双亲结点 下面重新读入x并删除以x为根的子树 输入x,元素值前 Bi的先序输出序列为: abcdef h)删除Bir中以x为根 后B辽的中序 chafe 除B辽T中以x为根的子树后Bi的后序输出序列为: dcbfea 以下根据二又树B构造相应的孩子兄弟法存储的树或森林 源二叉树凹式输出为: 由源二叉树转换得到的树或森林为: 构造好的树的后跟输出序列或森林的中序输出序列为: cabane 构造好的树的深度为:3 以下先复制BiI得到,后将树x的各结点的左右孩子互换: 互换完毕,以下进行结果测试: aefbcd fedcba 罪速第一种方法历树1得:ebe

a b c d e f g h

//头文件包含 #include Include #include 函数状态码定义 #define true Define ok 1010 #define error #define overFlow -l Define Infeasible -2 #define null 0 typedef int Status /以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定 位双亲、删除、凹式输出等操作实现 /树中元素类型定义与二叉链表存储结构定义 typedef char TElemType typedef struct BiTNodet TElemType data struct bitNode *lchild. *rchild ) BiTNode, * BiTree Status CreateBiTree(BiTree&T)/先序创建二叉树各结点,注意输入时空指针不要丢 TElemType e scanf (%c", &e) if(e==’’)T=NUL T=(BiTree) malloc(sizeof (BiTNode)) if(!T)exit(OVERFLOW) CreateBiTree(T->lchild) CreateBiTree(T->rchild) return OK. Status DestroyBiTree( BiTree&T)//销毁以T为根结点的树,注意T各子孙结点也要释放 if(T) Destroy Bi Tree(T->child) DestroyBi Tree(T->rchild) TENULL int TreeDepth(BiTree T)I if(T==NULL)d=0 el d1=TreeDepth(T->lchild) d2=Tree Depth(T->rchild) d=d1>=d2?d1+1: d2+1 t Node Count( BiTree T)i /递归法统计所有结点的个数 int n

//头文件包含 #include #include #include //函数状态码定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define INFEASIBLE -2 #define NULL 0 typedef int Status; //以下为二叉树的类型定义及创建、销毁、遍历、求树深、求结点数、叶结点数、复制、左右互换、查找、定 位双亲、删除、凹式输出等操作实现-------- //树中元素类型定义与二叉链表存储结构定义 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; Status CreateBiTree(BiTree &T){//先序创建二叉树各结点，注意输入时空指针不要丢 TElemType e; scanf("%c",&e); if(e==' ')T=NULL; else{ T=(BiTree)malloc(sizeof(BiTNode)); if(!T)exit(OVERFLOW); T->data=e; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } Status DestroyBiTree(BiTree &T)//销毁以T为根结点的树，注意T各子孙结点也要释放 { if(T){ DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); T=NULL; } return OK; } int TreeDepth(BiTree T){ int d,d1,d2; if(T==NULL)d=0; else { d1=TreeDepth(T->lchild); d2=TreeDepth(T->rchild); d=d1>=d2?d1+1:d2+1; } return d; } int NodeCount(BiTree T){ //递归法统计所有结点的个数 int n;

if (T==NULL)n=0 else n=l+Node Count(T->lchild)+Node Count(T->rchild) return n int LeafCount(BiTree T)i /递归法统计叶子结点的个数 int n if(T==NULL)n=0 else if(T->lchild==NULL&&T->rchild=NULL)n=l else n=LeafCount( T->lchild)+LeafCount(T->rchild) return n Status PrintTElem(TElem Type e)i intf("%c",e) return OK Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType)) if(T) (*visit)(T->data) PreOrderTraverse(T->lchild, (*visit)) PreOrderTraverse(T-rchild, (*visit)) re Status InOrderTraverse( BiTree T, Status(*visit)(TElem Type)) if(T)I InOrder Traverse(T->Child, (*visit)) InOrderTraverse(T->rchild, (*visit)) return Status Pos tOrderTraverse(BiTree T, Status(*visit)(TElemType)) f(T){ PostOrderTraverse(T-lchild,(*visit)) PostOrderTraverse(T->rchild, (*visit)) *visit)(T->data) return OK. int PreOrder LeafCount(BiTree T, int &count) /基于先序遄历求叶结点数, count用作计数器,初值为。函数返回值为叶结点数。实际将先序遍历过程中 的 visIt函数变为判断当前结点是否为叶子节点、是则加的操作即可 if(!T)return coun f(!T->lchild&&!T->rchild)++count PreOrder LeafCount(T->lchild, count) PreOrder LeafCount(T->rchild, count) return coun Status Copy BiTree( BiTree t, BiTree&x)/复制树T得到树x,T保持不变 if(T)X=NULL

if(T==NULL)n=0; else n=1+NodeCount(T->lchild)+NodeCount(T->rchild); return n; } int LeafCount(BiTree T){ //递归法统计叶子结点的个数 int n; if(T==NULL)n=0; else if(T->lchild==NULL&&T->rchild==NULL)n=1; else n=LeafCount(T->lchild)+LeafCount(T->rchild); return n; } Status PrintTElem(TElemType e){ printf("%c",e); return OK; } Status PreOrderTraverse(BiTree T,Status(*visit)(TElemType)) { if(T){ (*visit)(T->data); PreOrderTraverse(T->lchild,(*visit)); PreOrderTraverse(T->rchild,(*visit)); } return OK; } Status InOrderTraverse(BiTree T,Status(*visit)(TElemType)) { if(T){ InOrderTraverse(T->lchild,(*visit)); (*visit)(T->data); InOrderTraverse(T->rchild,(*visit)); } return OK; } Status PostOrderTraverse(BiTree T,Status(*visit)(TElemType)) { if(T){ PostOrderTraverse(T->lchild,(*visit)); PostOrderTraverse(T->rchild,(*visit)); (*visit)(T->data); } return OK; } int PreOrder_LeafCount(BiTree T,int &count){ //基于先序遍历求叶结点数，count用作计数器,初值为。函数返回值为叶结点数。实际将先序遍历过程中 的visit函数变为判断当前结点是否为叶子节点、是则加的操作即可 if(!T)return count; else{ if(!T->lchild&&!T->rchild)++count; PreOrder_LeafCount(T->lchild,count); PreOrder_LeafCount(T->rchild,count); return count; } } Status CopyBiTree(BiTree T,BiTree &X){//复制树T得到树X，T保持不变 if(!T)X=NULL; else{

X=(BiTree)malloc(sizeof(BiTNode)) f(!Xexit(OVERFLOW) X->data=T->data CopyBiTree(T->lchild, X->lchild) CopyBiTree(T->rchild, X->rchild) Status ExchangeBi Tree(BiTree&T){/将树T各结点的左右孩子互换 BiTree temp if(T)I temp=T->lchild T-Ichild=T->rchild rchild= ExchangeBi Tree(T->lchild) ExchangeBiTree(T->rchild) Status Locate Node(BiTree t, TElemType x, BiTree &p)i //在树T中查找(按先序)第一个结点值等于x的结点,若找到则函数返回TRUE,p带回该结点的地址;若 找不到则函数返回 FALSE,p赋值为NULL if(!T){p=NUL; return False;}//树T为空则p赋空且返回 FALSE else if(T->data=x)p=T: return TRUE: I else if( LocateNode(T-> Child,x,p) return TRUE;/搜索左子树 else if( LocateNode(T- rchild,x,p) return TrUE;//左子树中找不到再搜索右子树 else p=NULL: return FALSE: I Status LocateParent(Bi Tree T, TElemType x, BiTree &parent_p, int &LR) /己知树T中存在某结点值等于x,定位到该结点的双亲结点,若双亲存在(说明x结点非根结点)则 parent p 带回双亲位置,flag为代表是双亲的左孩子,为代表是双亲的右孩子,同时函数返回TRUE:否则函数返回 FALSE if(T->data=x) parent p=NULL; return FAlse;}//值等于x的结点是根结点,无双亲 if(T->lchild! =NULL&&T->Ichild->data==x)parent_p=T: LR=0; return TRUE; else if (T->rchild! =NULL&&T->rchild->data==x)parent_p=T: LR=l: return TRUE: K else f if(T->lchild!=NULL&&LocateParent(T->Child, x, parent p, LR))return TRUE else if(T->rchild! =NULL&&LocateParent(T->rchild, x, parent p, LR))return TRUE else parent_p=NULL; return FALSE; H Status DeleteChild(BiTree &T, TElemType x)I 删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK,若不存在x结点返回EROR BiTNode p, *parent_ p int LR if( LocateNode(T,x,p){//若树中存在结点x if( LocateParent(T,x, parent_p,LR)/若存在双亲,即x非根结点 if (LR==)DestroyBiTree(parent_p->lchild) else if(LR=1)DestroyBiTree(parent_p->rchild) else Destroy BiTree(T)://若x为根结点,不存在双亲,则删除整颗树,不可直接写T=NULL,为何? return ok

X=(BiTree)malloc(sizeof(BiTNode)); if(!X)exit(OVERFLOW); X->data=T->data; CopyBiTree(T->lchild,X->lchild); CopyBiTree(T->rchild,X->rchild); } return OK; } Status ExchangeBiTree(BiTree &T){//将树T各结点的左右孩子互换 BiTree temp; if(T){ temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; ExchangeBiTree(T->lchild); ExchangeBiTree(T->rchild); } return OK; } Status LocateNode(BiTree T, TElemType x,BiTree &p){ //在树T中查找(按先序)第一个结点值等于x的结点，若找到则函数返回ＴＲＵＥ,p带回该结点的地址;若 找不到则函数返回ＦＡＬＳＥ ，p赋值为NULL if(!T){ p=NULL;return FALSE;}//树T为空则p赋空且返回FALSE else if(T->data==x){p=T;return TRUE;} else { if(LocateNode(T->lchild,x,p))return TRUE;//搜索左子树 else if(LocateNode(T->rchild,x,p))return TRUE;//左子树中找不到再搜索右子树 else {p=NULL;return FALSE; } } } Status LocateParent(BiTree T,TElemType x,BiTree &parent_p,int &LR){ //已知树T中存在某结点值等于x，定位到该结点的双亲结点,若双亲存在（说明x结点非根结点）则parent_p 带回双亲位置，flag为代表是双亲的左孩子，为代表是双亲的右孩子，同时函数返回ＴＲＵＥ；否则函数返回 FALSE if(T->data==x){parent_p=NULL;return FALSE;}//值等于x的结点是根结点，无双亲 else{ if(T->lchild!=NULL&&T->lchild->data==x){parent_p=T;LR=0;return TRUE;} else if(T->rchild!=NULL&&T->rchild->data==x){parent_p=T;LR=1;return TRUE;} else{ if(T->lchild!=NULL&&LocateParent(T->lchild,x,parent_p,LR))return TRUE; else if(T->rchild!=NULL&&LocateParent(T->rchild,x,parent_p,LR))return TRUE; else {parent_p=NULL;return FALSE;} } } } Status DeleteChild(BiTree &T,TElemType x){ //删除树T中以x为根结点的子树,若存在x结点则删除成功后返回OK，若不存在x结点返回ERROR; BiTNode *p,*parent_p; int LR; if(LocateNode(T,x,p)){//若树中存在结点x if(LocateParent(T,x,parent_p,LR)){//若存在双亲，即x非根结点 if(LR==0)DestroyBiTree(parent_p->lchild); else if(LR==1)DestroyBiTree(parent_p->rchild); } else DestroyBiTree(T);//若x为根结点，不存在双亲,则删除整颗树，不可直接写T=NULL，为何？ return OK; } else

return ErrOR 以下为孩子兄弟表示法存储的树或森林的类型定义及树的相关操作实现 typedef struct CSNodet TElemType data struct CSNode *firstchild struct CSNode * nextsibling I CSNode, *sTRe Status BiTreetoTreeorForest(BiTree BiT, CSTree &T)I ∥/根据已经存在的二叉树BiT转换得到孩子兄弟法表示的树或者森林T,原二叉树BiT保持不变。注意思考 何时得到树,何时得到森林 if(BiT==NULL)T=NULL T=(CSTree)malloc(sizeof(CSNode)) if(!T)exit(OVERFLOW) T->data=BiT->data BiTreetoTreeor Forest(BiT->lchild, T->firstchild) BiTreetoTreeorForest( BiT->rchild, T->nextsibling) return OK: Status PostRoot Traverse(CSTree T, Status (*visit)(TElem Type))i 后根序遍历树T(对森林则是中序遍历),相当于中序遍历二叉链表存储结构 if(T) Post RootTraverse(T->firstchild, (*visit)) (*visit)(T->data) Post RootTraverse(T->nextsibling, (visit)) retu int Treeor Depth( STRee T){/求树或森林的深度 int d dl. d if(!T)d=0 d1=TreeorFores Depth(T->firstchild) d2=TreeorForest Depth (T->nextsibling) d=(dl+1)>d2?dl+1:d2 return d void PrintBiTree(BiTree T, int level)( /仿照题集题凹式打印树的形式打印二叉树 /注意是逐行打印,采用先序,凹入深度由结点所在层次控制,根结点位于第层,故最初 level为 if(Ti /先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(1evel-1)*4个空格 for (int i=l: idata) PrintBiTree(T->lchild, level+1) PrintBiTree(T->rchild, level+1) void PrintTree(STRee T, int level)[ /按题集题凹式打印树 /注意是逐行打印,采用先根序,凹入深度由结点所在层次控制,根结点位于第层,故最初 level为 if(T)i /先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(1evel-1)*4个空格

return ERROR; } //-------------------以下为孩子兄弟表示法存储的树或森林的类型定义及树的相关操作实现 ------------------------------------- typedef struct CSNode{ TElemType data; struct CSNode *firstchild; struct CSNode *nextsibling; }CSNode,*CSTree; Status BiTreetoTreeorForest(BiTree BiT,CSTree &T){ //根据已经存在的二叉树BiT转换得到孩子兄弟法表示的树或者森林T，原二叉树BiT保持不变。注意思考 何时得到树，何时得到森林 if(BiT==NULL)T=NULL; else{ T=(CSTree)malloc(sizeof(CSNode)); if(!T)exit(OVERFLOW); T->data=BiT->data; BiTreetoTreeorForest(BiT->lchild,T->firstchild); BiTreetoTreeorForest(BiT->rchild,T->nextsibling); } return OK; } Status PostRootTraverse(CSTree T,Status (*visit)(TElemType)){ //后根序遍历树T(对森林则是中序遍历），相当于中序遍历二叉链表存储结构 if(T){ PostRootTraverse(T->firstchild,(*visit)); (*visit)(T->data); PostRootTraverse(T->nextsibling,(*visit)); } return OK; } int TreeorForestDepth(CSTree T){//求树或森林的深度 int d,d1,d2; if(!T)d=0; else{ d1=TreeorForestDepth(T->firstchild); d2=TreeorForestDepth(T->nextsibling); d=(d1+1)>d2?d1+1:d2; } return d; } void PrintBiTree(BiTree T,int level){ //仿照题集题凹式打印树的形式打印二叉树 //注意是逐行打印,采用先序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为 if(T){ //先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格 for(int i=1;idata); PrintBiTree(T->lchild,level+1); PrintBiTree(T->rchild,level+1); } } void PrintTree(CSTree T,int level){ //按题集题凹式打印树 //注意是逐行打印,采用先根序,凹入深度由结点所在层次控制,根结点位于第层，故最初level为 if(T){ //先根据当前结点所处层次打印若干空格以缩进,每层所尽量为(level-1)*4个空格

for (int i=l: idata) PrintTree(T->firstchild, level+1) PrintTree(T->nextsibling, level) //以下非课程设计要求部分,可作复习用// 非递归实现树的遍历时需用到栈,故此处将顺序栈的定义及实现复制过来,不过栈元素类型需改变为 指向树的结点的指针类型 BiTree //元素类型与顺序栈类型声明 #define STACK INIt size 100 #define STACK INCrement 10 typedef BiTree ElemType;// BiTree等同于 BiNOde*,说明栈中的元素类型为指向树中结点的指针类型 typedef struct f ElemType base ElemType top int stacksize I SqStack ∥/顺序栈基本操作及其实现 Status InitStack(SqStack &S) /初始化一个顺序栈用S带回 S base=(Elem Type *)malloc(STACK INIT SIZE*sizeof(ElemType)) if(!S base)return ERROR S. stacksize=STACK INIT SIZE return OK. Status DestroyStack(SqStack &S) //销毁一个顺序栈 free(S base) S base=NULL S. top=NULL: s. stacksize=0: Status Clear Stack(SqStack &S)I //将一个顺序栈置空 Status Push(SqStack &S, ElemType e)( /向栈顶压入一个新元素 if((S.top-S.base)==S. stacksize){//当前栈满则重新为栈分配空间 S base=(ElemType *realloc(S base, (S stacks ize+STACKINCREMENT)*sizeof(Elem Type)) f(!S base)return ERROR S. top=S base+S. stacksize; S. stacksizetESTACKINCREMENT return OK Status Pop(SqStack &S, ElemType &e)I /栈顶元素出栈并用e带回其值

for(int i=1;idata); PrintTree(T->firstchild,level+1); PrintTree(T->nextsibling,level); } } //以下非课程设计要求部分，可作复习用// //------非递归实现树的遍历时需用到栈，故此处将顺序栈的定义及实现复制过来，不过栈元素类型需改变为 指向树的结点的指针类型BiTree--- //元素类型与顺序栈类型声明 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef BiTree ElemType;//BiTree等同于BiTNode*，说明栈中的元素类型为指向树中结点的指针类型 typedef struct{ ElemType * base; ElemType * top; int stacksize; }SqStack; //顺序栈基本操作及其实现 Status InitStack(SqStack &S){ //初始化一个顺序栈用S带回 S.base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if(!S.base)return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } Status DestroyStack(SqStack &S){ //销毁一个顺序栈 free(S.base); S.base=NULL; S.top=NULL; S.stacksize=0; return OK; } Status ClearStack(SqStack &S){ //将一个顺序栈置空 S.top=S.base; return OK; } Status Push(SqStack &S,ElemType e){ //向栈顶压入一个新元素 if((S.top-S.base)==S.stacksize){ //当前栈满则重新为栈分配空间 S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S.base)return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; } Status Pop(SqStack &S,ElemType &e){ //栈顶元素出栈并用e带回其值

if(S top==S base)return ERROR =*(S.top-1) --S. top: Status Set TopElem(SqStack &S, ElemType e) ∥/将栈顶元素的值修改为e,书中未设此操作,可根据需要新设 if(S top==S base)return ERROR *(S top-1)=e Status StackEmpty(SqStack S)I /栈空则返回TRUE,否则返回 FALSE if(S top==S base)return TRUE else return false int StackLength(SqStack S)f /返回栈中元素的个数 return(S top-S base) Status GetTop(SqStack S, Elem Type &e)f //用e带回栈顶元素的值 if(S top==S base)return ERROR (S top-1) return OK Status Print Elem(ElemType e)I //用于输出一个元素,根据元素类型的不同,此函数需适时改变 printf("%c", e->data) return OK Status StackTraverse(SqStack S, Status (*visit)(ElemType))( ∥/从栈底元素到栈顶元素依次执行 visIt函数,通常用于输出栈中元素 ElemType *p=S bas if(S.base==S.top) printf("空栈\n") hile(pChild Pop(s, p) (*visit)(p) p=p->rchild

if(S.top==S.base)return ERROR; e=*(S.top-1); --S.top; return OK; } Status SetTopElem(SqStack &S,ElemType e){ //将栈顶元素的值修改为e，书中未设此操作，可根据需要新设 if(S.top==S.base)return ERROR; *(S.top-1)=e; return OK; } Status StackEmpty(SqStack S){ //栈空则返回TRUE ，否则返回FALSE if(S.top==S.base)return TRUE; else return FALSE; } int StackLength(SqStack S){ //返回栈中元素的个数 return(S.top-S.base); } Status GetTop(SqStack S,ElemType &e){ //用e带回栈顶元素的值 if(S.top==S.base)return ERROR; e=*(S.top-1); return OK; } Status PrintElem(ElemType e){ //用于输出一个元素，根据元素类型的不同，此函数需适时改变 printf("%c",e->data); return OK; } Status StackTraverse(SqStack S,Status (*visit)(ElemType)){ //从栈底元素到栈顶元素依次执行visit函数，通常用于输出栈中元素 ElemType *p=S.base; if(S.base==S.top)printf("空栈\n"); else while(plchild; } Pop(S,p); (*visit)(p); p=p->rchild; } return OK; }

Status InOrderTraverse Non Recur 2 (BiTree T, Status (*visit)(ElemType))I //非递归中序遍历二叉树T /何时递归:根结点不空时将左孩子入栈作新根结点 /何时不递归:根结点为空时不递归,此后当前空根结点出栈,访问下一个栈顶元素并将其右孩子结点入 栈 /当栈中不含元素时整个树遍历完毕 InitStack(S) BiNOde*p;//实际 BiTree与 BiNOde*等价,具体根据上下文含义确定用谁,如根结点可声明为 BiTree 类型,指向结点的指针可声明为 BiNOde*类型 if(T){ printf("空树"); return ERROR;} else Push(S, T) while(!StackEmpty(S)) while( Get Top(S,p)&&p)Push(S,p-> Child;/p的左孩子入栈,直到入栈元素为空指针,此循 环后栈顶元素为NULL,相当于走到左子树外 Pop(S,p)://左子树是空树,对应的空指针出栈,下一步将访问根结点 if(! StackEmpty(S){//若栈中尚有元素代表未遍历完,下面访问栈顶根结点,之后栈顶跟结 点的右孩子入栈 Pop(s, p) (=*visit)(p) Push(S, p>rchild void main o BiTree bit CreateBiTree(BiT rinf("二叉树BiT的先序输出序列为:") PreOrderTraverse(BiT. PrintTElem printf("\n") printf("二叉树BiT的中序输出为:") InOrderTraverse(BiT, PrintTElem): printf("\") rinf("二叉树BiT后序输出为:") PostOrderTraverse(biT. PrintTElem printf("\n\n") rinf("二叉树BiT树深:%dn", TreeDepth(BiT) printf("二叉树BiT结点总数:%dn", Nodecount(BiT)) printf("递归求得二叉树BiT叶子结点数为:%d\n", LeafCount(BiT) int count=o printf("基于先序遍历求二叉树Bi叶子结点数为:%dnn”, PreOrder Leafcount(BiT, count)) TElemType x BiTree p, parent p;// BiTree等价于 BinOde* rinf("输入要查找的元素,元素值前加一个空格:");/此处在%前加一个空格,因在主函数第一个输入语 句执行时用户最后会输入一个回车,此处不加空格则x变为回车,不会再等待输入.若结点元素为整型则无此问 scanf("%c",&x);/此处在%前加一个空格,因在主函数第一个输入语句执行时用户最后会输入一个回车, 此处不加空格则x变为回车,不会再等待输入.若结点元素为整型则无此问题 if(LocateNode(BiT, x, p)=TRUE)( printf("元素%c在BiT中,",p->data f (LocateParent(BiT, x, parent p, LR)) printf("%c结点的双亲结点为%c,",x, parent_p->data) ifLR=0) printf("是双亲的左孩子n") else printf("是双亲的右孩子\n")

Status InOrderTraverse_NonRecur_2(BiTree T,Status (*visit)(ElemType)){ //非递归中序遍历二叉树T //何时递归:根结点不空时将左孩子入栈作新根结点, //何时不递归:根结点为空时不递归，此后当前空根结点出栈，访问下一个栈顶元素并将其右孩子结点入 栈 //当栈中不含元素时整个树遍历完毕 SqStack S; InitStack(S); BiTNode* p; //实际BiTree与BiTNode*等价，具体根据上下文含义确定用谁，如根结点可声明为BiTree 类型，指向结点的指针可声明为BiTNode*类型 if(!T){printf("空树");return ERROR;} else{ Push(S,T); while(!StackEmpty(S)){ while( GetTop(S,p)&&p)Push(S,p->lchild);//p的左孩子入栈，直到入栈元素为空指针，此循 环后栈顶元素为NULL，相当于走到左子树外 Pop(S,p);//左子树是空树，对应的空指针出栈，下一步将访问根结点 if(!StackEmpty(S)){ //若栈中尚有元素代表未遍历完,下面访问栈顶根结点，之后栈顶跟结 点的右孩子入栈 Pop(S,p); (*visit)(p); Push(S,p->rchild); } } return OK; } } void main() { BiTree BiT; CreateBiTree(BiT); printf("二叉树BiT的先序输出序列为："); PreOrderTraverse(BiT,PrintTElem); printf("\n"); printf("二叉树BiT的中序输出为："); InOrderTraverse(BiT,PrintTElem); printf("\n"); printf("二叉树BiT后序输出为："); PostOrderTraverse(BiT,PrintTElem); printf("\n\n"); printf("二叉树BiT树深：%d\n",TreeDepth(BiT)); printf("二叉树BiT结点总数：%d\n",NodeCount(BiT)); printf("递归求得二叉树BiT叶子结点数为：%d\n",LeafCount(BiT)); int count=0; printf("基于先序遍历求二叉树BiT叶子结点数为:%d\n\n",PreOrder_LeafCount(BiT,count)); TElemType x; BiTree p,parent_p; //BiTree等价于BiTNode * int LR; printf("输入要查找的元素,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语 句执行时用户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问 题 scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车， 此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题 if(LocateNode(BiT,x,p)==TRUE){ printf("元素%c在BiT中，",p->data); if(LocateParent(BiT,x,parent_p,LR)){ printf("%c结点的双亲结点为%c，",x,parent_p->data); if(LR==0)printf("是双亲的左孩子\n"); else printf("是双亲的右孩子\n"); }

else printf("‰c结点是树的根结点,不存在双亲结点n"); else printf("元素% printf("\n") intf("下面重新读入x并删除以x为根的子树n") rinf("输入x,元素值前加一个空格:");/此处在%c前加一个空格,因在主函数第一个输入语句执行时用 户最后会输入一个回车,此处不加空格则x变为回车,不会再等待输入若结点元素为整型则无此问题 scanf("%c",&x)://此处在%c前加一个空格,因在主函数第一个输入语句执行时用户最后会输入一个回车 此处不加空格则x变为回车,不会再等待输入.若结点元素为整型则无此问题 if( DeleteChild (BiT,x)= FERROR) printf(x不存在1n") printf("删除BiT中以x为根的子树后BiT的先序输出序列为:") eOrderTraverse(BiT, PrintTElem) intf("删除BiT中以x为根的子树后Bi的中序输出序列为:") InOrderTraverse(BiT, PrintTElem): rinf("Ⅶn"); printf("删除BiT中以x为根的子树后BiT的后序输出序列为:") PostOrderTraverse(BiT. PrintTElem) Tree T printf("以下根据二叉树BiT构造相应的孩子兄弟法存储的树或森林T.Ⅶn"); rinf("源二叉树凹式输出为:n") intBiTree (BiT, 1) BiTreetoTreeorForest(Bit, T) printf("由源二叉树转换得到的树或森林为:1n") entRee(T, 1) printf("构造好的树的后跟输出序列或森林的中序输出序列为:") PostRoot Traverse(T, PrintTEl printf("构造好的树的深度为:%d\nn", Treeor Forest Depth(T) BiTree X printf(以下先复制BiT得到X,后将树x的各结点的左右孩子互换:\n") CopyBiTree(Bit, X) ExchangeBiTree (X) printf("互换完毕,以下进行结果测试:1n") rinf("X先序输出为:") reOrderTraverse(X, PrintTElem) printf( \n") printf("X中序输出为:") InOrder Traverse(X, PrintTElem) printf(\") printf("X后序输出为:") PostOrderTraverse(X, PrintTElem) rinf(\n") printf("x树深:%d\n", TreeDepth(X) printf("X结点总数:%dn”, Node Count(X) printf("递归求得X叶子结点数为:%d\n", LeafCount(x)) printf("非递归第一种方法中序遍历树BiT得:") InOrderTraverse NonRecur 1(BiT, PrintElem) printf( \n") printf("非递归第二种方法中序遍历树BiT得:") InOrder Traverse NonRecur 2(BiT. PrintElem) printf("\n\n") DestroyBiTree (BiT) rinf("销毁后的树先序输出为:n") PreOrderTraverse(BiT, PrintTElem rinf("销毁后树深%d\n", TreeDepth(BiT)); printf("递归求结点总数:%d\n", Node Count(BiT))

else printf("%c结点是树的根结点，不存在双亲结点\n"); } else {printf("元素%c不在BiT中\n",x);} printf("\n"); printf("下面重新读入x并删除以x为根的子树\n"); printf("输入x,元素值前加一个空格：");//此处在%c前加一个空格，因在主函数第一个输入语句执行时用 户最后会输入一个回车，此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题 scanf(" %c",&x);//此处在%c前加一个空格，因在主函数第一个输入语句执行时用户最后会输入一个回车， 此处不加空格则x变为回车，不会再等待输入.若结点元素为整型则无此问题 if(DeleteChild(BiT,x)==ERROR)printf("x不存在\n"); printf("删除BiT中以x为根的子树后BiT的先序输出序列为："); PreOrderTraverse(BiT,PrintTElem); printf("\n"); printf("删除BiT中以x为根的子树后BiT的中序输出序列为："); InOrderTraverse(BiT,PrintTElem); printf("\n"); printf("删除BiT中以x为根的子树后BiT的后序输出序列为："); PostOrderTraverse(BiT,PrintTElem); printf("\n\n"); CSTree T; printf("以下根据二叉树BiT构造相应的孩子兄弟法存储的树或森林T.\n"); printf("源二叉树凹式输出为：\n"); PrintBiTree(BiT,1); BiTreetoTreeorForest(BiT,T); printf("由源二叉树转换得到的树或森林为：\n"); PrintTree(T,1); printf("构造好的树的后跟输出序列或森林的中序输出序列为:"); PostRootTraverse(T,PrintTElem); printf("\n"); printf("构造好的树的深度为:%d\n\n",TreeorForestDepth(T)); BiTree X; printf("以下先复制BiT得到X，后将树X的各结点的左右孩子互换:\n"); CopyBiTree(BiT,X); ExchangeBiTree(X); printf("互换完毕，以下进行结果测试：\n"); printf("X先序输出为："); PreOrderTraverse(X,PrintTElem); printf("\n"); printf("X中序输出为："); InOrderTraverse(X,PrintTElem); printf("\n"); printf("X后序输出为："); PostOrderTraverse(X,PrintTElem); printf("\n"); printf("X树深：%d\n",TreeDepth(X)); printf("X结点总数：%d\n",NodeCount(X)); printf("递归求得X叶子结点数为：%d\n",LeafCount(X)); printf("非递归第一种方法中序遍历树BiT得:"); InOrderTraverse_NonRecur_1(BiT,PrintElem); printf("\n"); printf("非递归第二种方法中序遍历树BiT得:"); InOrderTraverse_NonRecur_2(BiT,PrintElem); printf("\n\n"); DestroyBiTree(BiT); printf("销毁后的树先序输出为：\n"); PreOrderTraverse(BiT,PrintTElem); printf("销毁后树深%d\n",TreeDepth(BiT)); printf("递归求结点总数：%d\n",NodeCount(BiT));