Java代码实现在一颗中序线索二叉树中,实现以下操作。 ① 调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③ 在构造二叉树时进行线索化。 ④ 插入、删除操作。
时间: 2024-03-16 16:48:03 浏览: 24
以下是Java代码实现:
```java
class ThreadedBinaryTreeNode {
int data;
ThreadedBinaryTreeNode left, right;
boolean isLeftThreaded, isRightThreaded;
public ThreadedBinaryTreeNode(int data) {
this.data = data;
this.left = this.right = null;
this.isLeftThreaded = this.isRightThreaded = false;
}
}
class ThreadedBinaryTree {
ThreadedBinaryTreeNode root;
public ThreadedBinaryTree() {
this.root = null;
}
// 中序遍历
public void inOrderTraversal() {
ThreadedBinaryTreeNode current = this.root;
while (current != null) {
while (!current.isLeftThreaded) {
current = current.left;
}
System.out.print(current.data + " ");
while (current.isRightThreaded && current.right != null) {
current = current.right;
System.out.print(current.data + " ");
}
current = current.right;
}
System.out.println();
}
// 后序遍历
public void postOrderTraversal() {
ThreadedBinaryTreeNode current = this.root;
while (current != null && !current.isLeftThreaded) {
current = current.left;
}
ThreadedBinaryTreeNode lastVisited = null;
while (current != null) {
if (current.isRightThreaded || current.right == lastVisited) {
System.out.print(current.data + " ");
lastVisited = current;
current = current.left;
} else {
current = current.right;
while (current != null && !current.isLeftThreaded) {
current = current.left;
}
}
}
System.out.println();
}
// 线索化
public void thread() {
ThreadedBinaryTreeNode prev = null;
this.thread(this.root, prev);
}
private void thread(ThreadedBinaryTreeNode node, ThreadedBinaryTreeNode prev) {
if (node == null) {
return;
}
this.thread(node.left, prev);
if (node.left == null) {
node.left = prev;
node.isLeftThreaded = true;
}
if (prev != null && prev.right == null) {
prev.right = node;
prev.isRightThreaded = true;
}
prev = node;
this.thread(node.right, prev);
}
// 插入操作
public void insert(int data) {
ThreadedBinaryTreeNode node = new ThreadedBinaryTreeNode(data);
if (this.root == null) {
this.root = node;
return;
}
ThreadedBinaryTreeNode current = this.root;
ThreadedBinaryTreeNode parent = null;
while (current != null) {
parent = current;
if (data < current.data) {
if (!current.isLeftThreaded) {
current = current.left;
} else {
break;
}
} else {
if (!current.isRightThreaded) {
current = current.right;
} else {
break;
}
}
}
if (data < parent.data) {
node.left = parent.left;
node.right = parent;
parent.left = node;
parent.isLeftThreaded = false;
} else {
node.left = parent;
node.right = parent.right;
parent.right = node;
parent.isRightThreaded = false;
}
node.isLeftThreaded = true;
node.isRightThreaded = true;
}
// 删除操作
public void delete(int data) {
if (this.root == null) {
return;
}
ThreadedBinaryTreeNode current = this.root;
ThreadedBinaryTreeNode parent = null;
while (current != null && current.data != data) {
parent = current;
if (data < current.data) {
if (!current.isLeftThreaded) {
current = current.left;
} else {
return;
}
} else {
if (!current.isRightThreaded) {
current = current.right;
} else {
return;
}
}
}
if (current.isLeftThreaded && current.isRightThreaded) {
if (parent == null) {
this.root = null;
} else if (current == parent.left) {
parent.left = current.left;
parent.isLeftThreaded = true;
this.fixThread(parent, current.left);
} else {
parent.right = current.right;
parent.isRightThreaded = true;
this.fixThread(parent, current.right);
}
} else if (current.isLeftThreaded) {
ThreadedBinaryTreeNode predecessor = this.getPredecessor(current);
if (parent == null) {
this.root = current.left;
} else if (current == parent.left) {
parent.left = current.left;
this.fixThread(parent, predecessor);
} else {
parent.right = current.left;
this.fixThread(parent, predecessor);
}
} else if (current.isRightThreaded) {
ThreadedBinaryTreeNode successor = this.getSuccessor(current);
if (parent == null) {
this.root = current.right;
} else if (current == parent.left) {
parent.left = current.right;
this.fixThread(parent, successor);
} else {
parent.right = current.right;
this.fixThread(parent, successor);
}
} else {
ThreadedBinaryTreeNode predecessor = this.getPredecessor(current);
ThreadedBinaryTreeNode temp = predecessor.right;
current.data = predecessor.data;
predecessor.data = temp.data;
this.delete(temp.data);
}
}
private ThreadedBinaryTreeNode getPredecessor(ThreadedBinaryTreeNode node) {
if (node.isLeftThreaded) {
return node.left;
}
ThreadedBinaryTreeNode current = node.left;
while (!current.isRightThreaded) {
current = current.right;
}
return current;
}
private ThreadedBinaryTreeNode getSuccessor(ThreadedBinaryTreeNode node) {
if (node.isRightThreaded) {
return node.right;
}
ThreadedBinaryTreeNode current = node.right;
while (!current.isLeftThreaded) {
current = current.left;
}
return current;
}
private void fixThread(ThreadedBinaryTreeNode parent, ThreadedBinaryTreeNode node) {
if (node == null) {
return;
}
ThreadedBinaryTreeNode temp = node.left;
while (temp != parent && !temp.isRightThreaded) {
temp = temp.right;
}
if (temp == parent) {
return;
}
temp.right = parent;
}
}
```
注:以上代码实现了线索二叉树的构造、中序遍历、后序遍历、插入和删除等操作。其中,插入操作实现了在线索二叉树上插入一个新节点,并保持线索二叉树的性质不变;删除操作实现了删除一个指定的节点,并保持线索二叉树的性质不变。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)