C++空树

空树是一种常见的树形结构，它不包含任何节点。在 C++ 中，可以通过定义一个空指针来表示空树。

以下是一个示例代码，演示如何创建一棵空树：

#include <iostream>

using namespace std;

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

// 创建一棵空树
TreeNode* createTree() {
    return NULL;
}

// 测试代码
int main() {
    TreeNode* root = createTree();
    if (root == NULL) {
        cout << "This is an empty tree." << endl;
    }
    return 0;
}

在上面的代码中，`createTree()` 函数返回一个空指针，表示创建了一棵空树。然后在 `main()` 函数中，通过判断根节点是否为空指针来确认这是一棵空树。

希望这个示例能够帮助你理解如何在 C++ 中创建一棵空树。

相关问题

c++ avl树构建

AVL树是一种自平衡的二叉搜索树，用于高效地插入、删除和查询数据。构建AVL树的基本步骤如下：

1. 首先，创建一个空的AVL树。
2. 从根节点开始，插入第一个元素作为根节点。
3. 对每个新插入的节点，更新它的平衡因子（左子树高度减去右子树高度）。
4. 如果插入节点后导致不平衡，进行相应的旋转操作来重新平衡树。
- 左左情况：插入到左子树的左子树上，需要进行右旋转。
- 右右情况：插入到右子树的右子树上，需要进行左旋转。
- 左右情况：插入到左子树的右子树上，先进行左旋转，再进行右旋转。
- 右左情况：插入到右子树的左子树上，先进行右旋转，再进行左旋转。
5. 更新树中的每个节点的平衡因子。
6. 重复步骤3至5，直到所有元素都被插入并且树保持平衡。

注意：在插入和删除操作后，必要时需要对AVL树进行旋转以保持平衡。旋转操作可以通过调整节点之间的连接关系来完成，从而保持树的平衡性质。

c++红黑树简单代码

红黑树是一种自平衡的二叉搜索树，它具有以下特性：
1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色的。
3. 每个叶子节点（NIL节点，空节点）是黑色的。
4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
5. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点。

下面是一个简单的C++实现红黑树的代码示例：

#include <iostream>

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int data) : data(data), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

class RedBlackTree {
private:
    Node* root;

    void rotateLeft(Node* node) {
        Node* rightChild = node->right;
        node->right = rightChild->left;

        if (rightChild->left != nullptr) {
            rightChild->left->parent = node;
        }

        rightChild->parent = node->parent;

        if (node->parent == nullptr) {
            root = rightChild;
        } else if (node == node->parent->left) {
            node->parent->left = rightChild;
        } else {
            node->parent->right = rightChild;
        }

        rightChild->left = node;
        node->parent = rightChild;
    }

    void rotateRight(Node* node) {
        Node* leftChild = node->left;
        node->left = leftChild->right;

        if (leftChild->right != nullptr) {
            leftChild->right->parent = node;
        }

        leftChild->parent = node->parent;

        if (node->parent == nullptr) {
            root = leftChild;
        } else if (node == node->parent->left) {
            node->parent->left = leftChild;
        } else {
            node->parent->right = leftChild;
        }

        leftChild->right = node;
        node->parent = leftChild;
    }

    void fixInsertion(Node* node) {
        while (node != root && node->parent->color == RED) {
            if (node->parent == node->parent->parent->left) {
                Node* uncle = node->parent->parent->right;

                if (uncle != nullptr && uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->right) {
                        node = node->parent;
                        rotateLeft(node);
                    }

                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rotateRight(node->parent->parent);
                }
            } else {
                Node* uncle = node->parent->parent->left;

                if (uncle != nullptr && uncle->color == RED) {
                    node->parent->color = BLACK;
                    uncle->color = BLACK;
                    node->parent->parent->color = RED;
                    node = node->parent->parent;
                } else {
                    if (node == node->parent->left) {
                        node = node->parent;
                        rotateRight(node);
                    }

                    node->parent->color = BLACK;
                    node->parent->parent->color = RED;
                    rotateLeft(node->parent->parent);
                }
            }
        }

        root->color = BLACK;
    }

public:
    RedBlackTree() : root(nullptr) {}

    void insert(int data) {
        Node* newNode = new Node(data);
        Node* current = root;
        Node* parent = nullptr;

        while (current != nullptr) {
            parent = current;

            if (data < current->data) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        newNode->parent = parent;

        if (parent == nullptr) {
            root = newNode;
        } else if (data < parent->data) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }

        fixInsertion(newNode);
    }

    void printInorder(Node* node) {
        if (node == nullptr) {
            return;
        }

        printInorder(node->left);
        std::cout << node->data << " ";
        printInorder(node->right);
    }

    void printTree() {
        printInorder(root);
    }
};

int main() {
    RedBlackTree tree;

    tree.insert(7);
    tree.insert(3);
    tree.insert(18);
    tree.insert(10);
    tree.insert(22);
    tree.insert(8);
    tree.insert(11);
    tree.insert(26);
    tree.insert(2);
    tree.insert(6);
    tree.insert(13);

    std::cout << "红黑树中序遍历结果：" << std::endl;
    tree.printTree();

    return 0;
}

这段代码实现了红黑树的插入操作，并提供了一个简单的测试例子。你可以根据需要进行修改和扩展。