登录
当前位置： 首页 > 工具软件 > PE Tree > 使用案例 >

算法 - Tree

符允晨
2023-12-01

 

树的相关算法

           1
         /   \
        2     3
      /   \    \
     9     10   4
      \    /   /  \
       12 11  5    6
      /  \  \     /  \
    13    14 15  7    8

1. 根据先序和中序构建二叉树

主要思路：先从先序序列中确定根节点，在从中序中确认根节点两侧的左右子树递归创建

    TreeNode* BuildTree(vector<int>& pre, vector<int>& in)
    {

        if (pre.size() == 0 || pre.size() != in.size()) return NULL;

        m_root = BuildTreeInternal(pre, 0, pre.size() - 1, in, 0, in.size() - 1);

        return m_root;
    }

    TreeNode* BuildTreeInternal(vector<int>& pre, int ps, int pe, vector<int>& in, int is, int ie) 
    {

        if ( ps > pe && is > ie ) return NULL;

        int data = pre[ps];
        int mid = 0;
        vector<int>::iterator it = find(in.begin(), in.end(), data);

        if (it != in.end()) mid = it - in.begin();
        int llen = mid - is; //说明要以当前root为根节点对需要建树的序列b左子树长
        int rlen = ie - mid; //说明要以当前root为根节点对需要建树的序列b右子树长

        TreeNode* tn = new TreeNode();
        tn->m_data = data;
        tn->m_left = BuildTreeInternal(pre, ps + 1, ps + llen, in, is, is + llen -1);
        tn->m_right = BuildTreeInternal(pre, pe - rlen + 1, pe, in, ie - rlen + 1, ie);

        return tn;
    }

2. 计算树的高度

主要思路：树的高度 = max(左子树高度， 右子树高度）+ 1

    int GetHeight(TreeNode* node) 
    {
        if(node == NULL) return 0;
        return (GetHeight(node->m_left) > GetHeight(node->m_right) ? \
 GetHeight(node->m_left) : GetHeight(node->m_right)) + 1;
    }

3. 先序、中序、后序（递归和非递归）以及层次遍历二叉树

3.1 前序遍历 

主要思路：根、左、右，需要栈保存扫描过的根

    void PreTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        cout << node->m_data <<",";
        PreTraverse(node->m_left);
        PreTraverse(node->m_right);
    }

    void PreTraverseWithoutRecursive(TreeNode* node) 
    {
        if(node == NULL) return;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) {
            while(nd) {
                st.push(nd);
                cout << nd->m_data <<",";
                nd = nd->m_left;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            nd = tmpNode->m_right;
        }
    }

3.2 中序遍历

主要思路：左、根、右，需要栈保存扫描过的根

    void MidTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        MidTraverse(node->m_left);
        cout << node->m_data <<",";
        MidTraverse(node->m_right);
    }

    void MidTraverseWithoutRecursive(TreeNode* node) 
    {
        if(node == NULL) return ;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) { //此处的判读条件
            while(nd) {
                st.push(nd);
                nd = nd->m_left;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            cout << tmpNode->m_data <<",";
            nd = tmpNode->m_right;//此处遍历栈顶弹出node
        }
    }

3.3 后序遍历

主要思路：

  1. 当节点的"右子树存在且被访问后"或者是"右子树为空"才能访问自身。
  2. 设置标志变量 flag 来判断是否访问过左孩子， pre指针来指向先前访问过的节点。
  3. 所有左孩子压栈后， 最后一个节点的左孩子为空，已被访问p = NULL ， 令flag=1

   当左孩子被访问时，进入循环，取栈顶节点。

  •     当栈顶节点的右孩子等于空或"前一个被访问的节点"时,访问该节点， 令pre 等于当前节点，pre = p， 当前节点出栈。
  •     当栈顶节点的右孩子不为空时， 继续遍历以右孩子为根节点的右子树。

    void PostTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        PostTraverse(node->m_left);
        PostTraverse(node->m_right);
        cout << node->m_data <<",";
    }

    
    void PostTraverseWithoutRecursive(TreeNode* node) 
    {
        if(node == NULL) return;
        stack<TreeNode*> st;
        int flag = 0;
        TreeNode* nd = node, *pre = NULL;
        do {
            while(nd) {
                st.push(nd);
                nd = nd->m_left;
            }

            flag = 1;
            while (!st.empty() && flag) {
                TreeNode* tempNode = st.top();
                if(tempNode->m_right ==  pre || !tempNode->m_right) {
                    cout << tempNode->m_data << ",";
                    st.pop();
                    pre = tempNode;
                } else {
                    nd = tempNode->m_right;
                    flag = 0;
                }
            }
        } while (!st.empty());
    }

    //后序遍历顺序：左右根 -> 变换：先获得根右左的遍历顺序，再反转
    void PostTraverseReverse(TreeNode* node) 
    {
        if(node == NULL) return;
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) {
            while(nd) {
                st.push(nd);
                res.push_back(nd->m_data);
                nd = nd->m_right;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            nd = tmpNode->m_left;
        }

        for (int i = res.size() -1 ; i >= 0; i--) {
            cout << res[i] << ",";
        }
        cout << endl;
    }

