/**
* 线索化二叉树的节点
*/
public class IndexNode {
public int id;
public String name;
public IndexNode left;
public IndexNode right;
public IndexNode parent = null; // 后序线索化的时候需要使用
public boolean isLeftIndexed; // 0 表示 left 指针指向左子树，1 表示 left 指针指向前驱节点
public boolean isRightIndexed; // 0 表示 right 指针指向右子树，1 表示 right 指针指向后继节点
public IndexNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {return "[" + id + "," + name + "]";
}
// 前序遍历
public void preOrder() {System.out.println(this);
if (left != null) left.preOrder();
if (right != null) right.preOrder();}
// 中序遍历
public void infixOrder() {if (left != null) left.infixOrder();
System.out.println(this);
if (right != null) right.infixOrder();}
// 后序遍历
public void postOrder() {if (left != null) left.postOrder();
if (right != null) right.postOrder();
System.out.println(this);
}
}
/**
* 实现线索化功能的二叉树
*/
public class IndexBinaryTree {
IndexNode root;
// 为了实现线索化，需要一个 pre 指针，指向当前节点的前驱
// 进行线索化的时候，pre 总是指向前一个节点
IndexNode pre = null;
/** 前序遍历 */
public void preOrder() {if (root == null) {System.out.println("空树，无法遍历");
return;
}
root.preOrder();}
/** 中序遍历 */
public void infixOrder() {if (root == null) {System.out.println("空树，无法遍历");
return;
}
root.infixOrder();}
/** 后序遍历 */
public void postOrder() {if (root == null) {System.out.println("空树，无法遍历");
return;
}
root.postOrder();}
/** 对二叉树进行中序线索化 */
public void infixOrderIndexTree() {if (root == null) return;
infixOrderIndexTree(root);
}
/** 对二叉树进行前序线索化 */
public void preOrderIndexTree() {if (root == null) return;
preOrderIndexTree(root);
}
/** 对二叉树进行后序线索化 */
public void postOrderIndexTree() {if (root == null) return;
postOrderIndexTree(root);
}
/** 遍历经过中序线索化后的二叉树 */
public void showInfixOrderIndexedTree() {
IndexNode cur = root;
while (cur != null) {
// cur 一直循环向下找，找到 leftType = 1 的节点
while (!cur.isLeftIndexed) cur = cur.left;
// 打印 cur
System.out.println(cur);
// 若 cur 的右指针指向的是后继节点，就一直更新，然后输出
while (cur.isRightIndexed) {
cur = cur.right;
System.out.println(cur);
}
// 更新 cur 节点
cur = cur.right;
}
}
/** 遍历经过前序线索化后的二叉树 */
public void showPreOrderIndexedTree() {
IndexNode cur = root;
while (cur != null) {while (cur.left != null && !cur.isLeftIndexed) {System.out.println(cur);
cur = cur.left;
}
System.out.println(cur);
if (cur.isLeftIndexed) cur = cur.right;
while (cur != null && cur.isRightIndexed) {System.out.println(cur);
cur = cur.right;
}
}
}
/** 遍历经过后序线索化后的二叉树 */
public void showPostOrderIndexedTree() {
IndexNode cur = root;
while (cur != null) {while (!cur.isLeftIndexed) cur = cur.left;
while (cur != null && cur.isRightIndexed) {System.out.println(cur);
pre = cur;
cur = cur.right;
}
if (cur == root) {System.out.println(cur);
return;
}
while (cur != null && cur.right == pre) {System.out.println(cur);
pre = cur;
cur = cur.parent;
}
if (cur != null && !cur.isRightIndexed) {cur = cur.right;}
}
}
// 中序线索化的过程，node 是当前需要线索化的节点
private void infixOrderIndexTree(IndexNode node) {
// 1. 递归向左线索化
if (node.left != null && !node.isLeftIndexed) infixOrderIndexTree(node.left);
// 2. 对当前节点进行线索化
indexCurrentNode(node);
// 3. 递归向右线索化
if (node.right != null && !node.isRightIndexed) infixOrderIndexTree(node.right);
}
// 前序线索化的过程
private void preOrderIndexTree(IndexNode node) {
// 1. 对当前节点进行线索化
indexCurrentNode(node);
// 2. 递归向左线索化
if (node.left != null && !node.isLeftIndexed) preOrderIndexTree(node.left);
// 3. 递归向右线索化
if (node.right != null && !node.isRightIndexed) preOrderIndexTree(node.right);
}
// 后序线索化的过程
private void postOrderIndexTree(IndexNode node) {
// 1. 递归向左线索化
if (node.left != null && !node.isLeftIndexed) postOrderIndexTree(node.left);
// 2. 递归向右线索化
if (node.right != null && !node.isRightIndexed) postOrderIndexTree(node.right);
// 3. 对当前节点线索化
indexCurrentNode(node);
}
// 对当前节点进行线索化
private void indexCurrentNode(IndexNode current) {if (current.left == null) {
// 让当前节点的左指针指向前驱（左指针为空，才可以进行，不空则说明已经指向左子树）current.left = pre;
current.isLeftIndexed = true; // type 置为 1, 标记为指向的是前驱节点
}
if (pre != null && pre.right == null) {// 让前驱的右指针，指向当前节点(前驱的右指针为空，才可进行，不空则说明已经指向右子树)
pre.right = current;
pre.isRightIndexed = true; // type 置为 1, 标记为指向的是后继节点
}
// 处理完成后，要更新 pre 为 当前节点，（让当前节点称为下一个节点的前驱）pre = current;
}
}
/**
* 测试
* 1. 二叉树的中序遍历，先序遍历，后序遍历
* 2. 二叉树的中序索引化，先序索引化，后序索引化
* 3. 二叉树的中序索引化遍历，先序索引化遍历，后序索引化遍历
*/
public class IndexBinaryTreeDemo {
private static IndexBinaryTree tree;
private static IndexNode node5;
public static void main(String[] args) {testInfix();
System.out.println("************************");
testPrefix();
System.out.println("************************");
testPost();}
private static void testPost() {IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();
app.resetTree(); // 重置测试数据
System.out.println("后序遍历结果:");
tree.postOrder(); // 打印先序遍历结果
tree.postOrderIndexTree(); // 对二叉树进行先序索引化
// 测试节点 [10, King] 的前驱和后继
System.out.println("\n[10,King]的前驱和后继:");
System.out.println("前驱:" + node5.left); // [8,Mary]
System.out.println("后继:" + node5.right);// [6,Smith]
// 测试经过中序线索华后的遍历结果
System.out.println("\n 经过后序线索化后的遍历结果:");
tree.showPostOrderIndexedTree();}
private static void testPrefix() {IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();
app.resetTree(); // 重置测试数据
System.out.println("先序遍历结果:");
tree.preOrder(); // 打印先序遍历结果
tree.preOrderIndexTree(); // 对二叉树进行先序索引化
// 测试节点 [10, King] 的前驱和后继
System.out.println("\n[10,King]的前驱和后继:");
System.out.println("前驱:" + node5.left); // [8,Mary]
System.out.println("后继:" + node5.right);// [6,Smith]
// 测试经过中序线索华后的遍历结果
System.out.println("\n 经过前序线索化后的遍历结果:");
tree.showPreOrderIndexedTree();}
private static void testInfix() {IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();
app.resetTree(); // 重置测试数据
System.out.println("中序遍历结果");
tree.infixOrder(); // 打印中序遍历结果
tree.infixOrderIndexTree(); // 对二叉树进行中序遍历索引化
// 测试节点 [10, King] 的前驱和后继
System.out.println("\n[10,King]的前驱和后继:");
System.out.println("前驱:" + node5.left); // [3, Jack]
System.out.println("后继:" + node5.right);// [1, Tom]
// 测试经过中序线索化后的遍历结果
System.out.println("\n 经过中序线索化后的遍历结果:");
tree.showInfixOrderIndexedTree();}
private void resetTree() {IndexNode root = new IndexNode(1, "Tom");
IndexNode node2 = new IndexNode(3, "Jack");
IndexNode node3 = new IndexNode(6, "Smith");
IndexNode node4 = new IndexNode(8, "Mary");
IndexNode node5 = new IndexNode(10, "King");
IndexNode node6 = new IndexNode(14, "Dim");
IndexBinaryTreeDemo.node5 = node5; // 供测试用
// 手动创建二叉树, parent 指针用来辅助后序线索化
root.left = node2; node2.parent = root;
root.right = node3; node3.parent = root;
node2.left = node4; node4.parent = node2;
node2.right = node5; node5.parent = node2;
node3.left = node6; node6.parent = node3;
tree = new IndexBinaryTree();
tree.root = root;
}
}