建立一棵二叉树,并对其进行遍历(先序、中序、后序,层序),打印输出遍历结果;求二叉数的树的深度、统计叶子结点的个数、统计总的结点个数、交换左右子树等。
时间: 2024-11-30 16:15:46 浏览: 0
建立一棵二叉树通常涉及节点结构的定义,每个节点包含左子节点、右子节点以及一个值。以下是二叉树的基本操作:
1. **创建节点**:定义一个二叉树节点类,例如 `class TreeNode`,包含两个 `TreeNode` 类型的指针 `left` 和 `right`,以及一个存储数据的变量 `val`。
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
// 构造函数和其他辅助方法...
}
```
2. **构建二叉树**:通过递归或迭代的方式添加节点,如:
- 先序遍历(根-左-右):`root -> inorder(root.left) -> inorder(root.right)`
- 中序遍历(左-根-右):`inorder(root.left) -> root -> inorder(root.right)`
- 后序遍历(左-右-根):`inorder(root.left) -> inorder(root.right) -> root`
- 层次遍历(广度优先搜索):队列辅助,从根开始逐层访问。
```java
// 求深度
int depth(TreeNode node) {
if (node == null) return 0;
return Math.max(depth(node.left), depth(node.right)) + 1;
}
// 统计叶子节点
int countLeaves(TreeNode node) {
if (node == null) return 0;
return node.left == null && node.right == null ? 1 : countLeaves(node.left) + countLeaves(node.right);
}
// 统计总节点数
int totalNodes(TreeNode node) {
return node == null ? 0 : 1 + totalNodes(node.left) + totalNodes(node.right);
}
// 交换左右子树
void swapChildren(TreeNode& node) {
if (node != null) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
}
```
**遍历示例(使用递归)**:
```java
void printInOrder(TreeNode node) {
if (node != null) {
printInOrder(node.left);
System.out.print(node.val + " ");
printInOrder(node.right);
}
}
// 类似的函数可以为前序和后序遍历编写
```
阅读全文