3.4 层次遍历

   void TreeLevelTraverse(TreeNode* node) 
    {
        if(node == NULL) return ;

        queue<TreeNode*> que;
        que.push(node);
        while(!que.empty()) {
            TreeNode* tmpNode = que.front();
            cout << tmpNode->m_data <<",";
            que.pop();
            if(tmpNode->m_left) que.push(tmpNode->m_left);
            if(tmpNode->m_right) que.push(tmpNode->m_right);
        }
    }

4. 树向右拉平

主要思路：从根节点开始出发，先检测其左子结点是否存在，如存在则将根节点和其右子节点断开，将左子结点及其后面所有结构一起连到原右子节点的位置，把原右子节点连到元左子结点最后面的右子节点之后。

    void flatten(TreeNode *root) 
    {
        TreeNode *cur = root;
        while (cur) {
            if (cur->m_left) {
                TreeNode *p = cur->m_left;
                while (p->m_right) p = p->m_right;
                p->m_right = cur->m_right;
                cur->m_right = cur->m_left;
                cur->m_left = NULL;
            }
            cur = cur->m_right;
        }
    }

5. 树的右视图 

主要思路：层次遍历只取最右边的孩子, 统计每一层的节点个数，循环将他们的左右孩子入队，最后只保存这一次最右边的孩子的值

    vector<int> rightSideView(TreeNode *root) 
    {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
	      res.push_back(q.back()->m_data);
	      int size = q.size();
	      for (int i = 0; i < size; ++i) {
	        TreeNode *node = q.front();
	        q.pop();
	        if (node->m_left) q.push(node->m_left);
	        if (node->m_right) q.push(node->m_right);
	      }
        }
        return res;
    }

 6. 树的左右镜像

    TreeNode* switchTree(TreeNode* root) {
        if(NULL == root) return NULL;

        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* tn = st.top(); st.pop();
            TreeNode* tmp = tn->m_left;
            tn->m_left = tn->m_right;
            tn->m_right = tmp;
            if(tn->m_left) st.push(tn->m_left);
            if(tn->m_right) st.push(tn->m_right);
        }
        return root;
    }

 

附录：整个工程代码

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

struct TreeNode 
{
    int m_data;
    TreeNode* m_left;
    TreeNode* m_right;
};

class Tree 
{
private:
    TreeNode* m_root;
    int m_height;
public:
    ~Tree() { }
    Tree() { m_root = NULL; m_height = 0; }

    TreeNode* GetRoot() { return m_root;}

    TreeNode* BuildTree(vector<int>& pre, vector<int>& in)
    {

        if (pre.size() == 0 || pre.size() != in.size()) return NULL;

        m_root = BuildTreeInternal(pre, 0, pre.size() - 1, in, 0, in.size() - 1);

        return m_root;
    }

    TreeNode* BuildTreeInternal(vector<int>& pre, int ps, int pe, vector<int>& in, int is, int ie) 
    {

        if ( ps > pe && is > ie ) return NULL;

        int data = pre[ps];
        int mid = 0;
        vector<int>::iterator it = find(in.begin(), in.end(), data);

        if (it != in.end()) mid = it - in.begin();
        int llen = mid - is; //说明要以当前root为根节点对需要建树的序列b左子树长
        int rlen = ie - mid; //说明要以当前root为根节点对需要建树的序列b右子树长

        TreeNode* tn = new TreeNode();
        tn->m_data = data;
        tn->m_left = BuildTreeInternal(pre, ps + 1, ps + llen, in, is, is + llen -1);
        tn->m_right = BuildTreeInternal(pre, pe - rlen + 1, pe, in, ie - rlen + 1, ie);

        return tn;
    }

    void PreTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        cout << node->m_data <<",";
        PreTraverse(node->m_left);
        PreTraverse(node->m_right);
    }

    void PreTraverseWithoutRecursive(TreeNode* node) {
        if(node == NULL) return;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) {
            while(nd) {
                st.push(nd);
                cout << nd->m_data <<",";
                nd = nd->m_left;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            nd = tmpNode->m_right;
        }
    }

    void MidTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        MidTraverse(node->m_left);
        cout << node->m_data <<",";
        MidTraverse(node->m_right);
    }

    map<string, vector<int> >  MidTraverseWithoutRecursive(TreeNode* node) 
    {
        map<string, vector<int> > ret;
        if(node == NULL) return ret;
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) { //此处的判读条件
            while(nd) {
                st.push(nd);
                nd = nd->m_left;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            res.push_back(tmpNode->m_data);
            //cout << tmpNode->m_data <<",";
            nd = tmpNode->m_right;//此处遍历栈顶弹出node
        }
        ret.insert(pair<string, vector<int> >(__FUNCTION__, res));
        return ret;
    }

    void PostTraverse(TreeNode* node) 
    {
        if(node == NULL) return;
        PostTraverse(node->m_left);
        PostTraverse(node->m_right);
        cout << node->m_data <<",";
    }

