java代码实现在一颗中序线索二叉树中,实现以下操作。 ① 调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③ 在构造二叉树时进行线索化。 ④ 插入、删除操作。
时间: 2024-03-17 15:46:49 浏览: 79
以下是对应的 Java 代码实现:
```java
public class ThreadedBinaryTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
boolean leftThreaded;
boolean rightThreaded;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
this.leftThreaded = false;
this.rightThreaded = false;
}
}
private TreeNode root;
public ThreadedBinaryTree() {
this.root = null;
}
public void constructTree(int[] inorder) {
if (inorder.length == 0) {
return;
}
root = constructTreeHelper(inorder, 0, inorder.length - 1);
}
private TreeNode constructTreeHelper(int[] inorder, int start, int end) {
if (start > end) {
return null;
}
int mid = (start + end) / 2;
TreeNode node = new TreeNode(inorder[mid]);
if (start != mid) {
node.left = constructTreeHelper(inorder, start, mid - 1);
} else {
node.leftThreaded = true;
}
if (end != mid) {
node.right = constructTreeHelper(inorder, mid + 1, end);
} else {
node.rightThreaded = true;
}
return node;
}
public void inOrderTraversal() {
TreeNode cur = root;
while (cur != null) {
while (!cur.leftThreaded) {
cur = cur.left;
}
System.out.print(cur.val + " ");
while (cur.rightThreaded) {
cur = cur.right;
System.out.print(cur.val + " ");
}
cur = cur.right;
}
System.out.println();
}
public void postOrderTraversal() {
TreeNode cur = root;
while (!cur.leftThreaded || !cur.rightThreaded) {
if (!cur.rightThreaded) {
cur = cur.right;
while (!cur.leftThreaded || !cur.rightThreaded) {
if (!cur.leftThreaded) {
cur = cur.left;
} else {
cur = cur.right;
}
}
} else {
cur = cur.left;
}
}
System.out.print(cur.val + " ");
while (cur != root) {
if (cur == cur.parent.left) {
cur = cur.parent;
if (!cur.rightThreaded) {
cur = cur.right;
while (!cur.leftThreaded || !cur.rightThreaded) {
if (!cur.leftThreaded) {
cur = cur.left;
} else {
cur = cur.right;
}
}
}
} else {
cur = cur.parent;
}
System.out.print(cur.val + " ");
}
System.out.println();
}
public void insert(int val) {
if (root == null) {
root = new TreeNode(val);
return;
}
TreeNode cur = root;
while (true) {
if (val < cur.val) {
if (cur.leftThreaded) {
TreeNode newNode = new TreeNode(val);
newNode.left = cur.left;
newNode.right = cur;
newNode.leftThreaded = true;
newNode.rightThreaded = true;
cur.leftThreaded = false;
cur.left = newNode;
return;
}
cur = cur.left;
} else {
if (cur.rightThreaded) {
TreeNode newNode = new TreeNode(val);
newNode.left = cur;
newNode.right = cur.right;
newNode.leftThreaded = true;
newNode.rightThreaded = true;
cur.rightThreaded = false;
cur.right = newNode;
return;
}
cur = cur.right;
}
}
}
public void delete(int val) {
if (root == null) {
return;
}
TreeNode cur = root;
boolean isLeftChild = false;
while (cur != null && cur.val != val) {
if (val < cur.val) {
if (cur.leftThreaded) {
return;
}
cur = cur.left;
isLeftChild = true;
} else {
if (cur.rightThreaded) {
return;
}
cur = cur.right;
isLeftChild = false;
}
}
if (cur == null) {
return;
}
if (cur.leftThreaded && cur.rightThreaded) {
if (isLeftChild) {
cur.parent.left = cur.left;
cur.parent.leftThreaded = true;
deleteHelper(cur.right);
} else {
cur.parent.right = cur.right;
cur.parent.rightThreaded = true;
deleteHelper(cur.left);
}
} else if (cur.leftThreaded) {
if (isLeftChild) {
cur.parent.left = cur.left;
TreeNode predecessor = findPredecessor(cur);
predecessor.right = cur.right;
deleteHelper(cur.right);
} else {
cur.parent.right = cur.left;
TreeNode predecessor = findPredecessor(cur);
predecessor.right = cur.right;
deleteHelper(cur.right);
}
} else if (cur.rightThreaded) {
if (isLeftChild) {
cur.parent.left = cur.right;
TreeNode successor = findSuccessor(cur);
successor.left = cur.left;
deleteHelper(cur.left);
} else {
cur.parent.right = cur.right;
TreeNode successor = findSuccessor(cur);
successor.left = cur.left;
deleteHelper(cur.left);
}
} else {
TreeNode predecessor = findPredecessor(cur);
cur.val = predecessor.val;
if (predecessor.leftThreaded && predecessor.rightThreaded) {
predecessor.parent.left = predecessor.left;
predecessor.parent.leftThreaded = true;
deleteHelper(predecessor.right);
} else {
predecessor.parent.right = predecessor.left;
TreeNode predecessorPredecessor = findPredecessor(predecessor);
predecessorPredecessor.right = predecessor.right;
deleteHelper(predecessor.right);
}
}
}
private void deleteHelper(TreeNode cur) {
if (cur.leftThreaded && cur.rightThreaded) {
deleteHelper(cur.right);
} else if (cur.leftThreaded) {
TreeNode predecessor = findPredecessor(cur);
predecessor.right = cur.right;
if (cur.right != null) {
cur.right.parent = predecessor;
}
deleteHelper(cur.right);
} else if (cur.rightThreaded) {
TreeNode successor = findSuccessor(cur);
successor.left = cur.left;
if (cur.left != null) {
cur.left.parent = successor;
}
deleteHelper(cur.left);
} else {
TreeNode predecessor = findPredecessor(cur);
cur.val = predecessor.val;
if (predecessor.leftThreaded && predecessor.rightThreaded) {
predecessor.parent.left = predecessor.left;
predecessor.parent.leftThreaded = true;
deleteHelper(predecessor.right);
} else {
predecessor.parent.right = predecessor.left;
TreeNode predecessorPredecessor = findPredecessor(predecessor);
predecessorPredecessor.right = predecessor.right;
deleteHelper(predecessor.right);
}
}
}
private TreeNode findPredecessor(TreeNode node) {
if (node.leftThreaded) {
return node.left;
}
TreeNode cur = node.left;
while (!cur.rightThreaded) {
cur = cur.right;
}
return cur;
}
private TreeNode findSuccessor(TreeNode node) {
if (node.rightThreaded) {
return node.right;
}
TreeNode cur = node.right;
while (!cur.leftThreaded) {
cur = cur.left;
}
return cur;
}
}
```
其中,`constructTree` 方法用于构造线索二叉树,`inOrderTraversal` 方法用于按中根次序遍历线索二叉树,`postOrderTraversal` 方法用于按后根次序遍历线索二叉树,`insert` 方法用于插入一个结点,`delete` 方法用于删除一个结点,`findPredecessor` 方法用于查找前驱结点,`findSuccessor` 方法用于查找后继结点。具体实现细节可以参考代码注释。
阅读全文