二叉樹總結—建樹和4種遍歷方式（遞歸&&非遞歸）

今天總結一下二叉樹，要考離散了，求不掛！二叉樹最重要的就是 建立、4種遍歷方式，簡單應用，如何判斷兩顆二叉樹是否相似

二叉樹分為 ：1、完全二叉樹 2、滿二叉樹

2）.n個節點的 完全二叉樹 深度為 int（log2n）（以2為底n的對數）+ 1；

4）.非空二叉樹 某節點編號 n 若有左孩子，則左孩子節點 2*n，若有右孩子，則其節點編號為2*n+1

5）.知道其中兩種遍歷方式，就可知第三種遍歷方式。

6）.判斷倆顆二叉樹是否相同，只需判斷他們任意倆種相對應的遍歷順序即可

建樹：

已知輸入的字符為某顆二叉樹的先序序列，如abcXXdeXgXXfXXX (其中X表示空節點),建立二叉樹

struct node *make()
{
    char c;
    node *st;
    c = getchar();
    if(c=='X')
        st = NULL;
    else
    {
        st = (struct node *)malloc(sizeof(struct node));
        st ->data = c;//已知為先序遍歷，先填充根節點
        st ->left = make();//遞歸形式填充左分支
        st->right = make();//遞歸形式填充左分支
    }
    return st;
}

vcq9o7o8L3N0cm9uZz48L3A+CjxwPjxzdHJvbmc+senA+re9yr263NbY0qqjrMrXz8jSqtaqtcDI57rOsenA+qOsssXE3LTys/a0+sLro6zP1tTaxNS6o8DvxKPE4tK7sek8L3N0cm9uZz48L3A+CjxzdHJvbmc+0ruhos/I0PKx6cD6PC9zdHJvbmc+PGJyPgogICAgPGJyPgo8cD4gICAgMS7PyLfDzsq4+b3ateM8L3A+CiAgICAyLtTZt8POytfzt9bWpzxicj4KCjxwPiAgICAzLtTZt8POytPSt9bWpzwvcD4KPHA+yc/K9s28xqy2/rLmyve1xM/I0PKx6cD6o7pBQkRHQ0VGPC9wPgo8YnI+CjxzdHJvbmc+tv6hotbQ0PKx6cD6PC9zdHJvbmc+PGJyPgogIDxicj4KICAgIDEuz8i3w87K1/O31tanPGJyPgogICAgMi7U2rfDzsq4+b3ateM8YnI+CiAgICAzLtTZt8POytPSt9bWpzxicj4Kyc/K9s28xqy2/rLmyve1xNbQ0PKx6cD6o7pER0JBRUNGPGJyPgo8YnI+CjxzdHJvbmc+yP2horrz0Pix6cD6PC9zdHJvbmc+PGJyPgo8YnI+CiAgICAxLs/It8POytfzt9bWpzxicj4KICAgIDIu1Nm3w87K09K31tanPGJyPgoKPHA+ICAgIDMu1Nm3w87KuPm92rXjPC9wPgo8cD7Jz8r2zbzGrLb+subK97XEuvPQ8rHpwPqjukdEQkVGQ0E8YnI+CjwvcD4KPHA+PC9wPgo8cD48c3Ryb25nPsvEoaKy47TOsenA+jwvc3Ryb25nPjwvcD4KPHA+vs3Kx7TTw7/Su7LjsLTV1bTT1/PWwdPStcTLs9Dyo6zSu7TOsenA+rjDsuPL+dPQtcS92rXjPC9wPgo8cD6yydPDu7fQzrbTwdC1xLe9t6ijrL340NC3w87KPC9wPgq3w87K0rbX073ateMKPHA+PGJyPgo8L3A+CjxwPsnPyva13bnpyr7S4s28yOfPwqO6PC9wPgo8cD48YnI+CjwvcD4KPHA+PGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140602/20140602090831392.jpg" alt="\">

二叉樹的深度

從當前節點的左右分支開始判斷，誰大自增1

判斷倆顆二叉樹是否相似

1.所有節點的對應左右孩子都相同

2.如過 有任意倆種遍歷方式相同，那麼倆顆樹就相同

代碼模版：

