二叉树如何实现双亲结点及求树的高度

待我称王封你为后i 2022-08-18 03:24 192阅读 0赞

求二叉树的高度，可以用递归的思想去求解，也可以用非递归的思想去求解，只不过，递归的代码简单明了，但是总的来说，递归有递归的好处，非递归当然也有非递归的好处。

求树的高度的递归思想和递归建树的思想差不多：

从最底层的子树（结点）开始，求每颗子树（个结点）的左子树和右子树的高度，返回最大的那颗子树的高度，即每递归一次便加1

具体核心代码如下：

int getHight(BiNode<T>\*t)   //递归寻找高度  
                                                                        \{  
                                                                          int deep=0;  
                                                                     if(t!=NULL)  
                                                                  \{  
                                                             int lchild\_hight=getHight(t->lchild);   //树的左子树的高度  
                                                             int rchild\_hight=getHight(t->rchild);   //树的右子树的高度  
                                                            deep=(lchild>=rchild)?(lchild\_hight+1):(rchild\_hight+1); //deep取最大值  
                                                                  \}  
                                                                    return deep;  //返回deep  
                                                                          \}

如果递归思想不太明白的，建议去看看盗梦空间哟！

关于非递归的思想，通过遍历整棵二叉树，找出叶子结点，然后在从叶子结点回溯到树的根结点，通过结算结点个数，加1便是树高了

具体代码如下：

void TreeHight(BiNode<T>\* &t)     //中序遍历改造为寻找树高

\{  
using std::stack;  
t->father=NULL;  
stack<BiNode<T>\*>leafstack;//存储叶子结点的栈  
stack<BiNode<T>\*>nodeStack;//存储待访问的结点  
BiNode<T>\*pointer=t;  
while(!nodeStack.empty()||pointer)  //栈为空时结束遍历  
\{  
if(pointer)\{  
nodeStack.push(pointer);           //当前结点入栈  
pointer=pointer->lchild;         //转向访问左子树  
\}  
else\{  
pointer=nodeStack.top();    //读取栈顶元素  
    if(pointer->lchild==NULL&&pointer->rchild==NULL) //判断是否为叶子结点  
 leafstack.push(pointer);                      //若为叶子结点，存储到相应的栈中  
pointer=pointer->rchild;              //转向访问右子树  
nodeStack.pop();                      //栈顶元素退栈  
\}  
\}  
//叶子结点的地址在leafstack栈中呈线性排列  
int Hight=0;//第n个叶子结点的高度  
int hight=0;//第n+1个叶子结点的高度  
       while(!leafstack.empty())  
  \{  
  hight=0;     //初始化为0  
  pointer=leafstack.top(); //读取栈顶的叶子结点  
           while(pointer->father!=NULL)   //当叶子栈为空时结束  
  \{   
     hight++;       
 pointer=pointer->father;//回溯到其双亲结点  
   
  \}  
  leafstack.pop();   //栈顶元素退栈  
  if(Hight<hight)    //当前叶子结点的高度若比之前一个的叶子高度大，则赋值给前一个高度  
  Hight=hight;  
  \}  
  cout<<"树高为："<<hight+1<<endl;  
\}

当然，如果是用非递归思想，那我们在遍历的时候就该用层次遍历咯

不过过程中有一个father指针的标记倒是用到了递归的思想

完全代码如下：

