二叉树的链表实现

在计算机科学中，二叉树是一种常见的数据结构。为了便于管理和操作，我们可以通过链表的方式来表示二叉树。以下是具体的实现方法：

首先，定义一个二叉树节点的结构体：

#include 
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

接下来，定义一些辅助类型以简化后续代码：

typedef struct TreeNode TreeNode;
typedef TreeNode* BTree;

为了向二叉树中插入新节点，我们可以编写如下函数：

BTree insertNode(BTree root, int value) {
    BTree newNode = new TreeNode();
    newNode->data = value;
    newNode->left = nullptr;
    newNode->right = nullptr;

    if (root == nullptr) {
        return newNode;
    }

    BTree current = root;
    BTree parent = nullptr;

    while (current != nullptr) {
        parent = current;
        if (current->data > value) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    if (parent->data > value) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    return root;
}

有了插入函数后，我们可以轻松地创建一棵二叉树：

BTree createBTree(int* data, int len) {
    BTree root = nullptr;
    for (int i = 0; i         root = insertNode(root, data[i]);
    }
    return root;
}

最后，我们还需要一个函数来遍历并输出二叉树的内容：

void printBTree(BTree root) {
    if (root == nullptr) {
        cout <<"树为空" <        return;
    }

    cout <<"左子树内容：\n";
    BTree ptr = root->left;
    while (ptr != nullptr) {
        cout <<"[" <data <<"]\n";
        ptr = ptr->left;
    }

    cout <<"右子树内容：\n";
    ptr = root->right;
    while (ptr != nullptr) {
        cout <<"[" <data <<"]\n";
        ptr = ptr->right;
    }
}

以下是一个完整的示例程序：

int main() {
    BTree root = nullptr;
    int data[] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
    root = createBTree(data, 9);

    cout <<"树的结点内容:\n";
    printBTree(root);

    return 0;
}