二叉树及其上基本操作

1、#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):RefVa

2、lue(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;BinTree

3、Node *RightChild(BinTreeNode *current)return (current!=NULL)?current-right:NULL;BinTreeNodevT * Setleft(BinTreeNodevT *curre nt)left=curre nt;/设置左右子结点BinTreeNode *Setright(BinTreeNode *current)right=current;BinTreeNode *Create();/创建树void Preorder(BinTreeNode *t);/创建树void Inorder(BinTreeNode *t);/中根遍

4、历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

5、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;retu

6、rn 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);/符合数据域条件的结/删除节点及子树/符合数据域条件的结/删除节点及子树void BinTr

7、ee: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 B

8、inTree:Postorder(BinTreeNode *t)if(t=NULL) coutEmpty Tree!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)coutvv存储分配错误！ vvendl;exit(1);Create(in,subtree-left);Create(in,subtree-right);else subtree=NULL;return p; template vclass