数据结构二叉树.doc

#include/#includemystring.h#include/#include/二叉链表结点的类定义using namespace std;templateclass binarytreenode/friend class binarytree;private:T info; binarytreenode * left; binarytreenode * right;public: /binarytreenode() binarytreenode(T ele)info=ele;left=NULL;right=NULL; binarytreenode(T ele,binarytreenode * l,binarytreenode * r)info=ele;left=l;right=r;T value()const; binarytreenode * leftchild()const; binarytreenode * rightchild()const;void setleftchild(binarytreenode *l); void setrightchild(binarytreenode *l);void setvalue(T val);/*templatebinarytreenode:binarytreenode()left=null;right=null;templatebinarytreenode:binarytreenode(T ele)info=ele;left=NULL;right=NULL;templatebinarytreenode:binarytreenode(T ele,binarytreenode * l,binarytreenode * r) info=ele;left=l;right=r;*/templateT binarytreenode:value()constreturn info;templatebinarytreenode * binarytreenode:leftchild()constreturn left;templatebinarytreenode * binarytreenode:rightchild()constreturn right;templatevoid binarytreenode:setleftchild(binarytreenode * l)left=l;templatevoid binarytreenode:setrightchild(binarytreenode * r)right=r;templatevoid binarytreenode:setvalue(T val)info=val;/二叉链表的类定义templateclass binarytreeprivate:binarytreenode * root;public:binarytree()root=NULL;binarytree()deletebinarytree(root);binarytreenode * Root()return root;binarytreenode * parent(binarytreenode * current);binarytreenode * leftsibling(binarytreenode * current);binarytreenode * rightsibling(binarytreenode * current);void creattree(T info);void creattree(T info,binarytree & lefttree,binarytree & righttree);/void creattree(mystring a);void deletebinarytree(binarytreenode * root);void preorder1(binarytreenode * root); /保存当前结点的前序周游void preorder(binarytreenode * root); /保存当前结点右孩子的前序周游void inorder(binarytreenode * root); void postorder(binarytreenode * root);void levelorder(binarytreenode * root);int deep(binarytreenode * current); /求出一个结点的深度 void numofleaf(binarytreenode * root,int & i); /叶子个数/void high(binarytreenode * root,int & i); /高度 void shadow(binarytreenode * root); /镜面影射 void commonp(binarytreenode * p,binarytreenode * q); /求两结点的最近的共同祖先;/找双亲templatebinarytreenode * binarytree:parent(binarytreenode * current)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;if(root=null|current=null)return null;while(!astack.isempty()|pointer)if(pointer)if(pointer.left=current|pointer.right=current)return pointer;astack.push(poiter);pointer=pointer.left;elsepointer=astack.top();astack.pop(); pointer=pointer.right;/找左兄弟templatebinarytreenode * binarytree:leftsibling(binarytreenode * current)binarytreenode * pointer=parent(current);return pointer.left;/找右兄弟templatebinarytreenode * binarytree:rightsibling(binarytreenode * current)binarytreenode * pointer=parent(current);return pointer.right;/生成新树templatevoid binarytree:creattree(const T info)root=new binarytreenode (info);/l=r=NULL;/生成新树templatevoid binarytree:creattree(T info,binarytree & lefttree,binarytree & righttree)root=new binarytreenode (info,lefttree.root,righttree.root);lefttree.root=righttree.root=NULL;/用字符串生成新树/*templatevoid binarytree:creattree(mystring a)using std:stack;stackbinarytreenode * astack;root=new binarytreenode (a0);binarytreenode * pointer=root;int i;for(i=1;ai!=0;i+)if(ai=()astack.push();else if(ai=)astack.top();pointer=rightsibling(pointer); else pointer.left=new binarytreenode (ai);pointer=pointer-leftchild(); */删除树/*templatevoid binarytree:deletebinarytree(binarytreenode * root)if(root!=NULL)deletebinarytree(root-leftchild();deletebinarytree(root-rightchild();delete root;/保存当前结点的前序周游templatevoid binarytree:preorder1(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;while(!astack.empty()|pointer)if(pointer)coutvalue()leftchild();elsepointer=astack.top();astack.pop();pointer=pointer-rightchild();/保存当前结点右孩子的前序周游templatevoid binarytree:preorder(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;astack.push(NULL);while(!astack.empty()|pointer)if(pointer)coutvalue() rightchild()!=NULL)astack.push(pointer-rightchild();pointer=pointer-leftchild();else pointer=astack.top();astack.pop();/中序周游templatevoid binarytree:inorder(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;while(!astack.isempty()|pointer)if(pointer) astack.push(pointer); pointer=pointer.left;elsepointer=astack.top();t;pointer=poiter.right;/后序周游templatevoid binarytree:postorder(binarytreenode * root)using std:stack;enum tagsleft,right;templateclass stackelementpublic:binarytreenode * pointer;tags tag;stackstackelement * astack;stackelement element;binarytreenode * pointer=root;while(!astack.isempty()|pointer) while(pointer)element.pointer=pointer; element.tag=left;astack.push(element);pointer=pointer.leftchild();element=astack.top;pointer=element.pointer;if(element.tag=left)element.tag=right;astack.push(element);pointer=pointer.rightchild();elsecoutpointer.value();pointer=null;/求一个结点的深度templateint binarytree:deep(binarytreenode * current)int i;binarytreenode * pointer=null;while(pointer!=root)pointer=parent(current);i+;current=pointer;return i;/求叶结点个数templatevoid binarytree:numofleaf(binarytreenode * root,int & i)binarytreenode * pointer=root;if(pointer.leftchild()=pointer.rightchild()=null)i+;elsenumofleaf(pointer.leftchild(),i);numofleaf(pointer.rightchild(),i);/*templateint binarytree:high(binarytreenode * root,int & i)binarytreenode * pointer=root;if(pointer.leftchild()=pointer.rightchild()=null)i+;*/将一棵树镜面影射templatevoid binarytree:shadow(binarytreenode * root)binarytreenode * temp=null;binarytreenode * pointer=root;using std:queue;queuebinarytreenode * aqueue;if(pointer)aqueue.push(pointer);while(! aqueue.isempty()pointer=aqueue.front();temp=pointer.left;pointer.left=pointer.right;pointer.right=temp;if(pointer.leftchild()aqueue.push(pointer.leftchild();if(pointer.rightchild()aqueue.push(pointer.