#include 
#include 
#include 
#include 
#include 
const int N = 1010;
using namespace std;
char a[100];
struct node{
    char data;
    node *left;
    node *right;
};
struct node *make()
{
    char c;
    node *st;
    c = getchar();
    if(c=='X')
        st = NULL;
    else
    {
        st = (struct node *)malloc(sizeof(struct node));
        st ->data = c;//已知為先序遍歷，先填充根節點
        st ->left = make();//遞歸形式填充左分支
        st->right = make();//遞歸形式填充左分支
    }
    return st;
}

void First_Order(struct node *t )//先序遍歷的遞歸形式
{
    if(t==NULL)
        return ;
    printf("%c -> ",t->data);
    First_Order(t->left);
    First_Order(t->right);
}
void First_Order_1(struct node *t)//先序遍歷非遞歸形式
{
    struct node *stk[N],*p;
    int top = -1;
    if(t!=NULL)
    {
        top++;
        stk[top] = t; //根節點進棧
        while(top>-1)
        {
            p = stk[top];//出棧並訪問該節點
            top--;
            printf("%c -> ",p->data);
            if(p->right!=NULL)  //右孩子進棧
            {
                top++;
                stk[top] = p->right;
            }
            if(p->left!=NULL)//左孩子進棧
            {
                top++;
                stk[top] = p->left;
            }
        }
    }
}
void Mid_Order(struct node *t)//中序遍歷遞歸形式
{
    if(t==NULL)
        return ;
    Mid_Order(t->left);
    printf("%c -> ",t->data);
    Mid_Order(t->right);
}

void Mid_Order_1(struct node *t)//先序遍歷非遞歸形式
{
    struct node *stk[N],*p;
    int top = -1;
    if(t!=NULL)
    {
         p = t;

        while(top>-1 ||p!=NULL )// 遍歷左分支
        {
           while(p!=NULL)     // 將當前t節點的左分支，全部壓入棧
           {
               top++;
               stk[top] = p;
               p = p->left;
           }
           //while結束後，棧頂元素可能沒有左分支節點或者左分支節點已經訪問完畢
           if(top>-1)
           {
               p = stk[top];//出棧 ，並打印
               top--;
               printf("%c -> ",p->data);
               p = p->right;  // 遍歷右分支
           }
        }
    }
}

void Last_Order(struct node *t)//後序遍歷遞歸形式
{
    if(t==NULL)
        return ;
    Last_Order(t->right);
    Last_Order(t->left);
    printf("%c -> ",t->data);
}


void Print_Leaf(struct node *t)
{
    if(t!=NULL)
    {
        if(t->left==NULL && t->right==NULL)
        {
            printf("%c  ",t->data);
        }
            Print_Leaf(t->left);//訪問左分支的葉子節點
            Print_Leaf(t->right);//訪問右分支的葉子節點
    }
}

void Ceng_Order(struct node *t)//層次遍歷，采用環形隊列來實現
{
    struct node *que[N],*p;
    int f,r;   //隊列的頭指針 和 尾指針
    f = -1; r = -1;
    que[++r] = t;  //根節點入隊
    while(f!=r)
    {
        f = (f + 1)% N; //防止隊溢出
        p = que[f]; //隊列頭結點 出隊
        printf("%c -> ",p->data);
        if(p->left !=NULL)  // 將其左孩子 壓入隊列
        {
            r = (r + 1 )% N;
            que[r] = p->left;
        }
        if(p->right !=NULL)  // 將其右孩子 壓入隊列
        {
            r = (r + 1 )% N;
            que[r] = p -> right;
        }
    }
}

int shendu(struct node *t)
{
    int x=0,y = 0;
    if(t!=NULL)
    {
        x = shendu(t->left);
        y = shendu(t->right);

        if(x>y)
            return(x+1);
        else
            return (y+1);
    }
    else
        return 0;
}

/*bool Like(struct node *t1,struct node *t2)//判斷倆顆樹是否相似
{
    bool like1,like2;
    if(t1==NULL && t2 ==NULL)
        return true; //所有對應的分支都相同
    else if(t1==NULL || t2 ==NULL)
        return false;
    else
    {
        like1 = Like(t1->left,t2->left);
        like2 = Like(t1->right,t2->left);
        return (like1 && like2); //返回的是 like1 與 like2的 與
    }
}*/

int main()
{
    struct node *t;
    t = make();//建樹

    puts("先序遍歷,遞歸形式");
    First_Order(t);
    cout<<"END"<