数据结构实验二叉树C++完整代码.doc

#include using namespace std; const int MAXSIZE = 100 ;template struct BiNode /二叉链表结点T data;/数据域BiNode* lch;/左指针域BiNode* rch;/右指针域;template class BiTree /二叉树的实现 public: void Create (BiNode * &R,T data ,int i);/创建二叉树 void Release(BiNode *R); /释放二叉树 BiNode *root; /根节点 BiTree(T a)Create(root,a,1);/构造函数 BiNode * Getroot()return root;/根节点地址返回 void PrintWay(T data, T a); void PreOrder(BiNode *R); /前序遍历 void InOrder(BiNode *R); /中序遍历 void LevelOrder(BiNode *R);/层序遍历 void PostOrder(BiNode *R); /后序遍历 BiTree();/析构函数 int GetDepth(BiNode *R,int d);/求二叉树深度 void GetPath(T x,BiNode*R);/求指定结点到根结点的路径;template void BiTree :Create (BiNode * &R,T data ,int i)/顺序结构存储二叉链表/i表示位置，从1开始if(datai-1!=0)R=new BiNode;/创建根节点R-data=datai-1;Create(R-lch,data,2*i);/创建左子树Create(R-rch,data,2*i+1);/创建右子树else R=NULL;template void BiTree :PreOrder(BiNode *R)/前序遍历的实现if(R!=NULL)coutdata;/访问结点PreOrder(R-lch);/遍历左子树PreOrder(R-rch);/遍历右子树template void BiTree :InOrder(BiNode *R)/中序遍历的实现if(R!=NULL)PreOrder(R-lch);/遍历左子树coutdata;/访问结点PreOrder(R-rch);/遍历右子树template void BiTree :PostOrder(BiNode *R)/后序遍历的实现if(R!=NULL)PreOrder(R-lch);/遍历左子树PreOrder(R-rch);/遍历右子树coutdata;/访问结点template void BiTree :LevelOrder(BiNode *R)/层序遍历的实现BiNode * queueMAXSIZE;/利用队列实现层序遍历int f = 0,r = 0;/初始化空队列if(R!=NULL)queue+r = R;while(f!=r)BiNode *p=queue+f;/队头元素出列coutdata;if(p-lch!=NULL)queue+r=p-lch;if(p-rch!=NULL)queue+r=p-rch;template void BiTree:Release(BiNode *R)/释放二叉树 if (R!=NULL) Release(R-lch);Release(R-rch); delete R; template BiTree:BiTree() /调用Release函数Release(root); template int BiTree:GetDepth(BiNode *R,int d) /求二叉树的深度 if (R=NULL) return d; if (R-lch=NULL) & (R-rch=NULL) return d+1; else int m = GetDepth(R-lch,d+1); int n = GetDepth(R-rch,d+1); return nm? n:m; template void BiTree:PrintWay(T data, T a)/打印路径 int x;for(int i=1;i100;i+)if(ai-1=data)/数组中各元素和指定元素比较、查找所在位置i x=i;break;cout该结点到根结点的路径为:endl;while(x!=0)coutax-1endl;x/=2;/子节点对应父节点编号void main() char bufMAXSIZE=j,u,s,t,l,o,v,e,u,f,o,r,e,v,e,r; BiTree Test(buf); BiNode * A = Test.Getroot(); cout前序遍历：; Test.PreOrder(A); coutendl; cout中序遍历：; Test.InOrder(A); coutendl; cout后续遍历：; Test.PostOrder(A); coutendl; cout层序遍历：; Tes