二叉树C++实验代码.doc

#include#includeusing namespace std;void visit (char c)coutc;struct BiTNodeint data;BiTNode *lchild,*rchild;BiTNode(char ch,BiTNode *left,BiTNode *right)data=ch;lchild=left;rchild=right;BiTNode();struct BiTreeBiTNode *root;BiTree()root=NULL;void PreOrderTraverse();void InOrderTraverse();void PostOrderTraverse();void InOrderTraverse2();BiTNode* SearchBST1(BiTNode *T, int key); void InsertBST1(BiTNode* &T, int e);private:void PreOrder(BiTNode *p);void InOrder(BiTNode *p);void PostOrder(BiTNode *p);void InOrder2(BiTNode *p);BiTNode* BiTree:SearchBST1(BiTNode *T, int key)if (T = NULL) return T;/ 查找不成功else if (key data) return SearchBST1(T-lchild, key);else if (key T-data) return SearchBST1(T-rchild, key);else return T;/ 查找成功 key=T-datavoid BiTree: InsertBST1(BiTNode* &T, int e) if (T=NULL) T=new BiTNode(e, NULL, NULL);else if (e data) InsertBST1(T-lchild, e);else if (e T-data) InsertBST1(T-rchild, e);int cntLeaf(BiTNode *p)if(p=NULL) return 0;int cnt=0;if(p-lchild=NULL&p-rchild=NULL)return 1;elsereturn cntLeaf(p-lchild)+cntLeaf(p-rchild);void BiTree:PreOrderTraverse()PreOrder(root);void BiTree:InOrderTraverse()InOrder(root);void BiTree:InOrderTraverse2()InOrder2(root);void BiTree:PostOrderTraverse()PostOrder(root);void BiTree:PreOrder(BiTNode *p)if(p=NULL) return;coutdata; PreOrder(p-lchild);PreOrder(p-rchild);void BiTree:InOrder(BiTNode *p)if(p=NULL) return;PreOrder(p-lchild);coutdata;PreOrder(p-rchild);void BiTree:InOrder2(BiTNode *p)if(p=NULL) return;PreOrder(p-rchild);coutdata;PreOrder(p-lchild);void BiTree:PostOrder(BiTNode *p)if(p=NULL) return;PostOrder(p-lchild);PostOrder(p-rchild);coutdata;BiTNode *CopyTree(BiTNode *T) if (T=NULL ) return NULL;BiTNode*l= CopyTree(T-lchild);/复制左子树BiTNode*r = CopyTree(T-rchild);/复制右子树BiTNode *newT=new BiTNode(T-data,l,r); return newT; int main()BiTree T;T.InsertBST1(T.root,10);T.InsertBST1(T.root,5); /T.PreOrderTraverse();/coutendl;T.InOrderTraverse();couten