java代码实现线索化构造一棵中序线索二叉树,并在其中实现调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树,按后根次序遍历中序线索二叉树,插入、删除操作
时间: 2024-03-17 08:47:08 浏览: 70
好的,我会尽力回答你的问题。首先,中序线索二叉树是一种特殊的二叉树,它的每个结点都有两个指针,一个指向它的前驱结点,一个指向它的后继结点。这种特殊的二叉树能够提高对二叉树的遍历效率。
以下是 Java 代码实现线索化构造一棵中序线索二叉树,并在其中实现调用求结点的前驱结点算法:
```java
public class ThreadedBinaryTree {
private ThreadedNode root;
private ThreadedNode pre;
public ThreadedBinaryTree() {
root = null;
pre = null;
}
public void setRoot(ThreadedNode root) {
this.root = root;
}
public void inThreaded(ThreadedNode node) {
if (node != null) {
inThreaded(node.getLeftChild());
if (node.getLeftChild() == null) {
node.setLeftTag(1);
node.setLeftChild(pre);
}
if (pre != null && pre.getRightChild() == null) {
pre.setRightTag(1);
pre.setRightChild(node);
}
pre = node;
inThreaded(node.getRightChild());
}
}
public ThreadedNode getRoot() {
return root;
}
public ThreadedNode inOrderThreadedSearch(int value) {
ThreadedNode node = root;
while (node != null) {
if (node.getValue() == value) {
return node;
} else if (value < node.getValue()) {
if (node.getLeftTag() == 0) {
node = node.getLeftChild();
} else {
return node.getLeftChild();
}
} else {
if (node.getRightTag() == 0) {
node = node.getRightChild();
} else {
return node.getRightChild();
}
}
}
return null;
}
}
```
接下来,我们来实现按中根次序遍历一颗中序线索二叉树:
```java
public void inOrder() {
ThreadedNode node = root;
while (node != null) {
while (node.getLeftTag() == 0) {
node = node.getLeftChild();
}
System.out.print(node.getValue() + " ");
while (node.getRightTag() == 1) {
node = node.getRightChild();
System.out.print(node.getValue() + " ");
}
node = node.getRightChild();
}
System.out.println();
}
```
最后,我们来实现按后根次序遍历中序线索二叉树:
```java
public void postOrder() {
ThreadedNode node = root;
while (node != null && node.getLeftTag() == 0) {
node = node.getLeftChild();
}
while (node != null) {
if (node.getRightTag() == 0 && node.getRightChild() != null) {
node = node.getRightChild();
while (node.getLeftTag() == 0) {
node = node.getLeftChild();
}
} else {
System.out.print(node.getValue() + " ");
while (node.getRightTag() == 1) {
node = node.getRightChild();
System.out.print(node.getValue() + " ");
}
if (node == root) {
break;
}
node = node.getRightChild();
}
}
System.out.println();
}
```
至于插入和删除操作,可以参考普通二叉树的实现方式,但需要注意维护线索信息。
阅读全文