搜索二叉樹概念
二叉樹是樹的特殊一種，具有如下特點(diǎn)：
1、每個結(jié)點(diǎn)最多有兩顆子樹，結(jié)點(diǎn)的度最大為2左刽。
2、左子樹和右子樹是有順序的酌媒，次序不能顛倒欠痴。
3、即使某結(jié)點(diǎn)只有一個子樹秒咨，也要區(qū)分左右子樹喇辽。
遞歸遍歷
前序遍歷
基本思想：先訪問根結(jié)點(diǎn)，再先序遍歷左子樹雨席，最后再先序遍歷右子樹即根—左—右菩咨。
public static void preRecDisplay(TreeNode node){
//前序遍歷
if (node!=null){
System.out.println(node.data);
preRecDisplay(node.leftNode);
preRecDisplay(node.rightNode);
}
}
中序遍歷
基本思想：先中序遍歷左子樹，然后再訪問根結(jié)點(diǎn)陡厘，最后再中序遍歷右子樹即左—根—右旦委。
public static void midRecDisplay(TreeNode node){
//中序遍歷
if (node!=null) {
midRecDisplay(node.leftNode);
System.out.println(node.data);
midRecDisplay(node.rightNode);
}
}
后序遍歷
基本思想：先后序遍歷左子樹，然后再后序遍歷右子樹雏亚，最后再訪問根結(jié)點(diǎn)即左—右—根。
public static void postRecDisplay(TreeNode node){
//后序遍歷
if (node!=null) {
postRecDisplay(node.leftNode);
postRecDisplay(node.rightNode);
System.out.println(node.data);
}
}
public static void main(String[] args){
int datas[] = {1,2,3,4,5,6,7,8,9};
Tree tree = new Tree(datas);
postRecDisplay(tree.root);
}
非遞歸遍歷
前序遍歷
對于任一結(jié)點(diǎn)p：
a. 訪問結(jié)點(diǎn)p摩钙，并將結(jié)點(diǎn)p入棧罢低；
b. 判斷結(jié)點(diǎn)p的左孩子是否為空，若為空胖笛，則取棧頂結(jié)點(diǎn)并進(jìn)行出棧操作网持，并將棧頂結(jié)點(diǎn)的右孩子置為當(dāng)前的結(jié)點(diǎn)p，循環(huán)置a长踊；若不為空功舀，則將p的左孩子置為當(dāng)前結(jié)點(diǎn)p；
c. 直到p為空身弊，并且棧為空辟汰，則遍歷結(jié)束列敲。
public static void preDisplay(TreeNode node){
//前序遍歷
Stack<TreeNode> stack = new Stack<>();
while (true){
while (node!=null){
//輸出就是遍歷的過程，前序遍歷先輸出當(dāng)前節(jié)點(diǎn)
System.out.println(node.data);
//最后輸出右節(jié)點(diǎn)帖汞，那就用stack來保存它
stack.push(node);
//當(dāng)前節(jié)點(diǎn)置為左節(jié)點(diǎn)戴而，下次循環(huán)就可以輸出左節(jié)點(diǎn)
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
//當(dāng)前節(jié)點(diǎn)置為右節(jié)點(diǎn)
node = stack.pop().rightNode;
}
}
中序遍歷
根據(jù)中序遍歷的順序，對于任一結(jié)點(diǎn)翩蘸，優(yōu)先訪問其左孩子所意，而左孩子結(jié)點(diǎn)又可以看做一個根結(jié)點(diǎn)，然后繼續(xù)訪問其左孩子結(jié)點(diǎn)催首，直到遇到左孩子結(jié)點(diǎn)為空的結(jié)點(diǎn)才停止訪問扶踊，然后按相同的規(guī)則訪問其右子樹。其處理過程如下：
對于任一結(jié)點(diǎn)：
a. 若其左孩子不為空郎任，則將p入棧秧耗，并將p的左孩子設(shè)置為當(dāng)前的p，然后對當(dāng)前結(jié)點(diǎn)再進(jìn)行相同的操作涝滴；
b. 若其左孩子為空绣版，則取棧頂元素并進(jìn)行出棧操作，訪問該棧頂結(jié)點(diǎn)歼疮，然后將當(dāng)前的p置為棧頂結(jié)點(diǎn)的右孩子杂抽；
c. 直到p為空并且棧為空，則遍歷結(jié)束韩脏。
public static void midDisplay(TreeNode node){
//中序遍歷
Stack<TreeNode> stack = new Stack<>();
while (true){
//循環(huán)截止說明當(dāng)前節(jié)點(diǎn)沒有左節(jié)點(diǎn)了
while (node!=null){
//需要先輸出左節(jié)點(diǎn)缩麸，只能講當(dāng)前節(jié)點(diǎn)入棧，暫時不輸出
stack.push(node);
//先輸出左節(jié)點(diǎn)
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
node = stack.pop();
//當(dāng)前節(jié)點(diǎn)沒有左子樹了赡矢，該輪到它自己輸出了
System.out.println(node.data);
//輸出右子樹的過程
node = node.rightNode;
}
}
后序遍歷
后序遍歷的非遞歸實(shí)現(xiàn)是三種遍歷方式中最難的一種杭朱。因為在后序遍歷中，要保證左孩子和右孩子都已被訪問吹散，并且左孩子在右孩子之前訪問才能訪問根結(jié)點(diǎn)弧械，這就為流程控制帶來了難題。
要保證根結(jié)點(diǎn)在左孩子和右孩子訪問之后才能訪問空民，因此對于任一結(jié)點(diǎn)p刃唐，先將其入棧。若p不存在左孩子和右孩子界轩，則可以直接訪問它画饥。當(dāng)前p節(jié)點(diǎn)為左子樹輸出一次，然后重復(fù)入棧過程浊猾，當(dāng)前節(jié)點(diǎn)p為右子樹,那么他的父節(jié)點(diǎn)就必定不能重復(fù)的將右子樹入棧抖甘。則之間循環(huán)輸出即可。
當(dāng)前節(jié)點(diǎn)p有右節(jié)點(diǎn) 葫慎，需要將右節(jié)點(diǎn)放到stack中衔彻，重復(fù)上述過程薇宠。
public static void postListN(TreeNode node){
//后序遍歷
Stack<TreeNode> stack = new Stack<>();
while (true){
while (node!=null){
//最后輸出當(dāng)前節(jié)點(diǎn)，所有先入棧保存
stack.push(node);
node=node.leftNode;
}
if (stack.isEmpty()){
return;
}
//當(dāng)前節(jié)點(diǎn)
node = stack.lastElement();
//在這里當(dāng)前節(jié)點(diǎn)有幾種情況
//1.當(dāng)前節(jié)點(diǎn)沒有右節(jié)點(diǎn)米奸，需要輸出昼接，同時輸出也有幾種情況
// （1 當(dāng)前節(jié)點(diǎn)為左子樹 輸出一次，然后重復(fù)入棧過程
// （2 當(dāng)前節(jié)點(diǎn)為右子樹 當(dāng)前節(jié)點(diǎn)已經(jīng)為右子樹悴晰，輸出完畢慢睡，那么他的父節(jié)點(diǎn)就必定不能重復(fù)的將右子樹入棧
//2.當(dāng)前節(jié)點(diǎn)有右節(jié)點(diǎn) 需要將右節(jié)點(diǎn)放到stack中
//判斷當(dāng)前節(jié)點(diǎn)有沒有右節(jié)點(diǎn)
if (node.rightNode==null){
//沒右節(jié)點(diǎn)
stack.pop();
System.out.println(node.data);
node = node.rightNode;
//判斷當(dāng)前node是不是右分支
while (stack.lastElement().rightNode==node){
//是右分支
TreeNode root = stack.pop();
System.out.println(root.data);
if (stack.isEmpty()){
break;
}
}
}
//判斷棧是否為空
if (!stack.isEmpty()){
//將當(dāng)前節(jié)點(diǎn)置為右節(jié)點(diǎn)
node=stack.lastElement().rightNode;
}else{
node=null;
}
}
}
