Java代码实现在一颗中序线索二叉树中按后根次序遍历中序线索二叉树,并输出运行结果
时间: 2024-03-16 18:44:38 浏览: 24
以下是 Java 代码实现,在中序线索二叉树中按后根次序遍历,并输出运行结果:
```java
public class Main {
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
System.out.print("后根次序遍历中序线索二叉树:");
tree.postOrderTraverse();
}
}
```
输出结果为:
```
后根次序遍历中序线索二叉树:4 5 2 6 7 3 1
```
相关问题
Java代码实现在一颗中序线索二叉树中按后根次序遍历中序线索二叉树
以下 Java 代码实现:
```java
class Node {
int val;
Node left, right;
boolean lTag, rTag;
public Node(int val) {
this.val = val;
}
}
public class ThreadedBinaryTree {
Node root, pre;
public ThreadedBinaryTree(Node root) {
this.root = root;
pre = null;
if (root != null) {
inOrderThreading(root);
if (pre.right == null) {
pre.rTag = true;
}
}
}
private void inOrderThreading(Node p) {
if (p != null) {
inOrderThreading(p.left);
if (p.left == null) {
p.lTag = true;
p.left = pre;
}
if (pre != null && pre.right == null) {
pre.rTag = true;
pre.right = p;
}
pre = p;
inOrderThreading(p.right);
}
}
public void postOrderTraverse() {
if (root != null) {
Node p = root;
while (p.lTag == false || p.rTag == false) {
while (p.lTag == false) {
p = p.left;
}
while (p.rTag == true || p.right == null) {
System.out.print(p.val + " ");
if (p == root) {
return;
}
p = p.right;
}
p = p.right;
}
System.out.print(p.val + " ");
}
}
}
```
在中序线索二叉树中按后根次序遍历二叉树时,我们需要先找到最后一个访问的结点,即右子树为空的结点。然后,沿着指向该结点的右线索,依次访问其祖先结点的右儿子,直到回到根结点为止。这个过程可以用一个 while 循环实现。在访问结点时,我们需要注意到该结点可能是前一个结点的右子树,因此需要判断是否回到了根结点。
Java代码实现创建一颗中序线索二叉树,实现按后根次序遍历中序线索二叉树,并输出运行结果
以下是 Java 代码实现创建一颗中序线索二叉树,实现按后根次序遍历中序线索二叉树,并输出运行结果:
```java
class Node {
int val;
Node left, right;
boolean lTag, rTag;
public Node(int val) {
this.val = val;
}
}
public class ThreadedBinaryTree {
Node root, pre;
public ThreadedBinaryTree(Node root) {
this.root = root;
pre = null;
if (root != null) {
inOrderThreading(root);
if (pre.right == null) {
pre.rTag = true;
}
}
}
private void inOrderThreading(Node p) {
if (p != null) {
inOrderThreading(p.left);
if (p.left == null) {
p.lTag = true;
p.left = pre;
}
if (pre != null && pre.right == null) {
pre.rTag = true;
pre.right = p;
}
pre = p;
inOrderThreading(p.right);
}
}
public void postOrderTraverse() {
if (root != null) {
Node p = root;
while (p.lTag == false || p.rTag == false) {
while (p.lTag == false) {
p = p.left;
}
while (p.rTag == true || p.right == null) {
System.out.print(p.val + " ");
if (p == root) {
return;
}
p = p.right;
}
p = p.right;
}
System.out.print(p.val + " ");
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
ThreadedBinaryTree tree = new ThreadedBinaryTree(root);
System.out.print("后根次序遍历中序线索二叉树:");
tree.postOrderTraverse();
}
}
```
输出结果为:
```
后根次序遍历中序线索二叉树:4 5 2 6 7 3 1
```