《二叉树-顺序》由会员分享，可在线阅读，更多相关《二叉树-顺序（19页珍藏版）》请在金锄头文库上搜索。
1、测试.cpp#include12.hvoid main()status i;int j;position p;TElemtype e;SqBiTree T,s;InitBiTree(T);CreateBiTree(T);coutp.levelp.order;e=Value(T,p);coute;Assign (T,p,e); /给p的位置赋为新值 e coutej;InsertChild(T,e,j,s);Print(T);coutp.levelp.orderj;DeleteChild(T,p,j);Print(T);ClearBiTree(T);cout#include#include#in
2、cludeusing namespace std;#define OK 1#define FALSE 0#define ERROR 0#define TRUE 1#define MAX_TREE_SIZE 100typedef int status;#define CHAR 1 /字符型#define CHAR 0/整型(二选一)#if CHARtypedef char TElemtype;TElemtype Nil= ;#elsetypedef int TElemtype;TElemtype Nil=0;#endiftypedef int QElemtype;#includeG:学习12年暑
3、假3 4队列3 4队列1.htypedef TElemtype SqBiTreeMAX_TREE_SIZE;struct positionint level,order;/结点的层。本层序号;status InitBiTree(SqBiTree T)int i;for(i=0;iTi;if(Ti=999)break;if(i!=0&T(i+1)/2-1=Nil&Ti!=Nil)cout=0;i-)if(Ti!=Nil)break;i+; doj+;while ( i=pow(2,j);return j;status Root(SqBiTree T, TElemtype &e)/初始条件：二叉树
4、T存在。操作结果：当T不空，用e返回T的根，返回OK；否则返回ERROR,e无意义if(BiTreeEmpty(T)return ERROR;elsee=T0;return OK;TElemtype Value (SqBiTree T, position e) /初始条件：二叉树T存在，e是T中某个节点（的位置）/操作结果： 返回e的结点处的值return Tint(pow (2,e.level-1)+e.order-2);status Assign (SqBiTree T,position e,TElemtype value)/初始条件：二叉树T存在，e是T中某个节点（的位置）/操作结果：给
5、处于位置e（层，本层序号）的结点赋新值valueint i=int(pow(2,e.level-1)+e.order-2);if(value!=Nil&(T(i+1)/2-1=Nil) /叶子不空但是双亲为空return ERROR;elseif(value=Nil&(Ti*2+1!=Nil|Ti*2+2!=Nil)/ 给双亲赋空值但是给叶子赋非空值return ERROR;Ti=value;return OK;TElemtype Parent(SqBiTree T,TElemtype e) /初始条件 ：二叉树T存在，e是T中的某个节点/操作结果：若e是T的非根结点，则返回 它的双亲，否则返
6、回空int i;if(T0=Nil)return Nil;for(i=1;iMAX_TREE_SIZE;i+)if(Ti=e)return T(i+1)/2-1;return Nil;TElemtype LeftChild(SqBiTree T,TElemtype e) /初始条件 ：二叉树T存在，e是T中某个结点/操作结果：返回e的左孩子若e无左孩子，则返回空int i;if(T0=Nil)return Nil;for(i=0;iMAX_TREE_SIZE;i+)if(Ti=e)return Ti*2+1;return Nil;TElemtype RightChild(SqBiTree T,
7、TElemtype e)/初始条件 ：二叉树T存在，e是T中某个结点/操作结果：返回e的右孩子若e无右孩子，则返回空int i;if(T0=Nil)return Nil;for(i=0;iMAX_TREE_SIZE;i+)if(Ti=e)return Ti*2+2;return Nil;TElemtype LeftSibiling(SqBiTree T,TElemtype e) /初始条件 ：二叉树T存在，e是T中某个结点/操作结果：返回e的右兄弟，若e是T的左孩子或无左兄弟，则返回 “空”int i;if(T0=Nil)/空树return Nil;for(i=1;iMAX_TREE_SIZE
8、;i+)if(Ti=e&i%2=0)return Ti-1;return Nil;TElemtype RightSibling(SqBiTree T, TElemtype e) /初始条件 ：二叉树T存在，e是T中某个结点/操作结果：返回e的右兄弟，若e是T的右孩子或无右兄弟，则返回 “空”int i;if(T0=Nil)return Nil;for(i=1;i=MAX_TREE_SIZE-1;i+)if(Ti=e&i%2)return Ti+1;return Nil;void Move (SqBiTree q,int j,SqBiTree T,int i) /把从q的j结点开始的子树移为从T
9、的i结点开始的子树if(q2*j+1!=Nil) /q的左子树不空Move (q,(2*j+1),T,(2*i+1);if(q2*j+2!=Nil)Move(q,(2*j+2),T,(2*i+2);Ti=qj;qj=Nil;status InsertChild(SqBiTree T,TElemtype p,status LR,SqBiTree c)/初始条件：二叉树T存在，p是T中某个结点的值，LR为0或1，非空二叉树c与T不/ 操作结果：根据LR为0或1插入c为T中p结点的左或右子树int j,k,i=0;for(j=0;jint(pow(2,BiTreeDepth(T)-1;j+) if(
10、Tj=p) /j为p的序号break;k=2*j+1+LR; /k为p的左或右孩子的序号if( Tk!=Nil) /p原来的左孩子或右孩子不空Move (T,k,T,2*k+2); /把从T的k结点开始的子树移为 T从k结点的 右子树开始的子树Move(c,i,T,k); /把从c的i结点开始的子树移为从T的k结点开始的子树return OK;status DeleteChild(SqBiTree T, position p,int LR) /初始条件：二叉树T存在，p指向T中某个结点 LR为/操作结果：根据LR为1或0删除T中所指结点的左或右子树int i;status k=OK;LinkQ
11、ueue q;InitQueue(q);i=(int)pow(2,p.level-1)+p.order-2;if(Ti=Nil)return ERROR;i=i*2+1+LR;while(k)if(T2*i+1!=Nil)/左结点不空EnQueue(q,2*i+1); /入队左节点的序号if(T2*i+2!=Nil)/右结点不空EnQueue(q,2*i+2); /入队右结点的序号Ti=Nil; /删除此结点k=DeQueue(q,i); /队列不空return OK;status (*VisitFunc)(TElemtype);void PreTraverse(SqBiTree T, int
12、 e)/先序遍历VisitFunc(Te); /遍历根结点if(T2*e+1!=Nil) /左子树不空PreTraverse(T,2*e+1); /先序遍历左子树if(T2*e+2!=Nil)PreTraverse(T,2*e+2);status PreOrderTraverse(SqBiTree T,status(*visit)(TElemtype)/初始条件：二叉树存在。visit是对结点操作的应用函数/操作结果：先序遍历T，对每个结点调用函数visit依次且仅依次VisitFunc=visit;if(!BiTreeEmpty(T)/树不空PreTraverse(T,0);coutendl
13、;return OK;void InTravere(SqBiTree T,int e)if(T2*e+1!=Nil) InTravere(T,2*e+1); /中序遍历左子树VisitFunc(Te); /访问根节点if(T2*e+2!=Nil) /右子树不空InTravere(T,2*e+2); /中序遍历右子树status InOrderTraverse(SqBiTree T, status (*visit)(TElemtype) /初始条件：二叉树存在，visit是对点的操作应用函数/操作结果：中序遍历T对每个结点调用函数visit一次且仅一次 一旦visit调用失败则操作失败Visit
14、Func=visit;if(!BiTreeEmpty(T)/InTravere(T,0);coutendl;return OK;void PostTraverse(SqBiTree T, int e)/if(T2*e+1!=Nil)/PostTraverse(T,2*e+1);if(T2*e+2!=Nil)PostTraverse(T,2*e+2);VisitFunc(Te);status PostOrderTraverse(SqBiTree T,status (*visit)(TElemtype) /初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果： 后续遍历T，对每个结点
15、调用函数visiit一次且仅一次一旦调用失败则返回VisitFunc=visit;if(!BiTreeEmpty(T)PostTraverse(T,0);coutendl;return OK;void LevelOrderTraver(SqBiTree T,status (*visit) (TElemtype) /层序遍历二叉树int i=MAX_TREE_SIZE-1,j;while(Ti=Nil)i-;/找到最后一个非空结点的序号for(j=0;j=i;j+)if(Tj!=Nil)visit(Tj);coutendl;void Print(SqBiTree T)/ 层序，按照本层序号输出二叉树int j,k;position p;TElemtype e;for(j=1;j=BiTreeDepth(T);j+) cout
