数据结构库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<stdlib. h> Include<stdio. h> #include<malloc. h> 函数状态码定义 #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<stdlib.h> #include<stdio.h> #include<malloc.h> //函数状态码定义 #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