二叉树相关知识全解析

### 二叉树相关知识全解析 #### 1. 利用后序遍历和栈计算表达式 后序遍历可以结合栈来计算表达式。其算法步骤如下： 1. 初始化一个空栈 S。 2. 当未到达遍历结束时： - 获取下一个元素 x。 - 若 x 是操作数，将其压入栈 S。 - 若 x 是运算符： - 从栈 S 中弹出操作数。 - 应用该运算符进行计算。 - 将计算结果压入栈 S。 3. 遍历结束后，弹出栈 S 的元素，该元素即为表达式的值。 例如，对于后序遍历序列 `54 37 + 72 5 13 * - /`，计算过程如下： | 步骤 | 操作 | 栈 S 内容 | | ---- | ---- | ---- | | 1 | 元素 54，压入栈 S | 54 | | 2 | 元素 37，压入栈 S | 54 37 | | 3 | 元素 +，弹出 37 和 54，计算 54 + 37 = 91，压入栈 S | 91 | | 4 | 元素 72，压入栈 S | 91 72 | | 5 | 元素 5 和 13，依次压入栈 S | 91 72 5 13 | | 6 | 元素 *，弹出 13 和 5，计算 5 * 13 = 65，压入栈 S | 91 72 65 | | 7 | 元素 -，弹出 65 和 72，计算 72 - 65 = 7，压入栈 S | 91 7 | | 8 | 元素 /，弹出 7 和 91，计算 91 / 7 = 13，压入栈 S | 13 | | 9 | 遍历结束，弹出栈 S 的元素 | 13 | 需要注意的是，从栈中弹出操作数时，先弹出的是第二个操作数，后弹出的是第一个操作数。这对于加法和乘法无关紧要，但对于减法和除法很重要。 #### 2. 二叉树的表示 二叉树的每个节点至少包含三个字段：存储节点数据的字段、指向左子树的指针和指向右子树的指针。以下是用 Java 实现的 `TreeNode` 类： ```java class TreeNode { NodeData data; TreeNode left, right; TreeNode(NodeData d) { data = d; left = right = null; } } ``` 为了保持灵活性，`TreeNode` 类使用了通用数据类型 `NodeData`。任何使用 `TreeNode` 的程序都必须提供自己的 `NodeData` 定义。例如，如果节点数据是整数，`NodeData` 可以定义如下： ```java class NodeData { int num; public NodeData(int n) { num = n; } } ``` 如果数据是字符，也可以使用类似的定义。而且，`NodeData` 不限于单字段数据，可以包含任意数量的字段。 除了节点，我们还需要知道二叉树的根节点。一旦知道根节点，就可以通过左右指针访问树中的所有节点。因此，二叉树仅由其根节点定义。以下是 `BinaryTree` 类的定义： ```java class BinaryTree { TreeNode root; // 该类的唯一字段 BinaryTree() { root = null; } // 类中的方法 } ``` 构造函数实际上不是必需的，因为 Java 在创建 `BinaryTree` 对象时会将 `root` 设置为 `null`。但我们包含它是为了强调在空二叉树中，`root` 为 `null`。 在程序中，我们可以将 `TreeNode` 类和 `BinaryTree` 类放在同一个文件中，此时需要省略 `public` 关键字。 #### 3. 构建二叉树 我们可以编写一个函数来构建二叉树。假设我们要构建一个由单个节点组成的树，数据格式为 `A @ @`，其中每个 `@` 表示空指针的位置。以下是构建二叉树的函数： ```java static TreeNode buildTree(Scanner in) { String str = in.next(); if (str.equals("@")) return null; TreeNode p = new TreeNode(new NodeData(str)); p.left = buildTree(in); p.right = buildTree(in); return p; } ``` 该函数从与 `Scanner` 关联的输入流中读取数据。`NodeData` 类的定义如下： ```java class NodeData { String word; public NodeData(String w) { word = w; } } ``` 我们可以从以下构造函数调用 `buildTree`： ```java public BinaryTree(Scanner in) { root = buildTree(in); } ``` 假设用户类将树数据存储在文件 `btree.in` 中，可以使用以下代码创建二叉树： ```java Scanner in = new Scanner(new FileReader("btree.in")); BinaryTree bt = new BinaryTree(in); ``` 构建树后，我们可以通过遍历树来检查其是否正确构建。以下是 `BinaryTree` 类中实现的前序、中序和后序遍历方法： ```java import java.util.*; public class BinaryTree { TreeNode root; public BinaryTree() { root = null; } public BinaryTree(Scanner in) { root = buildTree(in); } public static TreeNode buildTree(Scanner in) { String str = in.next(); if (str.equals("@")) return null; TreeNode p = new TreeNode(new NodeData(str)); p.left = buildTree(in); p.right = buildTree(in); return p; } public void preOrder() { preOrderTraversal(root); } public void preOrderTraversal(TreeNode node) { if (node!= null) { node.data.visit(); preOrderTraversal(node.left); preOrderTraversal(node.right); } } public void inOrder() { inOrderTraversal(root); } public void inOrderTraversal(TreeNode node) { if (node!= null) { inOrderTraversal(node.left); node.data.visit(); inOrderTraversal(node.right); } } public void postOrder() { postOrderTraversal(root); } public void postOrderTraversal(TreeNode node) { if (node!= null) { postOrderTraversal(node.left); postOrderTraversal(node.right); node.data.visit(); } } } ``` 遍历方法都使用了 `node.data.visit()` 语句，因此 `NodeData` 类需要包含 `visit` 方法。以下是 `visit`