《数据结构二叉树》由会员分享，可在线阅读，更多相关《数据结构二叉树（23页珍藏版）》请在金锄头文库上搜索。
1、#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 *
2、 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;templatebina
3、rytreenode: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;templatebinar
4、ytreenode * 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
5、 * 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 crea
6、ttree(T info,binarytree / 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(binaryt
7、reenode * root);int deep(binarytreenode * current); /求出一个结点的深度 void numofleaf(binarytreenode * root,int /叶子个数/void high(binarytreenode * root,int /高度void shadow(binarytreenode * root); /镜面影射void commonp(binarytreenode * p,binarytreenode * q); /求两结点的最近的共同祖先;/找双亲templatebinarytreenode * binarytree:par
8、ent(binarytreenode * current)using std:stack;binarytreenode * pointer=root;stack * 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();as
9、tack.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 p
10、ointer.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;/用字符串生成新树
11、/*templatevoid binarytree:creattree(mystring a)using std:stack;stack * 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);elsepointer.left=new binarytreenode (ai);pointer=pointer-leftch
12、ild();*/删除树/*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;stack * astack;w
13、hile(!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;stack * astack;astack.push(NULL);while(!astack.empty()
14、|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;stack * astack;while(!astack.isempty()|point
15、er)if(pointer)astack.push(pointer);pointer=pointer.left;elsepointer=astack.top();coutvoid binarytree:postorder(binarytreenode* root)using std:stack;enum tagsleft,right;templateclass stackelementpublic:binarytreenode * pointer;tags tag;stack * astack;stackelement element;binarytreenode * pointer=root;while(!astack.isempty()|pointer) while(pointer)element.pointer=pointer;element.tag=left;astack.push(element);pointer
