6.16后序线索二叉树-526互联

import java.util.Scanner;

public class Main {
public static int i = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
Trees root = AddTrees(str);//创建前序二叉树
root.zhongxv(root);//中序遍历
System.out.println();
midCodeTree m = new midCodeTree(root);
m.creatMidCodeTree(root);//中序线索链表
m.Inorder(root);//中序线索链表遍历
}

public static Trees AddTrees(String a) {
Trees T = null;
if (i < a.length()) {
if (a.charAt(i) != '#') {
T = new Trees(a.charAt(i));
i++;
T.left = AddTrees(a);
T.right = AddTrees(a);
} else {
i++;
}
}
return T;
}
}

class midCodeTree {
private Trees root;
private Trees pre = null;

public midCodeTree(Trees root) {
this.root = root;
}

public void creatMidCodeTree(Trees t) {//中序线索化
if (t == null) {
return;
}

creatMidCodeTree(t.left);

if (t.left == null) {
t.l = 1;
t.left = pre;
}

if (pre != null && pre.right == null) {
pre.r = 1;
pre.right = t;
}

pre = t;

creatMidCodeTree(t.right);
}

public Trees next(Trees p) {//找后继节点
Trees q = null;
if (p == null)
return null;
if (p.r == 1) {
q = p.right;
} else {
q = p.right;
while (q.l == 0) {
q = q.left;
}
}
return q;
}

public void Inorder(Trees root) {
if (root == null)
return;
Trees p = root;
while (p.l == 0) {
p = p.left;
}
System.out.println(p.data);
while (p.right != null) {
p = next(p);
System.out.println(p.data);
}
}
}

class Trees {
public char data;
public Trees left;
public Trees right;
public int l;
public int r;

public Trees(char t) {
this.data = t;
this.left = null;
this.right = null;
l = 0;
r = 0;
}

public void zhongxv(Trees t) {
if (t != null) {
zhongxv(t.left);
System.out.print(t.data);
zhongxv(t.right);
}
}
}

线索