java代码实现线索化构造一棵中序线索二叉树,并在其中实现调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树,按后根次序遍历中序线索二叉树,插入、删除操作,并实例化该类
时间: 2024-03-17 15:47:11 浏览: 10
好的,以下是完整的 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;
}
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();
}
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();
}
public void insert(int value) {
ThreadedNode newNode = new ThreadedNode(value);
if (root == null) {
root = newNode;
return;
}
ThreadedNode node = root;
ThreadedNode parent;
while (true) {
parent = node;
if (value < node.getValue()) {
node = node.getLeftChild();
if (node == null) {
parent.setLeftChild(newNode);
newNode.setParent(parent);
inThreaded(newNode);
return;
}
} else {
node = node.getRightChild();
if (node == null) {
parent.setRightChild(newNode);
newNode.setParent(parent);
inThreaded(newNode);
return;
}
}
}
}
public boolean delete(int value) {
ThreadedNode current = root;
ThreadedNode parent = root;
boolean isLeftChild = true;
while (current.getValue() != value) {
parent = current;
if (value < current.getValue()) {
isLeftChild = true;
current = current.getLeftChild();
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null) {
return false;
}
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root) {
root = null;
} else if (isLeftChild) {
parent.setLeftChild(null);
} else {
parent.setRightChild(null);
}
return true;
} else if (current.getRightChild() == null) {
if (current == root) {
root = current.getLeftChild();
} else if (isLeftChild) {
parent.setLeftChild(current.getLeftChild());
} else {
parent.setRightChild(current.getLeftChild());
}
current.getLeftChild().setParent(parent);
return true;
} else if (current.getLeftChild() == null) {
if (current == root) {
root = current.getRightChild();
} else if (isLeftChild) {
parent.setLeftChild(current.getRightChild());
} else {
parent.setRightChild(current.getRightChild());
}
current.getRightChild().setParent(parent);
return true;
} else {
ThreadedNode successor = getSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.setLeftChild(successor);
} else {
parent.setRightChild(successor);
}
successor.setLeftChild(current.getLeftChild());
current.getLeftChild().setParent(successor);
return true;
}
}
private ThreadedNode getSuccessor(ThreadedNode delNode) {
ThreadedNode successorParent = delNode;
ThreadedNode successor = delNode.getRightChild();
while (successor.getLeftChild() != null) {
successorParent = successor;
successor = successor.getLeftChild();
}
if (successor != delNode.getRightChild()) {
successorParent.setLeftChild(successor.getRightChild());
successor.setRightChild(delNode.getRightChild());
}
successor.setLeftChild(delNode.getLeftChild());
return successor;
}
public static void main(String[] args) {
ThreadedBinaryTree tree = new ThreadedBinaryTree();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
tree.inThreaded(tree.getRoot());
tree.inOrder(); // 输出: 20 30 40 50 60 70 80
tree.postOrder(); // 输出: 20 40 30 60 80 70 50
tree.delete(20);
tree.delete(30);
tree.delete(50);
tree.inOrder(); // 输出: 40 60 70 80
}
}
```
以上就是完整的代码实现,包括线索化构造中序线索二叉树、调用求结点的前驱结点算法、按中根次序遍历一颗中序线索二叉树、按后根次序遍历中序线索二叉树、插入、删除操作,以及实例化该类的代码。