Java代码实现创建一个线索化中序线索二叉树,并且通过调用求结点的前驱结点算法来按中根次序遍历一颗中序线索二叉树,实例化
时间: 2024-03-21 08:41:53 浏览: 62
好的,下面是 Java 代码实现:
```java
class ThreadedBinaryTreeNode {
int val;
ThreadedBinaryTreeNode left;
ThreadedBinaryTreeNode right;
boolean isLeftThreaded;
boolean isRightThreaded;
public ThreadedBinaryTreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
this.isLeftThreaded = false;
this.isRightThreaded = false;
}
}
class ThreadedBinaryTree {
ThreadedBinaryTreeNode root;
ThreadedBinaryTreeNode prev;
public ThreadedBinaryTree(int[] nums) {
root = new ThreadedBinaryTreeNode(nums[0]);
prev = null;
createThreadedBinaryTree(root, nums, 0);
}
private void createThreadedBinaryTree(ThreadedBinaryTreeNode node, int[] nums, int index) {
if (index >= nums.length) {
return;
}
if (nums[index] < node.val) {
if (node.left == null) {
node.left = new ThreadedBinaryTreeNode(nums[index]);
createThreadedBinaryTree(node.left, nums, index + 1);
} else {
createThreadedBinaryTree(node.left, nums, index);
}
} else {
if (node.right == null) {
node.right = new ThreadedBinaryTreeNode(nums[index]);
createThreadedBinaryTree(node.right, nums, index + 1);
} else {
createThreadedBinaryTree(node.right, nums, index);
}
}
}
public void inOrderTraversal() {
ThreadedBinaryTreeNode curr = root;
while (curr != null) {
while (curr.isLeftThreaded == false) {
curr = curr.left;
}
System.out.print(curr.val + " ");
while (curr.isRightThreaded == true) {
curr = curr.right;
System.out.print(curr.val + " ");
}
curr = curr.right;
}
}
public void createInOrderThreadedBinaryTree() {
createInOrderThreadedBinaryTreeHelper(root);
}
private void createInOrderThreadedBinaryTreeHelper(ThreadedBinaryTreeNode node) {
if (node == null) {
return;
}
createInOrderThreadedBinaryTreeHelper(node.left);
if (node.left == null) {
node.isLeftThreaded = true;
node.left = prev;
}
if (prev != null && prev.right == null) {
prev.isRightThreaded = true;
prev.right = node;
}
prev = node;
createInOrderThreadedBinaryTreeHelper(node.right);
}
}
public class Main {
public static void main(String[] args) {
int[] nums = {4, 2, 6, 1, 3, 5, 7};
ThreadedBinaryTree tree = new ThreadedBinaryTree(nums);
tree.createInOrderThreadedBinaryTree();
tree.inOrderTraversal();
}
}
```
这里实现了一个线索化的中序线索二叉树,并且按中根次序遍历了这个二叉树。
在 `ThreadedBinaryTree` 类中,`root` 是二叉树的根节点,`prev` 是中序遍历时的前驱节点。`createThreadedBinaryTree` 方法用来根据数组构建二叉树,`createInOrderThreadedBinaryTree` 方法用来创建中序线索二叉树,`inOrderTraversal` 方法用来按中根次序遍历中序线索二叉树。
在 `ThreadedBinaryTreeNode` 类中,`val` 是节点的值,`left` 和 `right` 是左右子节点,`isLeftThreaded` 和 `isRightThreaded` 表示左右子节点是否为线索。当 `isLeftThreaded` 为 `true` 时,`left` 指向该节点在中根次序下的前驱节点;当 `isRightThreaded` 为 `true` 时,`right` 指向该节点在中根次序下的后继节点。
在 `Main` 类中,构建了一个数组 `{4, 2, 6, 1, 3, 5, 7}`,通过 `ThreadedBinaryTree` 类构建了一棵二叉树,并且创建了中序线索二叉树,并将中序遍历结果输出。
阅读全文