二叉树-顺序.doc

测试.cpp#include12.h void main() status i; int j;position p;TElemtype e;SqBiTree T,s;InitBiTree(T);CreateBiTree(T);cout建立二叉树后，树空否？BiTreeEmpty(T)（1：是，0：否） 树的深度=BiTreeDepth(T)endl; i=Root(T,e); if(i) cout二叉树的根为：eendl; else cout树空，无根endl; cout层序遍历二叉树endl; LevelOrderTraver(T,visit); cout先序遍历二叉树endl; PreOrderTraverse(T,visit); cout中序遍历二叉树endl; InOrderTraverse(T,visit); cout后序遍历二叉树endl; PostOrderTraverse(T,visit); cout请输入待修改结点的层序号和本层序号p.levelp.order; e=Value(T,p); cout待修改的结点原值为：ee; Assign (T,p,e); /给p的位置赋为新值 e cout先序遍历二叉树endl; PreOrderTraverse(T,visit); cout结点e的双亲为Parent(T,e)左右孩子分别为 :; coutLeftChild(T,e),RightChild(T,e)左右兄弟分别为; coutLeftSibiling(T,e),RightSibling(T,e)endl; InitBiTree(s); cout建立右子树为空的树sendl; CreateBiTree(s); cout树s插入到树T中，请输入树T中s的双亲结点s为左（0）或右（0）子树：ej; InsertChild(T,e,j,s); Print(T); coutp.levelp.orderj; DeleteChild(T,p,j); Print(T); ClearBiTree(T); cout清空二叉树后，树空否BiTreeEmpty(T)树的深度=BiTreeDepth(T)endl; i=Root(T,e); if(i) cout二叉树的根为：eendl; else cout树空，无根endl; 12.h#include#include#include#includeusing 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年暑假34队列34队列1.htypedef TElemtype SqBiTreeMAX_TREE_SIZE;struct positionint level,order;/结点的层。本层序号 ;status InitBiTree(SqBiTree T)int i;for(i=0;iMAX_TREE_SIZE;i+)Ti=Nil; return OK; status CreateBiTree(SqBiTree T) /按照层次顺序输入二叉树中结点的值（字符型或者整型），构造顺序存储的二叉树Tint i=0; #if CHAR int l;char sMAX_TREE_SIZE;cout请按照层序输入二叉树中结点的值（字符），空格 表示空节点，节点数=MAX_TREE_SIZE:endl; gets(s); l=strlen(s); for(;i1;i+) Ti=si;if(i!=0&T(i+1)/2-1=Nil&Ti!=Nil) cout出现无双亲的非根结点Tiendl; exit(ERROR); #elsecout请按照层次顺序输入结点的值（整型），0表示空结点输入 999 结束节点数=MAX_TREE_SIZE:Ti; if(Ti=999) break; if(i!=0&T(i+1)/2-1=Nil&Ti!=Nil) cout出现无双亲的非根结点Tiendl; exit(ERROR); i+; while(i=0;i-) if(Ti!=Nil) break; i+; do j+; while ( i=pow(2,j); return j; status Root(SqBiTree T, TElemtype &e)/初始条件：二叉树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中某个节点（的位置）/操作结果：给处于位置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的非根结点，则返回 它的双亲，否则返回空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,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;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的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(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;LinkQueue 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 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;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调用失败则操作失败VisitFunc=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，对每个结点调用函数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-;/找到最后一个非空结点的序号