天天看點
傳回

二叉樹的基本操作

這篇文章隻有二叉樹的基本操作，對于AVL、Huffman等不涉及。基本都是計科專業課内的知識點。

#include <bits/stdc++.h>
#define MAX 1010
using namespace std;
/*
    樹的基本操作：
        00)由前序結果建樹 
        01)前序遞歸周遊
        02)前序非遞歸周遊 
        03)中序遞歸周遊 
        04)中序非遞歸周遊 
        05)後序遞歸周遊 
        06)後序非遞歸周遊 
        07)層序周遊
        08)層序周遊，按層輸出
        09)計算葉結點個數
        10)計算每層中葉結點的個數
        11)樹的高度（根結點為 1）
        12)某結點的深度（根結點為 1，找不到傳回 0，如果有多個則傳回距根結點較近的）
        13)某結點的深度（根結點為 1，找不到傳回 0，如果有多個則傳回距根結點較遠的）
        14)某結點的父結點集合（找不到傳回空，此結點存在多個時傳回離根較近的結果，遠近相同時傳回左邊的）
        15)某結點的父結點集合（找不到傳回空，此結點存在多個時傳回離根較遠的結果，遠近相同時傳回左邊的）
        16)某結點的直接父節點（找不到傳回 -1，此結點存在多個時傳回離根較近的結果，遠近相同時傳回左邊的）
        17)某結點的直接父節點（找不到傳回 -1，此結點存在多個時傳回離根較遠的結果，遠近相同時傳回左邊的）
        18)前序和中序建樹
        19)後序和中序建樹
        20)每一棵樹及其子樹做鏡面反轉 
        21)樹的複制 
*/

//二叉樹結點結構 
typedef class Node
{
    public:
        int val;
        Node *left;
        Node *right;
        Node(){ left = right = NULL; }
        Node(int tval){ val = tval; left = right = NULL; }
} *BinTree;

//根據前序周遊的結果建樹，空結點用-1表示 
BinTree createTree_preOrder()
{
    int val;
    cin >> val;
    if(val == -)
        return NULL;            //空結點時退棧 
     BinTree temp = new Node();
     temp->val = val;
     temp->left = createTree_preOrder();    //遞歸建立左子樹 
     temp->right = createTree_preOrder();   //遞歸建立右子樹 
     return temp;
}

//遞歸的前序周遊
void print_preOrder_recursion(BinTree root)
{
    if(root != NULL)
    {
        cout << root->val;
        print_preOrder_recursion(root->left);
        print_preOrder_recursion(root->right);
    }
}

/*
    非遞歸的前序周遊：
        當棧不空或者目前指向的結點不空時，便還沒有通路完： 
            1)目前指向不空的時候：輸出、壓棧、向左下移
            2)目前指向為空的時候：彈棧、向右下移
*/
void print_preOrder_noRecursion(BinTree root)
{
    BinTree arr[MAX];
    int t = ;          //棧頂。模拟棧 
    BinTree pointer = root;
    while(pointer != NULL || t != )
    {
        if(pointer != NULL)
        {
            cout << pointer->val;
            arr[t++] = pointer;
            pointer = pointer->left;
        }else
            pointer = arr[--t]->right;
    }
}

//遞歸的中序周遊
void print_inOrder_recursion(BinTree root)
{
    if(root != NULL)
    {
        print_inOrder_recursion(root->left);
        cout << root->val;
        print_inOrder_recursion(root->right);
    }
}

/*
    非遞歸的中序周遊： 
        當棧不空或者目前指向的結點不空時，便還沒有通路完： 
            1)目前指向不空的時候：壓棧、向左下移
            2)目前指向為空的時候：彈棧、輸出、向右下移
*/
void print_inOrder_noRecursion(BinTree root)
{
    BinTree arr[MAX];
    int t = ;          //棧頂。模拟棧 
    BinTree pointer = root;
    while(pointer != NULL || t != )
    {
        if(pointer != NULL)
        {
            arr[t++] = pointer;
            pointer = pointer->left;
        }else{
            pointer = arr[--t];
            cout << pointer->val;
            pointer = pointer->right; 
        } 
    }
}

//遞歸的後序周遊
void print_posOrder_recursion(BinTree root)
{
    if(root != NULL)
    {
        print_posOrder_recursion(root->left);
        print_posOrder_recursion(root->right);
        cout << root->val;
    }
}

