# 检索二叉树中序遍历算法详解

XAMPP案例 764浏览
``````package tree;

/*
* 線索二叉樹
*/
private E[] elements = null;
private int count = 0;
private Node pre;//中序遍歷最後一個結點或中序遍歷前一個結點變數
private Node lastLeft;//中序遍歷第一個結點

/*前序遞迴生成二叉樹*/
public Node createBinaryTree(){
Node node = new Node();

if(count >= elements.length || elements[count++] == "#"){
return null;
}else{
node.element = elements[count - 1];
node.left = createBinaryTree();
node.right = createBinaryTree();
}

return node;
}

//中序遍歷生成線索二叉樹
if(current != null){
if(current.left == null){ //當前結點沒有左孩子
current.lefeTag = 1;
current.left = pre;
}

if(pre.right == null){ //前驅沒有右孩子
pre.rightTag = 1;
pre.right = current;
}

pre = current;//指向前一個結點
}
return null;
}

/*帶頭結點的線索二叉樹*/
}

if(root == null){
return;
}else{
//使二叉樹中序序列中的第一個結點的left和最後一個結點的right指向頭結點
//找到第一個結點
findLastLeftNode(root);
lastLeft.lefeTag = 1;

pre.rightTag = 1;

}
}

/*線索二叉樹的遍歷*/
while(current.lefeTag == 0){
current = current.left;
}
System.out.println(current.element);

while(current.rightTag == 1 && current.right != head){
current = current.right;
System.out.println(current.element);
}

current = current.right;
}
}

/*找到最左邊的結點，即中序遍歷的第一個結點*/
public void findLastLeftNode(Node root){
if(root == null){
return;
}

Node current = root;
while(current.left != null){
current = current.left;
}

lastLeft = current;
}

static class Node<E>{
int lefeTag; /*如果Tag為0則標識指向左右孩子的指標，如果為1則標識指向前驅或後繼的線索*/
int rightTag;
Node<E> left;
Node<E> right;
E element;

public Node(){
}

public Node(E element){
this.element = element;
}
}
}
``````