1、手动建立一个小型二叉树,包括树的结点和结点间的关系。2、设计程序实现通过输入先序、中序遍历序列建立二叉树的操作。3、设计程序实现通过输入中序、后序遍历序列建立二叉树的操作。4、通过实例测试程序正确性。要求写出完整的辅助代码。
时间: 2024-10-26 19:16:35 浏览: 16
1. **手动建立二叉树(递归方式)**:
我们可以使用节点类 `TreeNode` 来表示二叉树中的每个元素,包含一个值 `val` 和两个子节点 `left` 和 `right`。这里用递归的方法创建一个简单的二叉树:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
}
public TreeNode buildTreePreIn(String[] preorder, String[] inorder) {
if (preorder == null || preorder.length == 0) return null;
int rootIndex = inorder.indexOf(preorder[0]);
TreeNode root = new TreeNode(Integer.parseInt(preorder[0]));
root.left = buildTreePreIn(Arrays.copyOfRange(preorder, 1, rootIndex + 1),
Arrays.copyOfRange(inorder, 0, rootIndex));
root.right = buildTreePreIn(Arrays.copyOfRange(preorder, rootIndex + 1),
Arrays.copyOfRange(inorder, rootIndex + 1));
return root;
}
```
2. **根据先序和中序遍历重建二叉树**:
先序遍历(根->左->右)的第一个元素是根节点,中序遍历(左->根->右)可以帮助我们找到根节点的位置。
3. **根据中序和后序遍历重建二叉树**:
后序遍历(左->右->根),同样先找到根节点,然后分别从中序遍历中去掉根节点后的部分,得到左右子树对应的中序遍历。
4. **测试程序正确性**:
可以编写一些测试用例,比如构建特定的二叉树结构,然后比较重建后的二叉树是否与预期一致。你可以使用JUnit等单元测试框架进行验证。
**完整辅助代码**:
```java
import java.util.Arrays;
// ... (已有的TreeNode类)
public void testBuildTrees() {
// 测试用例1
String[] preorder1 = {"1", "2", "3", "4"};
String[] inorder1 = {"4", "2", "1", "3"};
TreeNode expected1 = new TreeNode(1);
expected1.left = new TreeNode(2);
expected1.right = new TreeNode(3);
expected1.left.left = new TreeNode(4);
assertEquals(expected1, buildTreePreIn(preorder1, inorder1));
// 测试用例2
String[] preorder2 = {"A", "B", "D", "E", "C"};
String[] inorder2 = {"D", "B", "E", "A", "C"};
TreeNode expected2 = new TreeNode('A');
expected2.left = new TreeNode('B');
expected2.left.left = new TreeNode('D');
expected2.left.right = new TreeNode('E');
expected2.right = new TreeNode('C');
assertEquals(expected2, buildTreePreIn(preorder2, inorder2));
// 添加更多测试用例...
}
```
阅读全文