Java代码实现在一颗中序线索二叉树中,实现以下操作。 ① 调用求结点的前驱结点算法,按中根次序遍历一颗中序线索二叉树 。 ② 按后根次序遍历中序线索二叉树。 ③ 在构造二叉树时进行线索化。 ④ 插入、删除操作。
时间: 2024-03-18 19:38:42 浏览: 66
以下是Java代码实现:
```
class ThreadedBinaryTreeNode {
int val;
ThreadedBinaryTreeNode left;
ThreadedBinaryTreeNode right;
boolean isLeftThread;
boolean isRightThread;
public ThreadedBinaryTreeNode(int val) {
this.val = val;
this.isLeftThread = false;
this.isRightThread = false;
}
}
public class ThreadedBinaryTree {
ThreadedBinaryTreeNode root;
public ThreadedBinaryTree() {
this.root = null;
}
public ThreadedBinaryTreeNode getPredecessor(ThreadedBinaryTreeNode node) {
if (node.isLeftThread) {
return node.left;
} else {
ThreadedBinaryTreeNode temp = node.left;
while (!temp.isRightThread) {
temp = temp.right;
}
return temp;
}
}
public void inOrderTraversal() {
ThreadedBinaryTreeNode temp = root;
while (temp != null && !temp.isLeftThread) {
temp = temp.left;
}
while (temp != null) {
System.out.print(temp.val + " ");
temp = getSuccessor(temp);
}
}
public void postOrderTraversal() {
ThreadedBinaryTreeNode temp = root;
while (!temp.isLeftThread || !temp.isRightThread) {
while (!temp.isRightThread) {
temp = temp.right;
}
while (temp.isLeftThread && temp.left != null) {
temp = temp.left;
}
}
while (temp != null) {
System.out.print(temp.val + " ");
temp = getPredecessor(temp);
}
}
public void insert(int val) {
ThreadedBinaryTreeNode node = new ThreadedBinaryTreeNode(val);
if (root == null) {
root = node;
return;
}
ThreadedBinaryTreeNode temp = root;
while (true) {
if (val < temp.val) {
if (temp.isLeftThread) {
node.left = temp.left;
node.right = temp;
temp.left = node;
temp.isLeftThread = false;
return;
} else {
temp = temp.left;
}
} else {
if (temp.isRightThread) {
node.right = temp.right;
node.left = temp;
temp.right = node;
temp.isRightThread = false;
return;
} else {
temp = temp.right;
}
}
}
}
public void delete(int val) {
ThreadedBinaryTreeNode temp = root;
ThreadedBinaryTreeNode parent = null;
boolean isLeftChild = false;
while (temp != null && temp.val != val) {
parent = temp;
if (val < temp.val) {
if (!temp.isLeftThread) {
temp = temp.left;
isLeftChild = true;
} else {
return;
}
} else {
if (!temp.isRightThread) {
temp = temp.right;
isLeftChild = false;
} else {
return;
}
}
}
if (temp.left == null && temp.right == null) {
if (temp == root) {
root = null;
} else if (isLeftChild) {
parent.left = temp.left;
parent.isLeftThread = true;
if (temp.isRightThread) {
parent.right = temp.right;
ThreadedBinaryTreeNode predecessor = getPredecessor(temp.right);
predecessor.left = parent;
parent.right = predecessor;
}
} else {
parent.right = temp.right;
parent.isRightThread = true;
if (temp.isLeftThread) {
parent.left = temp.left;
ThreadedBinaryTreeNode successor = getSuccessor(temp.left);
successor.right = parent;
parent.left = successor;
}
}
} else if (temp.left == null) {
if (temp == root) {
root = temp.right;
} else if (isLeftChild) {
parent.left = temp.right;
ThreadedBinaryTreeNode predecessor = getPredecessor(temp.right);
predecessor.left = parent;
parent.right = predecessor;
} else {
parent.right = temp.right;
ThreadedBinaryTreeNode successor = getSuccessor(temp.right);
successor.right = parent;
parent.left = successor;
}
} else if (temp.right == null) {
if (temp == root) {
root = temp.left;
} else if (isLeftChild) {
parent.left = temp.left;
ThreadedBinaryTreeNode successor = getSuccessor(temp.left);
successor.right = parent;
parent.left = successor;
} else {
parent.right = temp.left;
ThreadedBinaryTreeNode predecessor = getPredecessor(temp.left);
predecessor.left = parent;
parent.right = predecessor;
}
} else {
ThreadedBinaryTreeNode successor = getSuccessor(temp);
delete(successor.val);
temp.val = successor.val;
}
}
private ThreadedBinaryTreeNode getSuccessor(ThreadedBinaryTreeNode node) {
if (node.isRightThread) {
return node.right;
} else {
ThreadedBinaryTreeNode temp = node.right;
while (!temp.isLeftThread) {
temp = temp.left;
}
return temp;
}
}
public void inOrderThread() {
ThreadedBinaryTreeNode pre = null;
inOrderThread(root, pre);
}
private void inOrderThread(ThreadedBinaryTreeNode node, ThreadedBinaryTreeNode pre) {
if (node == null) {
return;
}
inOrderThread(node.left, pre);
if (node.left == null) {
node.left = pre;
node.isLeftThread = true;
}
if (pre != null && pre.right == null) {
pre.right = node;
pre.isRightThread = true;
}
pre = node;
inOrderThread(node.right, pre);
}
}
```
其中,`ThreadedBinaryTreeNode` 是线索二叉树的结点类,包含结点值、左右子树指针以及左右线索标记。`ThreadedBinaryTree` 是线索二叉树类,包含根结点指针以及实现插入、删除、中序线索化、求前驱结点和求后继结点等操作的方法。具体实现细节可以参考代码注释。
阅读全文