中序遍歷左子樹演算法

A. 求c#前中後序遍歷二叉樹的演算法及思想

下面簡單介紹一下幾種演算法和思路：
先序遍歷：
1. 訪問根結點
2. 按先序遍歷左子樹;
3. 按先序遍歷右子樹;
4. 例如：遍歷已知二叉樹結果為：A->B->D->G->H->C->E->F
中序遍歷：
1. 按中序遍歷左子樹;
2. 訪問根結點;
3. 按中序遍歷右子樹;
4. 例如遍歷已知二叉樹的結果：B->G->D->H->A->E->C->F
後序遍歷：
1. 按後序遍歷左子樹;
2. 按後序遍歷右子樹;
3. 訪問根結點;
4. 例如遍歷已知二叉樹的結果：G->H->D->B->E->F->C->A
層次遍歷：
1.從上到下,從左到右遍歷二叉樹的各個結點(實現時需要借輔助容器);
2.例如遍歷已知二叉樹的結果：A->B->C->D->E->F->G->H

附加代碼：
二叉遍歷演算法解決方案
using System;
using System.Collections.Generic;
using System.Text;
namespace structure
{
class Program
{
二叉樹結點數據結構的定義#region 二叉樹結點數據結構的定義
//二叉樹結點數據結構包括數據域,左右結點以及父結點成員;
class nodes<T>
{
T data;
nodes<T> Lnode, Rnode, Pnode;
public T Data
{
set { data = value; }
get { return data; }

}
public nodes<T> LNode
{
set { Lnode = value; }
get { return Lnode; }
}
public nodes<T> RNode
{
set { Rnode = value; }
get { return Rnode; }

}

public nodes<T> PNode
{
set { Pnode = value; }
get { return Pnode; }

}
public nodes()
{ }
public nodes(T data)
{
this.data = data;
}

}
#endregion

#region 先序編歷二叉樹
static void PreOrder<T>(nodes<T> rootNode)
{
if (rootNode != null)
{
Console.WriteLine(rootNode.Data);
PreOrder<T>(rootNode.LNode);
PreOrder<T>(rootNode.RNode);

}
}

#endregion

B. C++中二叉樹的前序（後序、中序）遍歷分別是什麼意思相應的樹圖怎麼看

二叉樹的遍歷是指按照一定次序訪問樹中所有結點，並且每個節點僅被訪問一次的過程。

1、先序遍歷（前序）

（1）訪問根節點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹。

2、中序遍歷

（1）中序遍歷左子樹；

（2）訪問根節點；

（3）中序遍歷右子樹。

3、後序遍歷

（1）後序遍歷左子樹；

（2）後序遍歷右子樹『

（3）訪問根節點。

記住訪問根結點的時機就可以區分三種遍歷方法了。

同時知道一棵二叉樹的先序序列和中序序列，或者同時知道中序序列和後序序列，就能確定這棵二叉樹的結構。構造演算法相信你已經學習過，在任一本介紹數據結構的書上應該也有描述的。由於涉及到演算法細節，這里就不細說了。

下面根據你例子中給出的序列來介紹確定二叉樹結構的步驟：

（1）後序序列中最後一個為樹的根節點，即c為二叉樹的根結點；

（2）中序遍歷中根節點把序列分為左右子樹的中序遍歷序列兩個部分，在你的例子在右子樹沒有中序遍歷序列（中序遍歷序列中c右邊沒有序列），故可知二叉樹的左子樹的後序遍歷序列為dabe，中序遍歷序列為deba；

（3）應用（1）的方法，確定c的左子樹的根結點為e，並把以e為根結點的子樹的中序遍歷序列劃分為d（以e為根結點的左子樹的中序遍歷序列）和ba（以e為根結點的右子樹的中序遍歷序列）兩個部分，後序遍歷序列為dab；

（4）應用（1）的方法，可確定e的左結點為b；

（5）應用（1）的方法，可確定e的右結點為a；

（6）最後，可確定a無左結點，右結點為d。

構造的二叉樹如圖中所示。

那麼可獲得前序遍歷序列為cedba

C. 二叉樹的遍歷

9二叉樹的遍歷（1）遍歷：遍歷（traverse）一個有限結點的集合，意味著對該集合中的每個結點訪問且僅訪問一次。（2）三種遍歷方式先序遍歷（VLR）：先序就是先訪問結點元素，然後是左，然後是右。若二叉樹不為空
訪問根結點；
先序遍歷左子樹；
先序遍歷右子樹。
先序遍歷序列：
A
B
D
C
E
F
template
void
BinaryTree
::PreOrder(){
PreOrder(root);}template
void
BinaryTree
::PreOrder(BTNode
*
t){
if(t)
{
cout<<(t->element);
PreOrder(t->lChild);
PreOrder(t->rChild);
}}
中序遍歷（LVR）若二叉樹不為空
中序遍歷左子樹；
訪問根結點；
中序遍歷右子樹。
中序遍歷序列：B
D
A
E
C
F
template
void
BinaryTree
::InOrder(){
InOrder(root);}template
void
BinaryTree
::InOrder(BTNode
*
t){
if(t)
{
InOrder(t->lChild);
cout<<(t->element);
InOrder(t->rChild);
}}
後序遍歷
（LRV）若二叉樹不為空
後序遍歷左子樹；
後序遍歷右子樹；
訪問根結點。後序遍歷序列：D
B
E
F
C
A
template
void
BinaryTree
::PostOrder(){
PostOrder(root);}template
void
BinaryTree
::PostOrder(BTNode
*
t){
if(t)
{
PostOrder(t->lChild);
PostOrder(t->rChild);
cout<<(t->element);
}}

D. 寫出二叉樹的先序遍歷、中序遍歷、後序遍歷。

一、先序遍歷：

1、訪問根節點

2、前序遍歷左子樹

3、前序遍歷右子樹

二、中序遍歷：

1、中序遍歷左子樹

2、訪問根節點

3、中序遍歷右子樹

三、後序遍歷：

1、後序遍歷左子樹

2、後序遍歷右子樹

3、訪問根節點

下面介紹一下例子與方法：

1、畫樹求法：

第一步，根據前序遍歷的特點，我們知道根結點為G

第二步，觀察中序遍歷ADEFGHMZ。其中root節點G左側的ADEF必然是root的左子樹，G右側的HMZ必然是root的右子樹。

第三步，觀察左子樹ADEF，左子樹的中的根節點必然是大樹的root的leftchild。在前序遍歷中，大樹的root的leftchild位於root之後，所以左子樹的根節點為D。

第四步，同樣的道理，root的右子樹節點HMZ中的根節點也可以通過前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節點遍歷完之後才會遍歷右子樹，並且遍歷的左子樹的第一個節點就是左子樹的根節點。同理，遍歷的右子樹的第一個節點就是右子樹的根節點。

第五步，觀察發現，上面的過程是遞歸的。先找到當前樹的根節點，然後劃分為左子樹，右子樹，然後進入左子樹重復上面的過程，然後進入右子樹重復上面的過程。最後就可以還原一棵樹了。該步遞歸的過程可以簡潔表達如下：

1 確定根,確定左子樹，確定右子樹。

2 在左子樹中遞歸。

3 在右子樹中遞歸。

4 列印當前根。

那麼，我們可以畫出這個二叉樹的形狀：

那麼，根據後序的遍歷規則，我們可以知道，後序遍歷順序為：AEFDHZMG

E. 二叉樹層次和中序遍歷演算法

先序非遞歸演算法
【思路】
假設：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;
}
}