/*
    非遞歸的後序周遊：
        當棧不空或者目前指向的結點不空時，便還沒有通路完： 
            1)循環 壓入結點、向左下移 至目前指向為空 
            2)彈棧
            3)右子樹為空或從右子樹傳回時：輸出、記錄右子樹、目前指向置空 
            4)右子樹不空且不是從右子樹傳回時：壓棧、向右下移
*/
void print_posOrder_noRecursion(BinTree root)
{
    BinTree arr[MAX];
    int t = ;          //棧頂。模拟棧 
    BinTree pointer = root;
    BinTree visit = NULL;
    while(pointer != NULL || t != )
    {
        while(pointer != NULL) 
        {
            arr[t++] = pointer;
            pointer = pointer->left;
        }
        pointer = arr[--t];
        if(pointer->right != NULL && pointer->right != visit)
        {
            arr[t++] = pointer;
            pointer = pointer->right;
        }else{
            cout << pointer->val;
            visit = pointer;
            pointer = NULL;
        }
    }
}

/*
    層序周遊，不分層輸出：
        樹不空時根結點壓入隊列中，當隊列不空時便沒有通路完
        對所有的結點，入隊和出隊都隻進行一次，兩種方式都可以通路，在這選擇出隊時通路： 
            1)出隊列、左子樹不空左子樹入隊、右子樹不空右子樹入隊 
*/
void print_levelOrder_noLayered(BinTree root)
{
    BinTree pointer = root;
    int f = , t = ;   //頭、尾。模拟隊列 
    BinTree arr[MAX];
    if(pointer != NULL)
        arr[t++] = pointer;
    while(t > f)
    {
        pointer = arr[f++];
        cout << pointer->val;
        if(pointer->left != NULL)
            arr[t++] = pointer->left;
        if(pointer->right != NULL)
            arr[t++] = pointer->right;
    }
}

/*
    層序周遊，分層輸出：
        樹不空時根結點壓入隊列中，當父親隊列和孩子隊列都不空時便沒有通路完
        對所有的結點，兩個隊列入隊和出隊都隻進行一次，四種方式都可以通路，在這選擇出父親隊列時通路：
            1)父親隊列不空時：出隊列、輸出、左子樹不空壓入孩子隊列、右子樹不空壓入孩子隊列
            2)父親隊列為空時：孩子隊列的結點都壓入父親隊列、輸出換行
*/
void print_levelOrder_layered(BinTree root)
{
    BinTree father[MAX], child[MAX];
    int ff = , ft = ;     //模拟父親隊列 
    int cf = , ct = ;     //模拟孩子隊列 
    BinTree pointer = root;
    if(pointer != NULL)
        father[ft++] = pointer;
    while(ff < ft || cf < ct)   //父親隊列不空且孩子隊列不空 
    {
        if(ff < ft)     //父親隊列不空時，輸出 
        {
            pointer = father[ff++];
            cout << pointer->val << " ";
            if(pointer->left != NULL)
                child[ct++] = pointer->left;
            if(pointer->right != NULL) 
                child[ct++] = pointer->right;
        }else{
            while(cf < ct)
                father[ft++] = child[cf++];
            cout << endl;
        }
    }
}

/*
    計算葉結點個數：
        任意一種周遊，左子樹為空右子樹為空時計入 
*/
int count_leaves(BinTree root)
{
    if(root == NULL)
        return ;
    if(root->left == NULL && root -> right ==NULL)
        return ;
    int l = count_leaves(root->left);
    int r = count_leaves(root->right);
    return l + r;
}

/*
    計算每層葉結點的個數
        層序周遊計數 
*/
void count_leaves_layered(BinTree root)
{
    BinTree father[MAX], child[MAX];
    int ff = , ft = ;     //模拟父親隊列 
    int cf = , ct = ;     //模拟孩子隊列
    int n = ;              //記錄每層的個數 
    BinTree pointer = root;
    if(pointer != NULL)
        father[ft++] = pointer;
    while(ff < ft || cf < ct)   //父親隊列不空且孩子隊列不空 
    {
        if(ff < ft)
        {
            pointer = father[ff++];
            if(pointer->left == NULL && pointer->right == NULL)
                n++;
            if(pointer->left != NULL)
                child[ct++] = pointer->left;
            if(pointer->right != NULL) 
                child[ct++] = pointer->right;
        }else{
            while(cf < ct)
                father[ft++] = child[cf++];
            cout << n << " ";
            n = ;
        }
    }
    cout << n;
}

/*
    樹的高度：
        目前結點為空結點時傳回 0，否則傳回其左右子樹中較大的高度 
*/
int tree_height(BinTree root)
{
    if(root == NULL)
        return ;
    int l = tree_height(root->left);
    int r = tree_height(root->right);
    return l > r ? l +  : r + ;
}

