投稿
  1. 高性能架构探索首页
  2. C/C++

二叉树的创建与遍历

admin • • C/C++ • 阅读 131

二叉树的创建

从vector创建队列

leetcode形式的创建，把NULL替换成不出现的数就行了

https://support.leetcode-cn.com/hc/kb/article/1194353/

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
constexpr auto MIN = (int)0x80000000;
TreeNode* createTreeFromVector(vector<int>& nums )
{
    if(nums.size() == 0 || nums[0] == MIN) return NULL;
    TreeNode* head = new TreeNode(nums[0]);
    queue<TreeNode*> q1;

    q1.push(head);
    int i = 0;
    while (1)
    {
        queue<TreeNode*> q2;
        while (!q1.empty())
        {
            TreeNode* p = q1.front();
            q1.pop();
            i++;
            if (i == nums.size()) return head;
            if (nums[i] == MIN) p->left = NULL;
            else
            {
                TreeNode* leftNode = new TreeNode(nums[i]);
                p->left = leftNode;
                q2.push(leftNode);
            }
            i++;
            if (i == nums.size()) return head;
            if (nums[i] == MIN) p->right = NULL;
            else
            {
                TreeNode* rightNode = new TreeNode(nums[i]);
                p->right = rightNode;
                q2.push(rightNode);
            }
        }
        q1 = q2;
    }
}

二叉树的遍历

一、递归方法

前序遍历

void preorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    nums.push_back(head->val);
    preorder(head->left, nums);
    preorder(head->right, nums);
}

vector<int> preorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    preorder(head, outputs);
    return outputs;
}

中序遍历

void inorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    inorder(head->left, nums);
    nums.push_back(head->val);
    inorder(head->right, nums);
}

vector<int> inorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    inorder(head, outputs);
    return outputs;
}

后序遍历

void postorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    postorder(head->left, nums);
    postorder(head->right, nums);
    nums.push_back(head->val);
}

vector<int> postorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    postorder(head, outputs);
    return outputs;
}

二、迭代方法

前序遍历

vector<int> preorderTraversaliter(TreeNode* root) {
        if(!root)   return {};
        stack<TreeNode*>  s;
        TreeNode* curr = root;
        vector<int> outputs;
        while(!s.empty()||curr)
        {
            while(curr)
            {
                //先访问当前节点，然后把右子树压入栈中，访问左子树
                outputs.push_back(curr->val);
                s.push(curr->right);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
        }
        return outputs;
    }

后序遍历（与前序遍历对称）

vector<int> postorderTraversaliter(TreeNode* root) {
        if(!root)   return {};
        stack<TreeNode*>  s;
        TreeNode* curr = root;
        vector<int> outputs;
        while(!s.empty()||curr)
        {
            while(curr)
            {
                //先访问当前节点，然后把左子树压入栈中，访问右子树
                outputs.push_back(curr->val);
                s.push(curr->left);
                curr = curr->right;
            }
            curr = s.top();
            s.pop();
        }
        //逆序
        reverse(outputs.begin(),outputs.end());
        return outputs;
    }

中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root)   return {};
        stack<TreeNode*>  s;
        s.push(root);
        TreeNode* curr = root->left;
        vector<int> outputs;
        while(!s.empty()||curr)
        {
            while(curr)
            {
                //先将当前节点压入栈中，直到访问到左子树为空
                s.push(curr);
                curr = curr->left;
            }
            //弹出顶端节点，访问它，并将当前节点切换为其右子树
            curr = s.top();
            s.pop();
            outputs.push_back(curr->val);
            curr = curr->right;
        }
        return outputs;
    }
};

代码

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
constexpr auto MIN = (int)0x80000000;
TreeNode* createTreeFromVector(vector<int>& nums )
{
    if(nums.size() == 0 || nums[0] == MIN) return NULL;
    TreeNode* head = new TreeNode(nums[0]);
    queue<TreeNode*> q1;

    q1.push(head);
    int i = 0;
    while (1)
    {
        queue<TreeNode*> q2;
        while (!q1.empty())
        {
            TreeNode* p = q1.front();
            q1.pop();
            i++;
            if (i == nums.size()) return head;
            if (nums[i] == MIN) p->left = NULL;
            else
            {
                TreeNode* leftNode = new TreeNode(nums[i]);
                p->left = leftNode;
                q2.push(leftNode);
            }
            i++;
            if (i == nums.size()) return head;
            if (nums[i] == MIN) p->right = NULL;
            else
            {
                TreeNode* rightNode = new TreeNode(nums[i]);
                p->right = rightNode;
                q2.push(rightNode);
            }
        }
        q1 = q2;
    }
}

void inorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    inorder(head->left, nums);
    nums.push_back(head->val);
    inorder(head->right, nums);
}

vector<int> inorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    inorder(head, outputs);
    return outputs;
}

void preorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    nums.push_back(head->val);
    preorder(head->left, nums);
    preorder(head->right, nums);
}

vector<int> preorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    preorder(head, outputs);
    return outputs;
}


void postorder(TreeNode* head, vector<int>& nums)
{
    if (!head) return;
    postorder(head->left, nums);
    postorder(head->right, nums);
    nums.push_back(head->val);
}

vector<int> postorderTraversal(TreeNode* head)
{
    vector<int> outputs;
    if (!head) return outputs;
    postorder(head, outputs);
    return outputs;
}



vector<int> preorderTraversaliter(TreeNode* root) {
    if (!root)   return {};
    stack<TreeNode*>  s;
    TreeNode* curr = root;
    vector<int> outputs;
    while (!s.empty() || curr)
    {
        while (curr)
        {
            //先访问当前节点，然后把右子树压入栈中，访问左子树
            outputs.push_back(curr->val);
            s.push(curr->right);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
    }
    return outputs;
}

vector<int> postorderTraversaliter(TreeNode* root) {
    if (!root)   return {};
    stack<TreeNode*>  s;
    TreeNode* curr = root;
    vector<int> outputs;
    while (!s.empty() || curr)
    {
        while (curr)
        {
            //先访问当前节点，然后把左子树压入栈中，访问右子树
            outputs.push_back(curr->val);
            s.push(curr->left);
            curr = curr->right;
        }
        curr = s.top();
        s.pop();
    }
    //逆序
    reverse(outputs.begin(), outputs.end());
    return outputs;
}

vector<int> inorderTraversaliter(TreeNode* root) {
    if (!root)   return {};
    stack<TreeNode*>  s;
    s.push(root);
    TreeNode* curr = root->left;
    vector<int> outputs;
    while (!s.empty() || curr)
    {
        while (curr)
        {
            //先将当前节点压入栈中，直到访问到左子树为空
            s.push(curr);
            curr = curr->left;
        }
        //弹出顶端节点，访问它，并将当前节点切换为其右子树
        curr = s.top();
        s.pop();
        outputs.push_back(curr->val);
        curr = curr->right;
    }
    return outputs;
}


int main()
{
    vector<int> nums = {1,2,3,4,5,6,7};

    TreeNode* head = createTreeFromVector(nums);
    cout << "中序遍历递归" << endl;
    auto innums = inorderTraversal(head);
    for (auto num : innums)
        cout << num << "  ";
    cout << endl;
    cout << "中序遍历迭代" << endl;
    innums = inorderTraversaliter(head);
    for (auto num : innums)
        cout << num << "  ";
    cout << endl;

    cout << "前序遍历递归" << endl;
    auto prenums = preorderTraversal(head);
    for (auto num : prenums)
        cout << num << "  ";
    cout << endl;
    cout << "前序遍历迭代" << endl;
    prenums = preorderTraversaliter(head);
    for (auto num : prenums)
        cout << num << "  ";
    cout << endl;

    cout << "后序遍历递归" << endl;
    auto postnums = postorderTraversal(head);
    for (auto num : postnums)
        cout << num << "  ";
    cout << endl;
    cout << "后序遍历迭代" << endl;
    postnums = postorderTraversaliter(head);
    for (auto num : postnums)
        cout << num << "  ";
    cout << endl;
    return 0;
}

原文链接: https://www.cnblogs.com/hustyan/p/12404659.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    二叉树的创建与遍历

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/333191

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月1日 下午9:04
下一篇 2023年3月1日 下午9:05

相关推荐