如何用c++建造一颗二叉树？如何
//stree。h//二叉树类的实现(查找树)/////////////////////////////////////////////////////////#ifndefSTREE_H#defineSTREE_H#include#include#includeusingnamespacestd;templateclassStNode{ *m_pFather;StNode*m_pLeft;StNode*m_pRight;StNode(consttype&item,StNode*left,StNode*right,StNode*father):NodeValue(item),m_pLeft...全部
//stree。h//二叉树类的实现(查找树)/////////////////////////////////////////////////////////#ifndefSTREE_H#defineSTREE_H#include#include#includeusingnamespacestd;templateclassStNode{ *m_pFather;StNode*m_pLeft;StNode*m_pRight;StNode(consttype&item,StNode*left,StNode*right,StNode*father):NodeValue(item),m_pLeft(left),m_pRight(right),m_pFather(father){}};//endclassStNodetemplateclassStree{ *m_pRoot;intm_nSize;//创造新结点,并返回其指针//若分配内存失败,抛出异常StNode*m_PGetAllocation(consttype&item,StNode*left,StNode*right,StNode*father);StNode*m_pCopy(StNode*obj);StNode*m_pFind(consttype&item)const;//以降序输出二叉树voidm_vOutByDown(StNode*obj,conststring&space)const;//以升序输出二叉树voidm_vOutByRise(StNode*obj,conststring&space)const;//以层次输出二叉树voidm_vOutByLayer(StNode*obj,conststring&space)const;//释放被删除的结点内存voidm_vDelete(StNode*obj){deleteobj;}//全部删除voidm_vDeleteAll(StNode*obj){StNode*curr=obj;if(curr!=NULL){m_vDeleteAll(curr->m_pLeft);m_vDeleteAll(curr->m_pRight);deletecurr;}}//endm_vDeleteAll(StNode*obj) { *m_pParent;StNode*m_pRootOfTree;//指向当前树的根结点 ():m_pParent(NULL),m_pRootOfTree(NULL){}iterator(StNode*obj,StNode*root):m_pParent(obj),m_pRootOfTree(root){}//重载操作符*//如果迭代器指向end,抛出异常type&operator*(){if(m_pParent==NULL)throwexception("*()const,迭代器指向无效!\n");returnm_pParent->NodeValue;}//endoperator*()const//重载操作符==和!=booloperator==(constiterator&obj){returnm_pParent==obj。
m_pParent;}booloperator!=(constiterator&obj){returnm_pParent!=obj。
m_pParent;}//重载操作符--//用遍历来模拟迭代的操作//如果是空树,抛出异常iteratoroperator++(){//前缀StNode*root=m_pRootOfTree;StNode*parent=m_pParent;//迭代器无效时if(m_pParent==NULL){//如果是空树if(root==NULL)throwexception("(),树为空!\n");//迭代器是由end返回的值else{parent=root;while(parent->m_pLeft!=NULL)//找到树中最小的结点parent=parent->m_pLeft;m_pParent=parent;returniterator(m_pParent,m_pRootOfTree);//返回最小的结点}}//endif(m_pParent==NULL)//当迭代器的右子树存在时if(parent->m_pRight!=NULL){parent=parent->m_pRight;//运动到右子树while(parent->m_pLeft!=NULL)//查找右子树中最小结点parent=parent->m_pLeft;m_pParent=parent;returniterator(m_pParent,m_pRootOfTree);}//endif(parent->m_pRight!=NULL)else{//迭代器右子树不存在if(parent->m_pFather==NULL){//当前结点是根结点m_pParent=NULL;returniterator(m_pParent,m_pRootOfTree);}//向父结点移动直到父结点的左指针指向当前结点StNode*father=parent->m_pFather;while(father->m_pLeft!=parent){parent=parent->m_pFather;father=parent->m_pFather;if(parent->m_pFather==NULL){//移动到跟结点,说明迭代器已经是最大结点m_pParent=NULL;returniterator(m_pParent,m_pRootOfTree);}}m_pParent=father;returniterator(m_pParent,m_pRootOfTree);}//endelse}//endoperator++()前缀iteratoroperator++(int){//后缀iteratornow=*this;//取得当前的迭代器operator++();//调用前缀形式returnnow;}//endoperator++(int)后缀iteratoroperator--(){//前缀StNode*parent=m_pParent;StNode*root=m_pRootOfTree;//如果迭代器无效时if(m_pParent==NULL){if(m_pRootOfTree==NULL)//空树throwexception("(),树为空!\n");else{//end返回的迭代器,将最大的结点返回parent=root;while(parent->m_pRight!=NULL)parent=parent->m_pRight;m_pParent=parent;returniterator(m_pParent,m_pRootOfTree);}}//endif(m_pParent==NULL)//如果没有左结点if(m_pParent->m_pLeft==NULL){//当前结点是根结点if(parent->m_pFather==NULL){m_pParent=NULL;returniterator(m_pParent,m_pRootOfTree);}//向父结点查找,直到父结点的右指针指向当前结点或到达根节点StNode*father=parent->m_pFather;while(father->m_pRight!=parent){parent=parent->m_pFather;father=parent->m_pFather;if(parent->m_pFather==NULL){//当前结点已经是根结点m_pParent=NULL;returniterator(m_pParent,m_pRootOfTree);}}m_pParent=father;returniterator(m_pParent,m_pRootOfTree);}//endif(m_pParent->m_pLeft==NULL)else{//有左子结点,查找左子树中最大的结点parent=parent->m_pLeft;//先移动到右结点while(parent->m_pRight!=NULL)parent=parent->m_pRight;m_pParent=parent;returniterator(m_pParent,m_pRootOfTree);}//endelse}//end。收起
