二叉树采用二叉链表存储,实现如下算法:①创建一棵二叉树;②交换该二叉树中的所有结点的左右子树
时间: 2024-12-07 20:14:00 浏览: 70
二叉树采用二叉链表存储,其实现涉及到节点结构的设计以及对二叉树操作的理解。以下是您提到的两个算法步骤:
**① 创建一棵二叉树:**
首先,需要定义一个二叉树节点类,包含三个属性:值(value)、左子节点(left)和右子节点(right),通常会有一个指向父节点的指针,用于构建树形结构。创建节点时,从根开始,每次插入新节点时,如果值小于当前节点,插入到左子树,反之插入到右子树。
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
```
**② 交换所有结点的左右子树:**
这个过程可以递归完成。对于每个节点,我们需要交换它的左右子节点。核心操作就是将`left`指向下原本的`right`节点,然后将`right`指向上原本的`left`节点(如果有的话)。递归地对新的左右子节点进行同样的操作,直到遍历完整棵树。
```java
public void swapLeftAndRightSubtrees(TreeNode root) {
if (root != null) {
// 临时保存当前节点的原左右子节点
TreeNode tempLeft = root.left;
TreeNode tempRight = root.right;
// 交换左右子节点
root.left = tempRight;
root.right = tempLeft;
// 递归处理新的左右子树
swapLeftAndRightSubtrees(root.left);
swapLeftAndRightSubtrees(root.right);
}
}
```
阅读全文