C语言实现llink-rlink存储二叉排序树

"这篇代码示例展示了如何使用llink-rlink方式存储二叉排序树，并用C语言实现。代码包括创建、输入数据和输出数据的功能。" 二叉排序树（Binary Sort Tree，BST），又称为二叉查找树，是一种特殊的二叉树结构，其每个节点的值都大于其左子树中的所有节点的值，小于其右子树中的所有节点的值。这种特性使得在二叉排序树中进行查找、插入和删除操作的时间复杂度可以达到O(logn)。 在"llink-rlink"方式中，"llink"代表左孩子，"rlink"代表右孩子，这是对二叉树节点的两个指针字段的通俗称呼。在C语言中，通常用两个结构体指针成员变量来表示这些链接，如代码中的`lson`和`rson`。 代码中的`struct tree`定义了二叉树节点的数据结构，包含三个部分：整型数据`data`，用于存储节点的值；`lson`指针，指向左子节点；`rson`指针，指向右子节点。 `input`函数是用于向二叉排序树中插入节点的函数。它接收一个二叉树根节点的指针和待插入的新节点指针。如果根节点为空，新节点成为根节点；否则，根据新节点的值与根节点的值比较，决定将新节点插入到左子树还是右子树。 `creat`函数用于创建二叉排序树。首先初始化`p1`为NULL，然后通过循环读取用户输入的整数（直到输入0结束），每次读取一个数值就创建一个新的节点`p2`，并将该节点插入到当前树`p1`的合适位置。最后返回构建好的二叉排序树的根节点。 `output`函数则实现了对二叉排序树的中序遍历输出。中序遍历的顺序是左子树 -> 节点 -> 右子树，这正好符合二叉排序树的性质，即输出的数值按升序排列。 `main`函数中，首先调用`creat`函数创建二叉排序树，然后调用`output`函数进行输出。程序结束前，用`getch()`函数暂停程序，以便观察输出结果。 这段代码虽然简单，但它很好地展示了二叉排序树的基本操作。通过理解并实践这样的代码，开发者可以深入理解二叉排序树的内部工作原理以及如何在实际编程中运用这种数据结构。