c++ 二叉树标准代码

二叉树是一种常用的数据结构，其标准代码如下：struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

相关问题

c++创建非二叉树的代码，

在C++中，创建非二叉树的数据结构并不像创建二叉树那样常见，因为标准库中并没有提供直接的支持。不过，你可以自定义一个数据结构来表示非二叉树，比如链表、图或者其他更复杂的结构。这里是一个简单的例子，展示如何使用链表模拟一棵单向链表形式的非二叉树：

#include <iostream>

// 定义节点
struct TreeNode {
    int value;
    std::list<TreeNode*> children; // 存储子节点

    TreeNode(int val) : value(val) {}
};

// 插入子节点
void insertChild(TreeNode* parent, TreeNode* child) {
    parent->children.push_back(child);
}

// 打印树
void printTree(TreeNode* node, int depth = 0) {
    for (auto& child : node->children) {
        printTree(child, depth + 1);
    }
    if (depth > 0) {
        std::cout << std::string(depth * 2, ' ') << node->value << std::endl;
    }
}

int main() {
    // 创建并插入节点示例
    TreeNode* root = new TreeNode(1);
    TreeNode* child1 = new TreeNode(2);
    TreeNode* child2 = new TreeNode(3);

    insertChild(root, child1);
    insertChild(root, child2);

    printTree(root); // 输出：   1
                    //  2   3

    return 0;
}

在这个例子中，`TreeNode` 表示一个节点，它有一个值和一个子节点列表。`insertChild` 函数用于添加子节点，而 `printTree` 函数用于按照层次结构打印节点。

请注意，这只是一个基础示例，实际的非二叉树可能有不同的形态，如分支树、有向无环图(DAG)等，需要根据具体需求设计相应的数据结构和操作方法。

建立C++代码二叉树，并实现二叉树的遍历，先序遍历采用递归算法实现，层次遍历用非递归算法来实现，可以自己输入字母来构成二叉树

好的，我来帮您解答这个问题。

首先，我们需要定义二叉树的节点结构体，包括节点值、左右子节点指针：

struct Node {
    char value; // 节点值
    Node* left; // 左子节点指针
    Node* right; // 右子节点指针
};

然后，我们可以定义一个二叉树类，包括插入节点、先序遍历、层次遍历等方法：

class BinaryTree {
public:
    BinaryTree(); // 构造函数
    ~BinaryTree(); // 析构函数
    void insert(char value); // 插入节点
    void preorderTraversal(); // 先序遍历
    void levelTraversal(); // 层次遍历
private:
    Node* root; // 根节点指针
    void preorderTraversalHelper(Node* node); // 先序遍历辅助函数
};

下面是具体实现：

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

struct Node {
    char value; // 节点值
    Node* left; // 左子节点指针
    Node* right; // 右子节点指针
};

class BinaryTree {
public:
    BinaryTree() {
        root = nullptr;
    }
    ~BinaryTree() {
        // TODO: 析构函数
    }
    void insert(char value) {
        if (root == nullptr) {
            root = new Node{value, nullptr, nullptr};
            return;
        }

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* node = q.front();
            q.pop();

            if (node->left == nullptr) {
                node->left = new Node{value, nullptr, nullptr};
                return;
            } else {
                q.push(node->left);
            }

            if (node->right == nullptr) {
                node->right = new Node{value, nullptr, nullptr};
                return;
            } else {
                q.push(node->right);
            }
        }
    }
    void preorderTraversal() {
        preorderTraversalHelper(root);
        cout << endl;
    }
    void levelTraversal() {
        if (root == nullptr) {
            return;
        }

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* node = q.front();
            q.pop();

            cout << node->value << " ";

            if (node->left != nullptr) {
                q.push(node->left);
            }

            if (node->right != nullptr) {
                q.push(node->right);
            }
        }

        cout << endl;
    }
private:
    Node* root;
    void preorderTraversalHelper(Node* node) {
        if (node == nullptr) {
            return;
        }

        cout << node->value << " ";
        preorderTraversalHelper(node->left);
        preorderTraversalHelper(node->right);
    }
};

int main() {
    BinaryTree tree;

    // 构建二叉树
    tree.insert('A');
    tree.insert('B');
    tree.insert('C');
    tree.insert('D');
    tree.insert('E');
    tree.insert('F');
    tree.insert('G');
    tree.insert('H');
    tree.insert('I');

    // 先序遍历
    tree.preorderTraversal();

    // 层次遍历
    tree.levelTraversal();

    return 0;
}

输入字母来构成二叉树，可以将 `insert` 方法改为从标准输入读入节点值，具体实现略。