中序和先序非递归建立二叉树

中序和先序遍历序列可以非递归地建立二叉树。具体步骤如下：

1. 创建一个栈，将先序遍历序列的第一个节点入栈。
2. 从先序遍历序列中取出下一个节点，如果该节点的值与栈顶节点的值不相等，则将该节点作为栈顶节点的左子树，并将该节点入栈。
3. 如果该节点的值与栈顶节点的值相等，则弹出栈顶节点，并将该节点作为栈顶节点的右子树。
4. 重复步骤2和3直到先序遍历序列中的所有节点都被处理。

5. 最后得到的二叉树即为所求。

中序遍历序列的处理方式与先序遍历序列类似，只需要将上述步骤中的先序遍历序列改为中序遍历序列即可。

相关问题

中序和先序非递归建立二叉树程序代码

下面是中序和先序非递归建立二叉树的程序代码示例，以C++为例：

#include <iostream>
#include <stack>
using namespace std;

// 二叉树结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 中序和先序非递归建立二叉树函数
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty())
        return NULL;

    stack<TreeNode*> s;
    int preIndex = 0, inIndex = 0;

    TreeNode* root = new TreeNode(preorder[preIndex]);
    s.push(root);
    preIndex++;

    while (preIndex < preorder.size()) {
        TreeNode* cur = new TreeNode(preorder[preIndex]);
        TreeNode* prev = NULL;

        while (!s.empty() && s.top()->val == inorder[inIndex]) {
            prev = s.top();
            s.pop();
            inIndex++;
        }

        if (prev != NULL) {
            prev->right = cur;
        } else {
            s.top()->left = cur;
        }

        s.push(cur);
        preIndex++;
    }

    return root;
}

// 中序遍历函数
void inorderTraversal(TreeNode* root) {
    if (root == NULL)
        return;

    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

// 先序遍历函数
void preorderTraversal(TreeNode* root) {
    if (root == NULL)
        return;

    cout << root->val << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

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

    TreeNode* root = buildTree(preorder, inorder);

    cout << "Inorder traversal: ";
    inorderTraversal(root);
    cout << endl;

    cout << "Preorder traversal: ";
    preorderTraversal(root);
    cout << endl;

    return 0;
}

该程序中，我们使用一个栈来辅助建立二叉树。在建立二叉树时，我们首先将先序遍历序列的第一个节点入栈，并将其作为根节点。然后，我们遍历先序遍历序列中的所有节点，对于每个节点，如果其值与栈顶节点的值不相等，则将该节点作为栈顶节点的左子树，并将该节点入栈；否则，我们弹出栈顶节点，并将该节点作为栈顶节点的右子树。最后，我们返回根节点，即可得到建立好的二叉树。

在程序中，我们还提供了中序遍历和先序遍历函数，用于验证建立的二叉树是否正确。

中序和先序非递归建立二叉树程序代码c语言

下面是中序和先序非递归建立二叉树的程序代码示例，以C语言为例：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结构体
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建节点函数
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 中序和先序非递归建立二叉树函数
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0 || inorderSize == 0)
        return NULL;

    struct TreeNode* root = createNode(preorder[0]);
    struct TreeNode* cur = root;

    int preIndex = 1, inIndex = 0;
    int flag = 0;
    struct TreeNode* stack[1000];
    int top = -1;

    stack[++top] = cur;

    while (preIndex < preorderSize) {
        if (top >= 0 && stack[top]->val == inorder[inIndex]) {
            cur = stack[top];
            top--;
            inIndex++;
            flag = 1;
        } else {
            if (flag == 0) {
                cur->left = createNode(preorder[preIndex]);
                cur = cur->left;
                stack[++top] = cur;
                preIndex++;
            } else {
                flag = 0;
                cur->right = createNode(preorder[preIndex]);
                cur = cur->right;
                stack[++top] = cur;
                preIndex++;
            }
        }
    }

    return root;
}

// 中序遍历函数
void inorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;

    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

// 先序遍历函数
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL)
        return;

    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    int preorder[6] = {1, 2, 4, 5, 3, 6};
    int inorder[6] = {4, 2, 5, 1, 3, 6};

    struct TreeNode* root = buildTree(preorder, 6, inorder, 6);

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    return 0;
}

该程序中，我们使用了一个栈来辅助建立二叉树。在建立二叉树时，我们首先创建根节点，并将其入栈。然后，我们遍历先序遍历序列中的所有节点，对于每个节点，如果其值与栈顶节点的值不相等，则将该节点作为栈顶节点的左子树，并将该节点入栈；否则，我们弹出栈顶节点，并将该节点作为栈顶节点的右子树。最后，我们返回根节点，即可得到建立好的二叉树。

在程序中，我们还提供了中序遍历和先序遍历函数，用于验证建立的二叉树是否正确。