写一个线索二叉树的java程序
时间: 2024-05-09 07:20:25 浏览: 5
线索二叉树是一种特殊的二叉树,它在节点的左右子树指针上添加了线索。线索指向的是该节点在中序遍历中的前驱或后继节点。以下是一个简单的线索二叉树的Java程序示例:
```
class Node {
int data;
Node left, right;
boolean leftThread, rightThread;
public Node(int value) {
data = value;
left = right = null;
leftThread = rightThread = false;
}
}
public class ThreadedBinaryTree {
Node root;
public ThreadedBinaryTree() {
root = null;
}
// 中序遍历线索化二叉树
public void inOrderThread() {
if (root == null) return;
Node cur = root;
Node prev = null;
while (cur != null) {
while (!cur.leftThread && cur.left != null) {
cur = cur.left;
}
if (cur.left == null) {
cur.leftThread = true;
cur.left = prev;
}
if (prev != null && prev.right == null) {
prev.rightThread = true;
prev.right = cur;
}
prev = cur;
cur = cur.right;
}
}
// 中序遍历线索二叉树
public void inOrderTraversal() {
if (root == null) return;
Node cur = root;
while (cur.left != null) {
cur = cur.left;
}
while (cur != null) {
System.out.print(cur.data + " ");
if (cur.rightThread) {
cur = cur.right;
} else {
cur = cur.right;
while (cur != null && !cur.leftThread) {
cur = cur.left;
}
}
}
System.out.println();
}
public static void main(String[] args) {
ThreadedBinaryTree tree = new ThreadedBinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.inOrderThread();
tree.inOrderTraversal();
}
}
```
在上述程序中,我们定义了一个`Node`类来表示二叉树的节点。每个节点包含数据、左右子树指针和左右线索指针。我们还定义了一个`ThreadedBinaryTree`类来表示线索二叉树。该类包含一个根节点和两个方法:`inOrderThread()`和`inOrderTraversal()`。`inOrderThread()`方法用于将二叉树线索化,即在每个节点的左右子树指针上添加线索。该方法使用中序遍历的方式将二叉树遍历,并在遍历过程中添加线索。`inOrderTraversal()`方法用于中序遍历线索二叉树,并输出每个节点的数据。
在`main()`方法中,我们创建了一个示例二叉树,并调用`inOrderThread()`方法将其线索化。然后,我们调用`inOrderTraversal()`方法中序遍历线索二叉树,并输出每个节点的数据。输出结果应该为:`4 2 5 1 6 3 7`。