二叉树及其上基本操作.doc

#include#include#define N 10;template struct BinTreeNode /二叉树结点类定义T data;BinTreeNode *left,*right;BinTreeNode():leftChild(NULL),rightChild(NULL)BinTreeNode(T &x,BinTreeNode *l=NULL,BinTreeNode *r=NULL):data(x),left(l),right(r);template class BinTreepublic:BinTree():root(NULL)BinTree(T value=0):RefValue(value),root(NULL)BinTree(BinTree &s);BinTree()Destroy(root);BinTreeNode Getroot()constreturn root; /取根bool Isempty()return (root=NULL)?true:false;BinTreeNode * Parent(BinTreeNode *current); /寻找父结点BinTreeNode *LeftChild(BinTreeNode *current) /寻找左右子结点return (current!=NULL)?current-left:NULL;BinTreeNode *RightChild(BinTreeNode *current)return (current!=NULL)?current-right:NULL;BinTreeNode *Setleft(BinTreeNode *current)left=current;/设置左右子结点BinTreeNode *Setright(BinTreeNode *current)right=current;BinTreeNode *Create(); /创建树void Preorder(BinTreeNode *t); /先根遍历void Inorder(BinTreeNode *t); /中根遍历void Postorder(BinTreeNode *t); /后根遍历bool Find(T &x); /查找符合数据域条件的结点 void Destroy(BinTreeNode &subtree); /删除子树void Del(BinTreeNode *p); void out(BinTreeNode *t); /以表格形式输出二叉树private:BinTreeNode *root;T RefValue;template BinTreeNode *BinTree:Parent(BinTreeNode *current) /父结点if(current=NULL|Isempty() return NULL;if(root-left=current|root-right=current) return root;BinTreeNode *q;q=Parent(root-left);if(q!=NULL) return q;return q=Parent(root-right);template bool BinTree:Find(BinTreeNode *t,T &x) /符合数据域条件的结点if(Isempty() return false;if(t-data=x) return true;BinTreeNode *q; q=Find(t-left,x); if(q!=NULL) return q;return q=Find(t-right,x);template void BinTree:Destroy(BinTreeNode &subtree) /删除节点及子树if(subtree=NULL) exit(1);if(subtree=root) Del(root);root=NULL;exit(1);BinTreeNode *p=subtree;BinTreeNode *q;q=Parent(p);if(q-left=p) q-left=NULL;if(q-right=p) q-right=NULL;Del(p);template void BinTree:Del(BinTreeNode *p)if(p=NULL)exit(0);Del(p-left);Del(p-right);delete p;template void BinTree:Preorder(BinTreeNode *t) /前序遍历if(t=NULL) coutEmpty Tree!endl;exit(1);coutdataleft);Preorder(t-right);template void BinTree:Inorder(BinTreeNode *t) /中序遍历if(t=NULL) coutEmpty Tree!left);coutdataright);template void BinTree:Postorder(BinTreeNode *t) /后序遍历if(t=NULL) coutEmpty Tree!left);Postorder(p-right);coutdata ;template BinTreeNode *BinTree:Create(istream &in,BinTree Node& subtreee)BinTreeNode * p=subtree;t item;if(!in.eof()initem;if(item!=RefValue)subtree=new BinTreeNode(item);if(subtree=NULL)cout存储分配错误！left); Create(in,subtree-right); else subtree=NULL;return p;temp