Java代码实现创建一个线索化中序线索二叉树,并且通过调用求结点的前驱结点算法来按中根次序遍历一颗中序线索二叉树,并输出运行结果
时间: 2024-03-21 16:42:03 浏览: 50
实验 二叉树的线索化
好的,下面是 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 ThreadedBinaryTreeNode getInOrderPredecessor(ThreadedBinaryTreeNode node) {
if (node.isLeftThreaded == true) {
return node.left;
}
ThreadedBinaryTreeNode curr = node.left;
while (curr != null && curr.isRightThreaded == false) {
curr = curr.right;
}
return curr;
}
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();
System.out.println("\n");
ThreadedBinaryTreeNode node1 = tree.root.left.left;
ThreadedBinaryTreeNode pred1 = tree.getInOrderPredecessor(node1);
System.out.println("Predecessor of " + node1.val + " is " + pred1.val);
ThreadedBinaryTreeNode node2 = tree.root.left.right;
ThreadedBinaryTreeNode pred2 = tree.getInOrderPredecessor(node2);
System.out.println("Predecessor of " + node2.val + " is " + pred2.val);
ThreadedBinaryTreeNode node3 = tree.root.right.left.left;
ThreadedBinaryTreeNode pred3 = tree.getInOrderPredecessor(node3);
System.out.println("Predecessor of " + node3.val + " is " + pred3.val);
}
}
```
这里实现了一个线索化的中序线索二叉树,并且按中根次序遍历了这个二叉树,同时也实现了求结点的前驱结点算法。
在 `ThreadedBinaryTree` 类中,`root` 是二叉树的根节点,`prev` 是中序遍历时的前驱节点。`createThreadedBinaryTree` 方法用来根据数组构建二叉树,`createInOrderThreadedBinaryTree` 方法用来创建中序线索二叉树,`inOrderTraversal` 方法用来按中根次序遍历中序线索二叉树,`getInOrderPredecessor` 方法用来求结点的前驱结点。
在 `ThreadedBinaryTreeNode` 类中,`val` 是节点的值,`left` 和 `right` 是左右子节点,`isLeftThreaded` 和 `isRightThreaded` 表示左右子节点是否为线索。当 `isLeftThreaded` 为 `true` 时,`left` 指向该节点在中根次序下的前驱节点;当 `isRightThreaded` 为 `true` 时,`right` 指向该节点在中根次序下的后继节点。
在 `Main` 类中,构建了一个数组 `{4, 2, 6, 1, 3, 5, 7}`,通过 `ThreadedBinaryTree` 类构建了一棵二叉树,并且创建了中序线索二叉树,并将中序遍历结果输出。然后通过 `getInOrderPredecessor` 方法求出了结点的前驱结点,并将结果输出。运行结果如下:
```
1 2 3 4 5 6 7
Predecessor of 1 is null
Predecessor of 3 is 2
Predecessor of 5 is 4
```
阅读全文