/*
    某結點的深度（近距離優先）：
        遞歸周遊，如果目前結點是所找結點，則傳回 1，否則傳回 0 
        如果目前結點的接受到的孩子結點傳回值（n）不是 0，傳回 n + 1 
*/
int node_depth_near(BinTree root, int val)
{
    if(root == NULL)
        return ; 
    if(root->val == val)
        return ;
    int l = node_depth_near(root->left, val);
    int r = node_depth_near(root->right, val);
    if(l ==  && r == )
        return ;
    else if(l == )
        return r + ;
    else if(r == )
        return l + ;
    return l < r ? l +  : r + ;
}

/*
    某結點的深度（遠距離優先）：
        遞歸周遊，如果目前結點是所找結點，則傳回 1，否則傳回 0 
        如果目前結點的接受到的孩子結點傳回值（n）不是 0，傳回 n + 1 
*/
int node_depth_far(BinTree root, int val)
{
    if(root == NULL)
        return ;
    int l = node_depth_far(root->left, val);
    int r = node_depth_far(root->right, val);
    if(l ==  && r == )
    {
        if(root->val == val)
            return ;
        else
            return ;
    }
    else if(l == )
        return r + ;
    else if(r == )
        return l + ;
    return l > r ? l +  : r + ;
} 

/*
    某結點的父節點集合（近距離優先。找不到時傳回空，多個時傳回較近的，遠近相同時傳回左邊的）： 
        結點為空時：傳回空
        結點為所求結點時：傳回vector<int> 
        結點不空時：向左向右遞歸
                    退棧時若左右結點都為空，傳回 NULL 
                    退棧時若左右結點都為空，且目前結點不所求系結點傳回vector<int>
                    左子樹空傳回右子樹、右子樹空傳回左子樹 
                    左右結點都不空時傳回size較大的，size一緻時傳回左子樹。 
*/ 
vector<int> *getFathers_near(BinTree root, int val)
{
    if(root == NULL)
        return NULL;
    if(val == root->val)
        return new vector<int>;
    vector<int> * l = getFathers_near(root->left, val);
    vector<int> * r = getFathers_near(root->right, val);
    if(l == NULL && r == NULL)
        return NULL;
    if(l == NULL)
    {
        r->push_back(root->val);
        return r;
    }
    if(r == NULL)
    {
        l->push_back(root->val);
        return l;
    }
    l->push_back(root->val);
    r->push_back(root->val); 
    if(r->size() == l->size())
        return l;
    return r->size() > l->size() ? l : r; 
}

/*
    某結點的父節點集合（遠距離優先。找不到時傳回空，多個時傳回較遠的，遠近相同時傳回左邊的）： 
        結點為空時：傳回空
        結點不空時：向左向右遞歸
                    退棧時若左右結點都為空，且目前結點不是所求系結點傳回NULL 
                    退棧時若左右結點都為空，且目前結點不所求系結點傳回vector<int>
                    左子樹為空傳回右子樹、右子樹為空傳回左子樹
                    左右結點都不空時傳回size較大的，size一緻時傳回左子樹。 
*/ 
vector<int> *getFathers_far(BinTree root, int val)
{
    if(root == NULL)
        return NULL;
    vector<int> * l = getFathers_far(root->left, val);
    vector<int> * r = getFathers_far(root->right, val);
    if(l == NULL && r == NULL)
    {
        if(val == root->val)
            return new vector<int>;
        else
            return NULL;
    } 
    if(l == NULL)
    {
        r->push_back(root->val);
        return r;
    }
    if(r == NULL)
    {
        l->push_back(root->val);
        return l;
    }
    l->push_back(root->val);
    r->push_back(root->val); 
    if(r->size() == l->size())
        return l;
    return r->size() > l->size() ? r : l; 
}

/*
    某結點的直接父節點（找不到傳回 -1，此結點存在多個時傳回離根較近的結果，遠近相同時傳回左邊的）
*/ 
int getDirectFather_near(BinTree root, int val)
{
    vector<int> * v = getFathers_near(root, val);
    if(v == NULL)
        return -;
    else
        return v->at();
}

/*
    某結點的直接父節點（找不到傳回 -1，此結點存在多個時傳回離根較遠的結果，遠近相同時傳回左邊的）
*/ 
int getDirectFather_far(BinTree root, int val)
{
    vector<int> * v = getFathers_far(root, val);
    if(v == NULL)
        return -;
    else
        return v->at();
}