F. 中序遍歷二叉樹的演算法

中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void
inorder(bintree
t)
{
//演算法里①~⑥是為了說明執行過程加入的標號
①
if(t)
{
//
如果二叉樹非空
②
inorder(t->lchild)；
③
printf("％c"，t->data)；
//
訪問結點
④
inorder(t->rchild);
⑤
}
⑥
}
//
inorder

G. c++二叉樹的幾種遍歷演算法

遍歷二叉樹的所有結點且僅訪問一次。按照根節點位置的不同分為前序遍歷，中序遍歷，後序遍歷（除此之外還有層次遍歷，但不常用，此處不做解釋）。

1.前序遍歷：根節點->左子樹->右子樹（根節點在前面）。

2.中序遍歷：左子樹->根節點->右子樹（根節點在中間）。

3.後序遍歷：左子樹->右子樹->根節點（根節點在後邊）。

例如：求下面樹的三種遍歷：

前序遍歷：abdefgc；

中序遍歷：debgfac；

後序遍歷：edgfbca。

H. 計算機二級二叉樹演算法

1、二叉樹的概念

二叉樹是一種特殊的樹形結構，每個結點最多隻有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態。

2、二叉樹的性質

性質1 在二叉樹的第k層上，最多有2^(k-1)(k≥1）個結點。

性質2 深度為m的二叉樹最多有2^m-1個結點。

性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個。

性質4 具有n個結點的二叉樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。

I. 二叉樹中序遍歷的非遞歸演算法

#define MAXNODE 100 //二叉樹最大節點數
//定義二叉樹鏈式結構
typedef struct BitNode
{
char data; //數據域
struct BitNode *lchild,*rchild;//左右指針域
}BitNode,*BiTree;
//二叉樹進行中序非遞歸遍歷
void NRInorder(BiTree t)
{
BiTree s; //s-指向當前節點
BiTree stack[MAXNODE]; //定義棧
int top=-1; //初始化棧頂指針

if(t==NULL)
return;

stack[++top]=t;//根指針入棧
s=t->lchild; //s指向左子樹
while(s!=NULL||top!=-1)//當存在節點(涉及到根下右子樹)或者棧不為空,進行遍歷
{
while(s!=NULL) //如果存在節點,尋找最左子樹並入棧
{
if(top>=MAXNODE-1)
{
printf("棧為滿\n");
return;
}
stack[++top]=s;//當前節點入棧
s=s->lchild; //左子樹進行遍歷
}

if(top==-1)
{
printf("棧為空\n");
return;
}

s=stack[top--]; //彈出棧頂元素到s中
printf("%c ",s->data); //輸出當前節點元素值
s=s->rchild; //遍歷右子樹

}

}

J. 中序遍歷二叉樹的演算法

如下， 中序的遍歷二叉樹：

struct Node //二叉樹的節點。
{
int value;
Node *left;
Node *right;
};
//中序遍歷二叉樹
void midTravel(Node *node)
{
if(node == NULL) return;
midTravel(node->left); //遞歸的周遊左子樹
printf("%d ", node->value); //列印本節點的值
midTravel(node->right);//遞歸的周遊右子樹
}