\#include<string>  
\#include<iostream>  
\#include<stack>  
using namespace std;   
//二叉链表表示二叉树     
template<class T>  
class BiNode    
\{    
public:  
     T data;//节点数据    
     BiNode \* lchild;//左孩子    
     BiNode \* rchild;//右孩子  
BiNode \*father;//双亲  
     BiNode();  
BiNode(T d)\{ data=d; \}        //new一个结点的时候就给其数据域赋值  
~BiNode()\{\}  
void createTree(BiNode<T>\* &t, string pre,string in) //后序，中序  
\{  
if(pre.length()==0)  
\{  
   t=NULL;  
\}  
if(pre.length()!=0)  
\{  
    t=new BiNode<T>(pre\[0\]);  
   int index=in.find(pre\[0\]);  
            string  in\_left\_str=in.substr(0, index);  
            string  in\_right\_str=in.substr(index+1);  
            string  pre\_left\_str=pre.substr(1, index);  
            string  pre\_right\_str=pre.substr(index+1);   
if(t!=NULL)  
            \{  
createTree(t->lchild,pre\_left\_str,in\_left\_str);  
                createTree(t->rchild,pre\_right\_str,in\_right\_str);  
\}  
\}  
\}  
     void preOrder(BiNode<T> \*t)  
\{  
if(t==NULL)  
\{  
  return ;  
\}  
  if(t!=NULL)  
  \{  
   cout<<t->data;  
preOrder(t->lchild);  
preOrder(t->rchild);  
  \}  
\}  
void inOrder(BiNode<T> \*t)  
\{  
   if(t==NULL)  
\{  
 return ;  
\}  
if(t!=NULL)  
\{  
  inOrder(t->lchild);  
  cout<<t->data;  
  inOrder(t->rchild);  
\}  
\}  
void TreeHight(BiNode<T>\* &t)     //中序遍历改造为寻找树高  
\{  
using std::stack;  
t->father=NULL;  
stack<BiNode<T>\*>leafstack;//存储叶子结点的栈  
stack<BiNode<T>\*>nodeStack;//存储待访问的结点  
BiNode<T>\*pointer=t;  
while(!nodeStack.empty()||pointer)  //栈为空时结束遍历  
\{  
if(pointer)\{  
nodeStack.push(pointer);           //当前结点入栈  
pointer=pointer->lchild;         //转向访问左子树  
\}  
else\{  
pointer=nodeStack.top();    //读取栈顶元素  
    if(pointer->lchild==NULL&&pointer->rchild==NULL) //判断是否为叶子结点  
 leafstack.push(pointer);                      //若为叶子结点，存储到相应的栈中  
pointer=pointer->rchild;              //转向访问右子树  
nodeStack.pop();                      //栈顶元素退栈  
\}  
\}  
//叶子结点的地址在leafstack栈中呈线性排列  
int Hight=0;//第n个叶子结点的高度  
int hight=0;//第n+1个叶子结点的高度  
       while(!leafstack.empty())  
  \{  
  hight=0;     //初始化为0  
  pointer=leafstack.top(); //读取栈顶的叶子结点  
           while(pointer->father!=NULL)   //当叶子栈为空时结束  
  \{   
     hight++;       
 pointer=pointer->father;//回溯到其双亲结点  
   
  \}  
  leafstack.pop();   //栈顶元素退栈  
  if(Hight<hight)    //当前叶子结点的高度若比之前一个的叶子高度大，则赋值给前一个高度  
  Hight=hight;  
  \}  
  cout<<"树高为："<<hight+1<<endl;  
\}  
int getHight(BiNode<T>\*t)   //递归寻找高度  
\{  
 int deep=0;  
if(t!=NULL)  
\{  
int lchild\_hight=getHight(t->lchild);   //树的左子树的高度  
int rchild\_hight=getHight(t->rchild);   //树的右子树的高度  
deep=(lchild>=rchild)?(lchild\_hight+1):(rchild\_hight+1); //deep取最大值  
\}  
return deep;  //返回deep  
\}  
void DeFineFather(BiNode \*t)//递归标记结点的双亲  
 \{  
    if(t!=NULL)  
\{  
  if(t->lchild!=NULL)  
  t->lchild->father=t;  
  if(t->rchild!=NULL)  
  t->rchild->father=t;  
  
DeFineFather(t->lchild);  
DeFineFather(t->rchild);  
\}  
 \}  
\};  
int main()  
\{  
   BiNode<char>\*t=NULL;  
   string pre="ABDFGCEH";  
   string  in="BFDGACEH";  
   t->createTree(t,pre,in);  
   /\*  
   cout<<"前序遍历"<<endl;  
   t->preOrder(t);  
   cout<<endl;  
   cout<<"中序遍历"<<endl;  
   t->inOrder(t);  
   cout<<endl;\*/  
   t->DeFineFather(t);  
   t->TreeHight(t);  
   cout<<endl;  
cout<<"递归寻求树的高度："<<t->getHight(t)<<endl;  
   return 0;  
\}