/*
    前序和中序建樹（結點數值不能重複）： 
        傳入前序周遊結果、中序周遊結果、樹的結點個數
        結點個數大于 0時，向左，向右遞歸。退棧時建立結點把左右子樹連接配接成一棵樹 
        結點個數不大于 0時，傳回空 
*/
BinTree createTree_preAndIn(int *pre, int *in, int n)
{
    if(n > )
    {
        int temp = pre[], i = ;
        while(i < n)
            if(in[i++] == temp)
                break;
        BinTree l = createTree_preAndIn(&pre[], &in[], i - );
        BinTree r = createTree_preAndIn(&pre[i], &in[i], n - i);
        BinTree t = new Node(temp);
        t->left = l;
        t->right = r;
        return t;
    }
    return NULL;
}

/*
    後序和中序建樹（結點數值不能重複）： 
        傳入後序周遊結果、中序周遊結果、樹的結點個數
        結點個數大于 0時，向左，向右遞歸。退棧時建立結點把左右子樹連接配接成一棵樹 
        結點個數不大于 0時，傳回空 
*/
BinTree createTree_posAndIn(int *pos, int *in, int n)
{
    if(n > )
    {
        int temp = pos[n - ], i = ;
        while(i < n)
            if(in[i++] == temp)
                break;
        BinTree l = createTree_posAndIn(&pos[], &in[], i - );
        BinTree r = createTree_posAndIn(&pos[i - ], &in[i], n - i);
        BinTree t = new Node(temp);
        t->left = l;
        t->right = r;
        return t;
    }
    return NULL;
}

/*
    每棵樹及其子樹都做鏡面反轉 
        後序遞歸，退棧時交換左右子樹 
*/ 
void reverseTree_mirror(BinTree root)
{
    if(root != NULL)
    {
        reverseTree_mirror(root->left);
        reverseTree_mirror(root->right);
        BinTree temp = root->left;
        root->left = root->right;
        root->right = temp;
    }
}

BinTree copyTree(BinTree root)
{
    if(root != NULL)
    {
        BinTree l = copyTree(root->left);
        BinTree r = copyTree(root->right);
        BinTree temp = new Node(root->val);
        temp->left = l;
        temp->right = r;
        return temp;
    }
    return NULL;
} 
int main()
{
    int pre[] = {, , , , , , , , };
    int in[] = {, , , , , , , , };
    int pos[] = {, , , , , , , , };
    BinTree root = createTree_preOrder();
    print_preOrder_noRecursion(root);
    cout << endl;
    print_inOrder_noRecursion(root);
    cout << endl;
    print_posOrder_noRecursion(root);
    cout << endl;
    print_levelOrder_noLayered(root);
    cout << endl;
    print_levelOrder_layered(root);
    cout << endl;
    cout << count_leaves(root); 
    cout << endl;
    count_leaves_layered(root);
    cout << endl;
    cout << tree_height(root);
    cout << endl;
    cout << node_depth_near(root, );
    cout << endl;
    cout << node_depth_far(root, );
    cout << endl;
    vector<int> *vn = getFathers_near(root, );
    for(int i = ; i < vn->size(); i++)
        cout << vn->at(i) << " ";
    cout << endl;
    vector<int> *vf = getFathers_far(root, );
    for(int i = ; i < vf->size(); i++)
        cout << vf->at(i) << " ";
    cout << endl;
    cout << getDirectFather_near(root, );
    cout << endl;
    cout << getDirectFather_far(root, );
    cout << endl;
    BinTree preAndIn = createTree_preAndIn(pre, in, );
    print_preOrder_recursion(preAndIn);
    cout << endl;
    BinTree posAndIn = createTree_posAndIn(pos, in, );
    print_preOrder_recursion(posAndIn);
    cout << endl;
    reverseTree_mirror(root);
    print_preOrder_recursion(root);
    cout << endl;
    BinTree copy = copyTree(root);
    print_preOrder_recursion(copy);
    return ;
}

/*
                1
            2      3
          4   5  6   7
                8     
                 9
    input:
        1 2 4 -1 -1 5 -1 -1 3 6 8 -1 9 -1 -1 -1 7 -1 -1
    output:
        pre：  124536897
        in：   425189637
        pos：  452986731
        level：123456789
    mirror:
        137689254
*/
dsa
上一篇: 阿裡雲常用服務介紹
下一篇: android 高德地圖設定不能旋轉_還不知道高德地圖車機版？比手機導航好用

繼續閱讀