二叉树的原理与操作详解

### 二叉树的原理与操作详解 #### 一、二叉树基础概念 二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。我们这里主要讨论的是二叉搜索树，其定义特征为：节点的左子节点的键值必须小于其父节点，而右子节点的键值必须大于或等于其父节点。 为了更好地理解树的概念，我们可以类比计算机系统中的分层文件结构。在分层文件结构中，设备的根目录（如 C:\）是树的根，根目录下一级的目录是其子节点，可能存在多个级别的子目录，文件则代表叶子节点，它们没有子节点。不过，分层文件结构并非二叉树，因为一个目录可能有多个子节点。而且，在文件结构中，子目录只包含对其他子目录或文件的引用，不包含数据，只有文件包含数据；而在二叉树中，每个节点都包含数据，除叶子节点外，所有节点还包含对其他节点的引用。 #### 二、二叉搜索树工作原理 我们将通过 Binary Tree Workshop 小程序来演示常见的二叉树操作，包括查找节点、插入节点、遍历树和删除节点，然后再查看对应的 Java 代码实现。 ##### （一）Binary Tree Workshop 小程序使用 启动 Binary Tree Workshop 小程序后，会看到一个随机生成的树，节点中的键值范围是 0 到 99。在实际应用中，键值范围可能更大。该小程序的树深度限制为 5 层，以确保所有节点都能在屏幕上显示，而实际树的层数是无限的（直到内存耗尽）。 要创建新树，点击 Fill 按钮，程序会提示输入树中的节点数量，范围是 1 到 31，输入 15 可以得到一个具有代表性的树。输入数量后，再按两次 Fill 按钮即可生成新树，你可以尝试创建不同节点数量的树进行实验。 在生成的树中，有些树可能是不平衡的，即大部分节点集中在根节点的一侧。树不平衡的原因是数据项的插入顺序，如果键值是随机插入的，树会大致平衡；但如果是升序或降序插入，树就会变得不平衡。例如，若按升序插入键值，所有值都会成为右子节点；按降序插入则会成为左子节点。在小程序中，键值是随机生成的，但仍可能出现局部的升序或降序序列，导致局部不平衡。当使用 Fill 按钮创建大量节点时，由于树的深度限制，可能无法得到所需数量的节点，而在实际树中不会出现这个问题。 ##### （二）Java 代码实现树的表示 在 Java 中实现二叉树，常见的方法是将节点存储在内存的不相关位置，并通过每个节点中的引用连接其子节点。我们也可以将树表示为数组，但在示例代码中，我们使用引用连接节点的方法。 1. **Node 类** ```java class Node { int iData; // 用作键值的数据 double fData; // 其他数据 Node leftChild; // 该节点的左子节点 Node rightChild; // 该节点的右子节点 public void displayNode() { // (见清单 8.1 中的方法体) } } ``` 有些程序员会在节点中包含对其父节点的引用，这会简化某些操作，但也会使其他操作变得复杂，所以我们这里不包含。同时，我们包含了一个 `displayNode()` 方法来显示节点数据，但这里不给出其具体代码。 另外，还有一种设计 Node 类的方法，即使用对表示数据项的对象的引用： ```java class Node { Person p1; // 对 Person 对象的引用 Node leftChild; // 该节点的左子节点 Node rightChild; // 该节点的右子节点 } class Person { int iData; double fData; } ``` 这种方法在概念上更清晰地区分了节点和其所持有的数据项，但会使代码更复杂，所以我们采用第一种方法。 2. **Tree 类** ```java class Tree { private Node root; // Tree 类中唯一的数据字段 public void find(int key) { } public void insert(int id, double dd) { } public void delete(int id) { } // 各种其他方法 } // 结束 Tree 类 ``` Tree 类用于实例化树对象，它只有一个字段 `root` 来存储根节点，因为其他节点都可以从根节点访问。该类有多个方法，用于查找、插入和删除节点，以及进行不同类型的遍历和显示树。 3. **TreeApp 类** ```java class TreeApp { public static void main(String[] args) { Tree theTree = new Tree(); // 创建一个树 theTree.insert(50, 1.5); // 插入 3 个节点 theTree.insert(25, 1.7); theTree.insert(75, 1.9); Node found = theTree.find(25); // 查找键值为 25 的节点 if(found != null) System.out.println("Found the node with key 25"); else System.out.println("Could not find node with key 25"); } // 结束 main() } // 结束 TreeApp 类 ``` TreeApp 类的 `main()` 方法演示了如何创建树、插入节点并查找特定键值的节点。在实际应用中，`main()` 方法还可以提供一个简单的用户界面，让你通过键盘选择插入、查找、删除或执行其他操作。 #### 三、具体树操作实现 ##### （一）查找节点 查找具有特定键值的节点是树的主要操作中最简单的，我们从这里开始介绍。 1. **使用 Workshop 小程序查找节点** 在 Workshop 小程序中，选择一个节点（最好是靠近树底部的节点），该节点显示的数字就是其键值。假设我们要查找键值为 57 的节点，点击 Find 按钮，程序会提示输入要查找的节点值，输入 57 后再点击两次 Find 按钮。在查找过程中，提示信息会显示“Going to left child”或“Going to right child”，红色箭头会向下移动一层到左或右。例如，从根节点开始，若根节点的值为 63，因为 57 小于 63，所以程序知道目标节点在树的左侧；根节点的左子节点值为 27，57 大于 27，所以目标节点在 27 的右子树中；继续比较，最终找到键值为 57 的节点。小程序找到节点后，只会显示找到的消息，而实际程序可能会对找到的节点执行一些操作，如显示其内容或更改其字段。 2. **Java 代码实现查找节点** ```java public Node find(int key) // 查找具有给定键值的节点 { // (假设树非空) Node current = root; // 从根节点开始 ```