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（先左后右最后根）。

运用整体和部分的思维，很容易就能分析这些遍历方式，举例说明中序遍历的过程，如下表：