/*后续遍历关键在于，当节点的"右子树存在且被访问后"或者是"右子树为空"才能访问自身。
设置标志变量 flag 来判断是否访问过左孩子， pre指针来指向先前访问过的节点。
所有左孩子压栈后， 最后一个节点的左孩子为空，已被访问p = NULL ， 令flag=1
当左孩子被访问时，进入循环，取栈顶节点。
1. 当栈顶节点的右孩子 等于 空  或  前一个被访问的节点  时， 访问该节点， 令pre 等于当前节点，pre = p， 当前节点出栈。
2. 当栈顶节点的右孩子不为空时， 继续遍历以右孩子为根节点的右子树。
*/
    void PostTraverseWithoutRecursive(TreeNode* node) 
    {
        if(node == NULL) return;
        stack<TreeNode*> st;
        int flag = 0;
        TreeNode* nd = node, *pre = NULL;
        do {
            while(nd) {
                st.push(nd);
                nd = nd->m_left;
            }

            flag = 1;
            while (!st.empty() && flag) {
                TreeNode* tempNode = st.top();
                if(tempNode->m_right ==  pre || !tempNode->m_right) {
                    cout << tempNode->m_data << ",";
                    st.pop();
                    pre = tempNode;
                } else {
                    nd = tempNode->m_right;
                    flag = 0;
                }
            }
        } while (!st.empty());
    }

    //后序遍历顺序：左右根 -> 变换：先获得根右左的遍历顺序，再反转
    void PostTraverseReverse(TreeNode* node) 
    {
        if(node == NULL) return;
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode* nd = node;
        while(nd || !st.empty()) {
            while(nd) {
                st.push(nd);
                res.push_back(nd->m_data);
                nd = nd->m_right;
            }
            TreeNode* tmpNode = st.top();
            st.pop();
            nd = tmpNode->m_left;
        }

        for (int i = res.size() -1 ; i >= 0; i--) {
            cout << res[i] << ",";
        }
        cout << endl;
    }

    int GetHeight(TreeNode* node) 
    {
        if(node == NULL) return 0;
        return (GetHeight(node->m_left) > GetHeight(node->m_right) ? GetHeight(node->m_left) : GetHeight(node->m_right)) + 1;
    }

    void TreeLevelTraverse(TreeNode* node) 
    {
        if(node == NULL) return ;

        queue<TreeNode*> que;
        que.push(node);
        while(!que.empty()) {
            TreeNode* tmpNode = que.front();
            cout << tmpNode->m_data <<",";
            que.pop();
            if(tmpNode->m_left) que.push(tmpNode->m_left);
            if(tmpNode->m_right) que.push(tmpNode->m_right);
        }
    }

    vector<int> RightSideView(TreeNode *root)
    {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            res.push_back(q.back()->m_data);
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *node = q.front();
                q.pop();
                if (node->m_left) q.push(node->m_left);
                if (node->m_right) q.push(node->m_right);
            }
        }
        return res;
    }

    void LeftFlattenTree(TreeNode *root)
    {
        TreeNode *cur = root;
        while (cur) {
            if (cur->m_left) {
                TreeNode *p = cur->m_left;
                while (p->m_right) p = p->m_right;
                p->m_right = cur->m_right;
                cur->m_right = cur->m_left;
                cur->m_left = NULL;
            }
            cur = cur->m_right;
        }
    }

    void showTree(map<string, vector<int> > data) 
    {
        if(data.empty()) return;
        map<string,vector<int> >::iterator it = data.begin();
        cout << it->first << ":" <<endl;
        vector<int>::iterator vit = it->second.begin();
        while (vit != it->second.end()) {
            cout << *vit++ << ",";
        }
    }

    void PrintTree(TreeNode* n, bool left, string const& indent)
    {
        if (n->m_right)
        {
            PrintTree(n->m_right, false, indent + (left ? "|     " : "      "));
        }
        cout << indent;
        cout << (left ? '\\' : '/');
        cout << "-----";
        cout << n->m_data << endl;
        if (n->m_left)
        {
            PrintTree(n->m_left, true, indent + (left ? "      " : "|     "));
        }
    }

    void Print(TreeNode* root)
    {
        if (root->m_right)
        {
            PrintTree(root->m_right, false, "");
        }
        cout << root->m_data << endl;
        if (root->m_left)
        {
            PrintTree(root->m_left, true, "");
        }
    }
};

