package utitled;
// 引線二元樹形式進行前序, 中序, 後續遍歷
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
Node root = new Node(1);
Node no3 = new Node(3);
Node no6 = new Node(6);
Node no8 = new Node(8);
Node no10 = new Node(10);
Node no14 = new Node(14);
root.setLeft(no3);
root.setRight(no6);
no3.setLeft(no8);
no3.setRight(no10);
no6.setLeft(no14);
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
String orderType = "postOrder";
threadedBinaryTree.threadedNodes(orderType);
System.out.printf("no10 left is no%d, right is no%d\n", no10.getLeft().getId(), no10.getRight().getId());
threadedBinaryTree.threadedNodesLoop(orderType);
}
}
// 引線二元樹
class ThreadedBinaryTree {
private Node root;
/*
在設置後繼結點時，需要pre結點(前一個結點)
*/
private Node pre;
public void setRoot(Node root) {
this.root = root;
}
public boolean isNotNull(Node node) {
return node != null;
}
/**
* 根結點不為空才能開始進行引線化
* 若當前結點與另一結點已存在link的關係引線化會跳過
*/
public void threadedNodes(String orderType) {
if (isNotNull(root)) {
switch (orderType) {
case "preOrder":
preOrderThreadedNodes(root);
break;
case "inOrder":
inOrderThreadedNodes(root);
break;
case "postOrder":
postOrderThreadedNodes(root);
break;
default:
break;
}
}
}
public void threadedNodesLoop(String orderType) {
if (isNotNull(root)) {
switch (orderType) {
case "preOrder":
preOrderThreadedNodesLoop();
break;
case "inOrder":
inOrderThreadedNodesLoop();
break;
case "postOrder":
postOrderThreadedNodesLoop();
break;
default:
break;
}
}
}
public void inOrderThreadedNodesLoop() {
Node current = root;
while(current != null) {
// 先找到第一個left_relative = false的結點
while(!current.isLeft_relative()) {
current = current.getLeft();
}
// 輸出當前結點
System.out.println("current = " + current.getId());
while (current.isRight_relative()) {
current = current.getRight();
System.out.println("current = " + current.getId());
}
current = current.getRight();
// 左子樹最後一個葉子結點不要先輸出
}
}
public void preOrderThreadedNodesLoop() {
Node current = root;
while(current != null) {
while (!current.isLeft_relative()) {
System.out.println("current = " + current.getId());
current = current.getLeft();
}
while (current.isRight_relative() && current.isLeft_relative()) {
System.out.println("current = " + current.getId());
current = current.getRight();
}
while (current != null && !current.isRight_relative()) {
System.out.println("current = " + current.getId());
current = current.getRight();
}
}
}
/**
* 從root開始設置引線 (thread)
* 中序遍歷
* @param current 當前結點
*/
public void inOrderThreadedNodes(Node current) {
if (current == null) {
return;
}
// 先向左中序遍歷
if (!current.isLeft_relative()) {
inOrderThreadedNodes(current.getLeft());
}
// 輸出當前結點，並安插引線(目前結點之左子樹為空或右子樹為空)
if (current.getLeft() == null) {
current.setLeft(pre);
// 設置前驅結點
current.setLeft_relative(true);
}
// 若想為結點設置後繼，就需先走回上層結點
if (pre != null && pre.getRight() == null) {
pre.setRight(current);
// 設置後繼結點
pre.setRight_relative(true);
}
// 上面兩個if-clause走完代表完成該結點設置thread
// 就把該結點設為上一個結點了~
pre = current;
// 向右中序遍歷
if (!current.isRight_relative()) {
inOrderThreadedNodes(current.getRight());
}
}
public void preOrderThreadedNodes(Node current) {
if (current == null) {
return;
}
// 先將當前結點空指針的部分設置thread
if (current.getLeft() == null) {
current.setLeft(pre);
current.setLeft_relative(true);
}
if (pre != null && pre.getRight() == null) {
pre.setRight(current);
pre.setRight_relative(true);
}
// 當前結點設置thread完成後記得將當前結點複製一份到pre
pre = current;
// 向左前序遍歷
if (!current.isLeft_relative()) {
// 代表當前結點已經有左子樹了(link)
preOrderThreadedNodes(current.getLeft());
}
// 向右前序遍歷
if (!current.isRight_relative()) {
preOrderThreadedNodes(current.getRight());
}
}
public void postOrderThreadedNodesLoop() {
Node current = root;
while (current != null) {
while (!current.isLeft_relative()) {
current = current.getLeft();
}
while (current.isRight_relative()) {
System.out.println("current = " + current.getId());
current = current.getRight();
}
System.out.println("current = " + current.getId());
if (current == root) {
return;
}
current = root;
while (!current.isRight_relative()) {
current = current.getRight();
}
}
}
public void postOrderThreadedNodes(Node current) {
if (current == null) {
return;
}
// 向左後序遍歷
if (!current.isLeft_relative()) {
postOrderThreadedNodes(current.getLeft());
}
// 向右後序遍歷
if (!current.isRight_relative()) {
postOrderThreadedNodes(current.getRight());
}
// 將當前結點空指針部分設置thread(引線化)
if (current.getLeft() == null) {
current.setLeft(pre);
current.setLeft_relative(true);
}
if (pre != null && pre.getRight() == null) {
pre.setRight(current);
pre.setRight_relative(true);
}
// 當前結點設置thread完成後記得將當前結點複製一份到pre
pre = current;
}
}
class Node {
private int id;
private Node left;
private Node right;
private boolean left_relative = false;
private boolean right_relative = false;
/*
left_relative, right_relative = false(預設) 代表node之間原先就有link連接，分別指向左右子結點
left_relative, right_relative = true 代表node之間以thread連接，分別指向前驅(predecessor)與後繼(successor)結點
*/
public Node(int id) {
this.id = id;
}
public int getId() {
return id;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public boolean isLeft_relative() {
return left_relative;
}
public void setLeft_relative(boolean left_relative) {
this.left_relative = left_relative;
}
public boolean isRight_relative() {
return right_relative;
}
public void setRight_relative(boolean right_relative) {
this.right_relative = right_relative;
}
}
如有敘述錯誤，還請不吝嗇留言指教，thanks!
