用c++创建一个5个节点的树并用中序遍历实现打印每个节点的值

以下是用C++创建5个节点的树并用中序遍历打印每个节点的值的示例代码：

#include <iostream>
using namespace std;

// 定义树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 中序遍历打印树节点的值
void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

int main() {
    // 创建5个节点的树
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->right = new TreeNode(4);
    root->left->left = new TreeNode(1);
    root->right->right = new TreeNode(5);

    // 中序遍历打印树节点的值
    inorder(root);

    return 0;
}

输出结果为：`1 2 3 4 5`，符合中序遍历的顺序。

相关问题

用c++语言写程序，已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列 【问题描述】 已知一个二叉树的中序遍历序列和后序遍历序列，求这棵树的前序遍历序列。 【输入形式】 一个树的中序遍历序列 该树后序遍历序列，中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母 【输出形式】 一个树的前序遍历序列 【样例输入】 dbeafcg debfgca 【样例输出】 abdecfg

以下是一种使用递归的实现方法：

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

#define MAX_LEN 100

struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 根据中序遍历和后序遍历构造二叉树
struct TreeNode* buildTree(char* inorder, char* postorder, int len) {
    if (len == 0) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = postorder[len - 1];
    int i;
    for (i = 0; i < len; i++) {
        if (inorder[i] == root->val) {
            break;
        }
    }
    root->left = buildTree(inorder, postorder, i);
    root->right = buildTree(inorder + i + 1, postorder + i, len - i - 1);
    return root;
}

// 前序遍历二叉树
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    char inorder[MAX_LEN], postorder[MAX_LEN];
    scanf("%s %s", inorder, postorder);
    int len = strlen(inorder);
    struct TreeNode* root = buildTree(inorder, postorder, len);
    preorderTraversal(root);
    printf("\n");
    return 0;
}

首先定义了一个 `TreeNode` 结构体表示二叉树节点，包含节点值 `val` 和左右子节点指针 `left` 和 `right`。然后定义了一个 `buildTree()` 函数，根据中序遍历和后序遍历构造二叉树。该函数的输入参数为中序遍历序列 `inorder`、后序遍历序列 `postorder` 和序列长度 `len`，返回值为构造出的二叉树的根节点指针。

在 `buildTree()` 函数中，首先判断序列长度是否为 0，如果是，则返回 `NULL` 表示空树。否则，根据后序遍历的特点，最后一个元素为根节点，找到该元素在中序遍历中的位置，分别递归构造左子树和右子树，最后返回根节点指针。

接着定义了一个 `preorderTraversal()` 函数，用于前序遍历二叉树。该函数的输入参数为二叉树的根节点指针 `root`，输出为前序遍历序列。遍历顺序为先输出当前节点值，再遍历左子树，最后遍历右子树。

最后在 `main()` 函数中读入中序遍历序列和后序遍历序列，调用 `buildTree()` 函数构造二叉树，再调用 `preorderTraversal()` 函数输出前序遍历序列。

C++代码实现：一颗具有n个节点的完全二叉树放在二叉树的顺序存储结构中 ，试编写非递归算法对该树进行中序遍历。输入：1输入完全二叉树的元素个数，2输入二叉树的节点数据。输出：中序遍历的序列

在C++中，对于完全二叉树的中序遍历，我们可以使用迭代的方式，因为完全二叉树的特性使得我们可以在数组中通过索引来访问每个节点。以下是基于这个思路的非递归中序遍历算法：

#include <iostream>
using namespace std;

// 完全二叉树的节点结构体
struct TreeNode {
    int val; // 节点值
    TreeNode* left; // 左孩子指针
    TreeNode* right; // 右孩子指针
};

// 判断当前节点是否为空
bool isEmpty(TreeNode* node) {
    return node == nullptr;
}

// 助手函数，用于查找左子树的最后一个节点的右子节点
TreeNode* findLastNode(TreeNode* root) {
    if (isEmpty(root)) return nullptr;
    TreeNode* last = root;
    while (last->right != nullptr) {
        last = last->right;
    }
    return last;
}

// 中序遍历的核心函数
void inorderTraversal(TreeNode* root, vector<int>& result) {
    stack<TreeNode*> s; // 使用栈辅助中序遍历
    TreeNode* current = root;
    
    while (!isEmpty(root) || !isEmpty(s)) {
        // 先将所有左子树节点压入栈
        while (!isEmpty(current)) {
            s.push(current);
            current = current->left;
        }

        // 弹出栈顶节点，并将其右子节点置空，以便进入下一个左子树
        current = s.top();
        s.pop();

        // 访问当前节点
        result.push_back(current->val);

        // 更新当前节点为右子节点
        current = current->right;
    }
}

int main() {
    int n; // 输入节点个数
    cin >> n;

    // 创建并初始化二叉树顺序存储结构，假设已知前序遍历结果
    TreeNode* nodes[n];
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        nodes[i] = new TreeNode{val, nullptr, nullptr};
    }

    // 假设前序遍历已经确定了根节点
    TreeNode* root = nodes[0];

    // 初始化结果数组
    vector<int> result;

    // 进行中序遍历
    inorderTraversal(root, result);

    // 输出中序遍历结果
    for (int value : result) {
        cout << value << " ";
    }
    cout << endl;

    // 清理内存
    for (int i = 0; i < n; ++i) {
        delete nodes[i];
    }

    return 0;
}