做題之前要了解的是：二叉樹的括號表示法和中序遍歷的順序。

括號表示法：括號外的是父結(jié)點，括號內(nèi)“，”號左側(cè)為左子樹“，”右側(cè)為右子樹。例如a(b(c(d,e)),f(g,h(i,j)))，變?yōu)闃淙鐖D：

10年積累的做網(wǎng)站、網(wǎng)站建設(shè)經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先做網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有土默特右旗免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

中序遍歷：就是依次遍歷：左子樹--->根結(jié)點--->右子樹。

第一題: ? 一、題目

二、思路：

?首先設(shè)置樹的結(jié)點，因為要逆序所以我額外設(shè)置了父指針，指向父結(jié)點。

typedef struct Node
{
 char data;
 Node *left;
 Node *right;
 Node *parents;
}BTNode;

因為是按照括號形式輸入，所以要寫一個函數(shù)，來通過該輸入方式創(chuàng)建二叉樹：

//由括號表示法創(chuàng)建二叉樹
void CreateBTree(BTNode *&root, char str[])
{
 int i=0, flag;
 BTNode *p=NULL, *temp=NULL;
 stackS;
 while( str[i]!='\0')
 {
  switch( str[i] )
  {
   case '(':flag=1; S.push(p); break;//表示其后創(chuàng)建的為左兒子
   case ')':S.pop( );break;//棧頂元素的左右兒子處理完了， 出棧
   case ',':flag=2;break;//其后創(chuàng)建的為右兒子
   default:
           p=new Node;
     p->data=str[i]; p->left=p->right=NULL;

     if( root==NULL ) //如果當(dāng)前每根，說明是第一個結(jié)點，設(shè)為根
                    {
                        root=p;
                        p->parents = NULL;
                    }

     else //有根節(jié)點了，就把棧頂元素放到對應(yīng)的子樹上
     {
      temp=S.top();
      p->parents = temp; //設(shè)置p的父結(jié)點
      switch( flag )
      {
       case 1:temp->left=p; break;
       case 2:temp->right=p; break;
      }
     }
  }
  i++;
 }
}

題目要求按照中序遍歷的順序來輸出：

//中序遍歷二叉樹
void InOrder(BTNode *root)
{
    //cout<< "進來了1"<< endl ;
    if(root)
    {
        //cout<< "進來了2"<< endl ;
        InOrder(root->left);

        if(root->left == NULL && root->right == NULL)
        {
            //cout<< "進來了3"<< endl ;
            BTNode *p = root;
            while(p != NULL)
            {
                //cout<< "進來了4"<< endl ;
                cout<< p->data<< ' ';
                p = p->parents;
            }
            cout<< endl;
        }


        InOrder(root->right);
    }
}

三、所有代碼：?

#include#includeusing namespace std;

typedef struct Node
{
 char data;
 Node *left;
 Node *right;
 Node *parents;
}BTNode;

//由括號表示法創(chuàng)建二叉樹
void CreateBTree(BTNode *&root, char str[])
{
 int i=0, flag;
 BTNode *p=NULL, *temp=NULL;
 stackS;
 while( str[i]!='\0')
 {
  switch( str[i] )
  {
   case '(':flag=1; S.push(p); break;//表示其后創(chuàng)建的為左兒子
   case ')':S.pop( );break;//棧頂元素的左右兒子處理完了， 出棧
   case ',':flag=2;break;//其后創(chuàng)建的為右兒子
   default:
           p=new Node;
     p->data=str[i]; p->left=p->right=NULL;

     if( root==NULL ) //如果當(dāng)前每根，說明是第一個結(jié)點，設(shè)為根
                    {
                        root=p;
                        p->parents = NULL;
                    }

     else //有根節(jié)點了，就把棧頂元素放到對應(yīng)的子樹上
     {
      temp=S.top();
      p->parents = temp; //設(shè)置p的父結(jié)點
      switch( flag )
      {
       case 1:temp->left=p; break;
       case 2:temp->right=p; break;
      }
     }
  }
  i++;
 }
}


