欧姆龙旋转编码器应用：构建二叉树数据结构

构建二叉树数据结构

这部分讲解如何利用一组数据构建一个二叉树来存放数据。

举个例子，假设我们要从文件中读取一组整数，然后用一个二叉树来保存这些整数。首先，读取的第一个整数会被存储在根节点 root 上。之后，每读取一个整数，就在以 root 为根的二叉树上插入一个新的节点来存储这个整数。最终构建的二叉树需要满足以下特性：对于任意节点 A，A 的值大于等于其左子树中所有节点的值，并且小于其右子树中所有节点的值。

以下代码演示了如何构建这样一棵二叉树。

代码的第 4-9 行定义了二叉树节点的数据类型，它包含两部分：数据域和指针域。数据域定义了要存储的数据元素类型，而指针域定义了两个指针：左指针和右指针，它们的类型必须与二叉树节点的数据类型一致。

代码的第 11-27 行定义了一个递归函数 insertTree(TreeNode *root, int val)，用于向 root 指向的二叉树添加新节点。每次添加一个节点时，存储元素值 val。如果 root 指向的二叉树为空，则将新节点作为二叉树的根节点。否则：

1. 如果 val 小于或等于 root 节点的值，则将新节点插入到 root 节点的左子树上；
2. 如果 val 大于 root 节点的值，则将新节点插入到 root 节点的右子树上。

代码的第 29-34 行定义了一个递归函数 delTree(TreeNode *root)，用于删除 root 指向的二叉树，并释放各个节点占用的存储空间。该函数首先分别删除根节点的左子树和右子树，然后再删除根节点本身。

代码的第 36-51 行定义了一个递归函数 printTree(TreeNode *root)，用于查看 root 指向的二叉树的形状。每个节点占一行，根节点的值输出在第一行的第一个位置。输出一个节点后，接着输出它的左子树，然后再输出它的右子树。第 K 层的节点向右缩进 K 个位置。如果一个子树为空，则在对应的行输出一个 $ 字符。例如，图 12-2 展示了一棵二叉树的形状，图 12-3 是 printTree() 函数的输出结果。

在主函数中，使用一个 TreeNode 类型的指针 root 来记录二叉树的根节点。开始时，二叉树为空。每次从输入文件中读取一个整数 val 时，就调用一次函数 insertTree(TreeNode *root, int val)，将 val 存储到 root 指向的二叉树上。

(图 12-2 二叉树形状)

(图 12-3 printTree() 输出结果)

8 4 12 2 7 20

8 4 2 $ $ 7 $ $ 12 $ 20 $ $