中序遍历左子树算法

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);//递归的周游右子树
}