//中序遍歷二叉樹
void InOrder(BTNode *root)
{
    //cout<< "進來了1"<< endl ;
    if(root)
    {
        //cout<< "進來了2"<< endl ;
        InOrder(root->left);

        if(root->left == NULL && root->right == NULL)
        {
            //cout<< "進來了3"<< endl ;
            BTNode *p = root;
            while(p != NULL)
            {
                //cout<< "進來了4"<< endl ;
                cout<< p->data<< ' ';
                p = p->parents;
            }
            cout<< endl;
        }


        InOrder(root->right);
    }
}

int main()
{
 char str1[2000];
 BTNode *root1=NULL;
 cin>>str1;

    //判斷一棵二叉樹是否為相似同構(gòu)
 root1=NULL;
 CreateBTree(root1, str1);
 InOrder(root1);

    return 0;
}
//a(b(c(d,e)),f(g,h(i,j)))

第二題:? 一、題目描述

二、思路

? 該題不需要父指針，去掉即可，創(chuàng)建二叉樹的方式與上一題一樣。主要是如何判斷同構(gòu)。

先設(shè)計個函數(shù)，用來判斷兩個樹是否同構(gòu)。

//判斷兩二叉樹是否相似
int Like(BTNode *p1, BTNode *p2)
{
 if(p1==NULL && p2==NULL)
      return 1;
    else if( p1==NULL || p2==NULL) //有一個先結(jié)束了，說明不同構(gòu)
         return 0;
    else return Like(p1->left, p2->left)&Like(p1->right, p2->right); //左子樹的左側(cè)和右子樹的左側(cè)比，右側(cè)和右側(cè)比
}

再設(shè)計個函數(shù)，用上一個函數(shù)判斷兩個子樹即可。

//判斷一棵樹是否對稱同構(gòu)
int SymmTree(BTNode *root)
{
 if( root==NULL)//當(dāng)樹為空時
     return 1;
 else
     return Like(root->left, root->right); //判斷一棵樹的兩個子樹
}

三、答案：?

#include#includeusing namespace std;

typedef struct Node
{
 char data;
 Node *left;
 Node *right;
}BTNode;

//由括號表示法創(chuàng)建二叉樹
void CreateBTree(BTNode *&root, char str[])
{
 int i=0, flag;
 BTNode *p=NULL, *temp=NULL;
 stackS;
 while( str[i]!='\0')
 {
  switch( str[i] )
  {
   case '(':flag=1; S.push(p); break;//表示其后創(chuàng)建的為左兒子
   case ')':S.pop( );break;//棧頂元素的左右兒子處理完了， 出棧
   case ',':flag=2;break;//其后創(chuàng)建的為右兒子
   default:
           p=new Node;
     p->data=str[i]; p->left=p->right=NULL;

     if( root==NULL ) //如果當(dāng)前每根，說明是第一個結(jié)點，設(shè)為根
      root=p;
     else //有根節(jié)點了，就把棧頂元素放到對應(yīng)的子樹上
     {
      temp=S.top();
      switch( flag )
      {
       case 1:temp->left=p; break;
       case 2:temp->right=p; break;
      }
     }
  }
  i++;
 }
}


//判斷兩二叉樹是否相似
int Like(BTNode *p1, BTNode *p2)
{
 if(p1==NULL && p2==NULL)
      return 1;
    else if( p1==NULL || p2==NULL) //有一個先結(jié)束了，說明不同構(gòu)
         return 0;
    else return Like(p1->left, p2->left)&Like(p1->right, p2->right); //左子樹的左側(cè)和右子樹的左側(cè)比，右側(cè)和右側(cè)比
}

//判斷一棵樹是否對稱同構(gòu)
int SymmTree(BTNode *root)
{
 if( root==NULL)//當(dāng)樹為空時
     return 1;
 else
     return Like(root->left, root->right); //判斷一棵樹的兩個子樹
}

int main()
{
 char str1[2000];
 BTNode *root1=NULL;
 cin>>str1;

    //判斷一棵二叉樹是否為相似同構(gòu)
 root1=NULL;
 CreateBTree(root1, str1);
 if( SymmTree(root1) )
        cout<<"true"<

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧


當(dāng)前標題：二叉樹習(xí)題（1.從葉節(jié)點按中序遍歷逆序輸出2.判斷是否同構(gòu)）-創(chuàng)新互聯(lián)
URL分享：http://weahome.cn/article/dgsodj.html