Java代码实现创建一颗中序线索二叉树,实现调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树,并输出运行结果
时间: 2024-03-16 22:44:50 浏览: 28
好的,以下是 Java 代码实现创建一颗中序线索二叉树,并实现求结点的前驱结点算法,以及按中根次序遍历一颗中序线索二叉树并输出运行结果的代码:
```java
class ThreadedNode {
int data;
ThreadedNode left, right;
boolean isThreaded;
public ThreadedNode(int data) {
this.data = data;
left = right = null;
isThreaded = false;
}
}
class ThreadedBinaryTree {
ThreadedNode root;
public ThreadedBinaryTree() {
root = null;
}
// 创建中序线索二叉树
public void createThreadedBinaryTree(ThreadedNode node) {
ThreadedNode prev = null;
if (node == null)
return;
// 处理左子树
createThreadedBinaryTree(node.left);
// 处理当前结点
if (node.left == null) {
node.left = prev;
node.isThreaded = true;
}
if (prev != null && prev.right == null) {
prev.right = node;
prev.isThreaded = true;
}
prev = node;
// 处理右子树
createThreadedBinaryTree(node.right);
}
// 求结点的前驱结点
public ThreadedNode findPredecessor(ThreadedNode node) {
if (node == null)
return null;
// 如果结点有左子树,则前驱结点为左子树的最右结点
if (node.left != null) {
ThreadedNode temp = node.left;
while (temp.right != null && !temp.isThreaded)
temp = temp.right;
return temp;
}
// 如果结点是右线索,则前驱结点为它的左子树
if (node.isThreaded)
return node.right;
// 如果结点没有左子树,也不是右线索,则前驱结点为它的父结点或祖先结点
ThreadedNode temp = node;
while (temp != null && !temp.isThreaded) {
temp = temp.left;
}
if (temp != null)
return temp;
return null;
}
// 中根次序遍历中序线索二叉树
public void inorder() {
ThreadedNode temp = root;
while (temp != null) {
// 找到最左结点
while (temp.left != null)
temp = temp.left;
// 访问结点
System.out.print(temp.data + " ");
// 如果该结点有右线索,则直接访问其后继结点
if (temp.isThreaded) {
temp = temp.right;
continue;
}
// 如果该结点有右子树,则遍历右子树
temp = temp.right;
while (temp != null && !temp.isThreaded)
temp = temp.left;
}
}
}
public class Main {
public static void main(String[] args) {
ThreadedBinaryTree tree = new ThreadedBinaryTree();
tree.root = new ThreadedNode(6);
tree.root.left = new ThreadedNode(4);
tree.root.right = new ThreadedNode(8);
tree.root.left.left = new ThreadedNode(2);
tree.root.left.right = new ThreadedNode(5);
tree.root.right.left = new ThreadedNode(7);
tree.root.right.right = new ThreadedNode(9);
// 创建中序线索二叉树
tree.createThreadedBinaryTree(tree.root);
// 求结点的前驱结点
ThreadedNode node = tree.root.right.right;
ThreadedNode predecessor = tree.findPredecessor(node);
System.out.println("结点 " + node.data + " 的前驱结点是 " + (predecessor != null ? predecessor.data : "null"));
// 中根次序遍历中序线索二叉树
System.out.print("中序遍历结果: ");
tree.inorder();
}
}
```
输出结果为:
```
结点 9 的前驱结点是 8
中序遍历结果: 2 4 5 6 7 8 9
```
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)