java二叉樹中序遍歷

㈠ 用java語言實現二叉樹的層次遍歷的非遞歸演算法及查找演算法。

先序非遞歸演算法
【思路】
假設：T是要遍歷樹的根指針，若T != NULL
對於非遞歸演算法，引入棧模擬遞歸工作棧，初始時棧為空。
問題：如何用棧來保存信息，使得在先序遍歷過左子樹後，能利用棧頂信息獲取T的右子樹的根指針？
方法1：訪問T->data後，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，再先序遍歷T的右子樹。
方法2：訪問T->data後，將T->rchild入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T->rchild，出棧，遍歷以該指針為根的子樹。
【演算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【演算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基於方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。

中序非遞歸演算法
【思路】
T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹後，訪問根，再遍歷右子樹。
問題：如何用棧來保存信息，使得在中序遍歷過左子樹後，能利用棧頂信息獲取T指針？
方法：先將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，訪問T->data，再中序遍歷T的右子樹。
【演算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
進一步考慮：對於處理流程中的循環體的直到型、當型+直到型的實現。

後序非遞歸演算法
【思路】
T是要遍歷樹的根指針，後序遍歷要求在遍歷完左右子樹後，再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法，結點入棧時，配一個標志tag一同入棧(0：遍歷左子樹前的現場保護，1：遍歷右子樹前的現場保護)。
首先將T和tag(為0)入棧，遍歷左子樹；返回後，修改棧頂tag為1，遍歷右子樹；最後訪問根結點。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【演算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}

㈡ java二叉樹中序遍歷 的遞歸演算法沒有看懂。。search(data.getLeft());之後不就回到最左邊的一個

最左邊的節點是沒有左子樹和右子樹的。
if(data.getLeft()!=null){ // 這里getLetf()為null

search(data.getLeft());
}
System.out.print(data.getObj()+","); //只有這句是執行的！

if(data.getRight()!=null){ // 這里getRight()為null

search(data.getRight());
}

然後就會退到上一個節點的遍歷函數了。

㈢ 二叉樹中什麼是中序序列

中序序列。

中序遍歷首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。若二叉樹為空則結束返回，否則：

（1）中序遍歷左子樹

（2）訪問根結點

（3）中序遍歷右子樹

如圖所示二叉樹，中序遍歷結果：DBEAFCG

中序遍歷數學表達式形式：

當對一棵數學表達式樹進行中序，前序和後序遍歷時，就分別得到表達式的中綴、前綴和後綴形式。中綴（infix）形式即平時所書寫的數學表達式形式，在這種形式中，每個二元操作符（也就是有兩個操作數的操作符）出現在左操作數之後，右操作數之前。在使用中綴形式時，可能會產生一些歧義。

例如，x+y ×z可以理解為(x+y) ×z或x+ (y ×z)。為了避免這種歧義，可對操作符賦於優先順序並採用優先順序規則來分析中綴表達式。在完全括弧化的中綴表達式中，每個操作符和相應的操作數都用一對括弧括起來。

更甚者把操作符的每個操作數也都用一對括弧括起來。如( (x) + (y) )，( (x) + ( (y) * (z) ) )和( ( (x) + (y) ) * ( (y) + (z) ) ) * (w)。

㈣ 根據二叉樹的先序遍歷結果輸出中序遍歷

編一個程序，讀入用戶輸入的一串先序遍歷字元串，根據此字元串建立一個二叉樹（以指針方式存儲）。 例如如下的先序遍歷字元串： ABC##DE#G##F### 其中「#」表示的是空格，空格字元代表空樹。建立起此二叉樹以後，再對二叉樹進行中序遍歷，輸出遍歷結果。

輸入包括1行字元串，長度不超過100。

可能有多組測試數據，對於每組數據，
輸出將輸入字元串建立二叉樹後中序遍歷的序列，每個字元後面都有一個空格。
每個輸出結果佔一行。

abc##de#g#f###

c b e g d f a

㈤ 二叉樹的先序,中序,後序遍歷是

前序遍歷就是先遍歷根節點，然後遍歷左節點，最後是右節點；

中序遍歷就是先遍歷左節點，然後遍歷中間的根節點，最後是右節點；

後序遍歷就是先遍歷左節點，然後遍歷是右節點，最後是中間的根節點。

二叉樹的這三種遍歷方法，是按照每顆子樹的根節點順序遍歷的。

(5)java二叉樹中序遍歷擴展閱讀：

例子：已知二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）

(1)中序遍歷：debac

後序遍歷：dabec

後序遍歷序列的最後一個結點是根結點，所以可知c為根結點。

中序遍歷序列的根結點在中間，其左邊是左子樹，右邊是右子樹。所以從中序遍歷序列中可看出，根結點c只有左子樹，沒有右子樹。

(2)中序遍歷：deba

後序遍歷：dabe

後序遍歷序列的最後一個結點是根結點，所以可知e為c的左子樹的根結點。

中序遍歷序列的根結點在中間，其左邊是左子樹，右邊是右子樹。所以從中序遍歷序列中可看出，根結點e的左子結點是d，右子樹是ba。

(3)中序遍歷：ba

後序遍歷：ab

由後序遍歷序列可知b為e的右子樹的根結點。由中序遍歷序列中可看出，a為根結點b的右子結點。

㈥ 關於二叉樹的前序、中序、後序三種遍歷

二叉樹中遍歷分為三種：前序、中序、後序，是根據根節點的順序命名的。

例如下圖：

該圖中，A為根節點，B、C分別為左右節點。前序順序為ABC（根節點最先，然後是同級先左後右），中序順序為BAC（先左後根最後右），後序為BCA（先左後右最後根）。

運用整體和部分的思維，很容易就能分析這些遍歷方式，舉例說明中序遍歷的過程，如下表：