void printVector(int tag, vector<int>& vec) 
{
    int i = 0;
    switch(tag) {
    case 1:
        cout << "PreTraverse..."<<endl;
        break;
    case 2:
        cout << "MidTraverse..."<<endl;
        break;
    case 3:
        cout << "PostTraverse..."<<endl;
        break;
    default:
        break;
    }
    for(i = 0; i < vec.size() - 1; i++) {
        cout << vec[i] <<" , ";
    }
    cout << vec[vec.size() - 1] << endl;
}



int main()
{
    int a[] = {1, 2, 9, 12, 13, 14, 10, 11, 15, 3, 4, 5, 6, 7, 8};
    int b[] = {13, 12, 14, 9, 2, 11, 15, 10, 1, 3, 5, 4, 7, 6, 8};
    vector<int> pre(a, a + sizeof(a)/sizeof(a[0]));
    vector<int> ldr(b, b + sizeof(b)/sizeof(b[0]));
    printVector(1, pre);
    printVector(2, ldr);
    cout <<endl;
    Tree* tr = new Tree();
    tr->CreateTree(pre, ldr);
    tr->Print(tr->GetRoot());
    tr->BuildTreeInplace(pre, ldr);
    tr->Print(tr->GetRoot());
    cout << endl << "Pre Traverse:" << endl;;
    tr->PreTraverse(tr->GetRoot());
    cout << endl;
    tr->PreTraverseWithoutRecursive(tr->GetRoot());
    cout << endl << endl << "Mid Traverse:" << endl;
    tr->MidTraverse(tr->GetRoot());
    cout << endl;
    tr->showTree(tr->MidTraverseWithoutRecursive(tr->GetRoot()));
    cout << endl << endl << "Post Traverse:" << endl;
    tr->PostTraverse(tr->GetRoot());
    cout << endl;
    tr->PostTraverseWithoutRecursive(tr->GetRoot());
    cout << endl;
    tr->PostTraverseReverse(tr->GetRoot());
    cout << endl;
    cout <<"Tree Height:" << tr->GetHeight(tr->GetRoot());
    cout << endl << endl << "Level Traverse:" << endl;
    tr->TreeLevelTraverse(tr->GetRoot());
    cout << endl << endl << "Tree Left View:" << endl;
    vector<int> ret = tr->RightSideView(tr->GetRoot());
	for(auto item: ret) cout << item << ", ";
    cout << endl;
    cout << endl << endl << "Tree Left Flatten View:" << endl;
    tr->LeftFlattenTree(tr->GetRoot());
    tr->Print(tr->GetRoot());
    return 1;
}

执行结果

PreTraverse...
1 , 2 , 9 , 12 , 13 , 14 , 10 , 11 , 15 , 3 , 4 , 5 , 6 , 7 , 8
MidTraverse...
13 , 12 , 14 , 9 , 2 , 11 , 15 , 10 , 1 , 3 , 5 , 4 , 7 , 6 , 8

                  /-----8
            /-----6
            |     \-----7
      /-----4
      |     \-----5
/-----3
1
|     /-----10
|     |     |     /-----15
|     |     \-----11
\-----2
      \-----9
            |     /-----14
            \-----12
                  \-----13

Pre Traverse:
1,2,9,12,13,14,10,11,15,3,4,5,6,7,8,
1,2,9,12,13,14,10,11,15,3,4,5,6,7,8,

Mid Traverse:
13,12,14,9,2,11,15,10,1,3,5,4,7,6,8,
MidTraverseWithoutRecursive:
13,12,14,9,2,11,15,10,1,3,5,4,7,6,8,

Post Traverse:
13,14,12,9,15,11,10,2,5,7,8,6,4,3,1,
13,14,12,9,15,11,10,2,5,7,8,6,4,3,1,
13,14,12,9,15,11,10,2,5,7,8,6,4,3,1,

Tree Height:5

Level Traverse:
1,2,3,9,10,4,12,11,5,6,13,14,15,7,8,

Tree Left View:
1, 3, 4, 6, 8,


Tree Left Flatten View:
                                                                              /-----8
                                                                        /-----7
                                                                  /-----6
                                                            /-----5
                                                      /-----4
                                                /-----3
                                          /-----15
                                    /-----11
                              /-----10
                        /-----14
                  /-----13
            /-----12
      /-----9
/-----2
1

 

 类似资料：

相关阅读

对数算法高耸算法Python Dijkstra算法Jarvis March算法贪婪算法

相关文章

贪心算法分治算法递归算法回溯算法算法面经

相关问答

排序算法组合算法变更算法杂耍算法Dijkstra SDSP算法

相关文档

算法珠玑结构之法算法之道常用算法实现方法常规算法教程数据挖掘算法
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.