二叉樹遍歷非遞歸java

1. 二叉樹後序遍歷非遞歸演算法

#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建樹
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//這是遞歸實現
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化棧
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入棧
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//彈出棧頂元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取棧頂元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//這是非遞歸後序實現
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非遞歸後序遍歷\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以運行。
我空間中有中序遍歷的非遞歸實現。
不過給你寫的是後序遍歷的遞歸實現和非遞歸實現，它兩個輸出的結果是一致的。
輸入
234##5#6##7##回車
就可以看到結果。
中序遍歷及其對應樹可以參考我空間中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html

2. 用java編寫一個非遞歸的二叉樹的遍歷，急要！！！

import java.util.LinkedList;
import java.util.Stack;

public class MainTest {

public static void scanTree1(Tree root) { //橫向遍歷
LinkedList<Tree> queue = new LinkedList<Tree>();
queue.add(root);
while (!queue.isEmpty()) {
Tree node = queue.poll();
System.out.println(node.getData());
Tree left = node.getLeft();
Tree right = node.getRight();
if (left != null) {
queue.add(left);
}
if (right != null) {
queue.add(right);
}
}
}

public static void scanTree2(Tree root) { //縱向前序
Tree node = root;
Stack<Boolean> stack = new Stack<Boolean>();
boolean leftFlg = false;
while (true) {
System.out.println(node.getData());
if (node.getLeft() != null && leftFlg) {
node = node.getLeft();
stack.add(true);
leftFlg = true;
} else if (node.getRight() != null) {
node = node.getRight();
stack.add(false);
leftFlg = true;
} else if (stack.isEmpty()) {
break;
} else if (stack.pop()) {
node = node.getParent();
leftFlg = false;
}
}
}

public static void scanTree3(Tree root) {//縱向中序
Tree node = root;
Stack<Boolean> stack = new Stack<Boolean>();
boolean leftFlg = false;
while (true) {
if (node.getLeft() != null && leftFlg) {
node = node.getLeft();
stack.add(true);
leftFlg = true;
} else if (node.getRight() != null) {
System.out.println(node.getData());
node = node.getRight();
stack.add(false);
leftFlg = true;
} else if (stack.isEmpty()) {
break;
} else if (stack.pop()) {
node = node.getParent();
leftFlg = false;
}
}
}

public static void scanTree4(Tree root) {//縱向後序
Tree node = root;
Stack<Boolean> stack = new Stack<Boolean>();
boolean leftFlg = false;
while (true) {
if (node.getLeft() != null && leftFlg) {
node = node.getLeft();
stack.add(true);
leftFlg = true;
} else if (node.getRight() != null) {
node = node.getRight();
stack.add(false);
leftFlg = true;
} else if (stack.isEmpty()) {
break;
} else if (stack.pop()) {
System.out.println(node.getData());
node = node.getParent();
leftFlg = false;
}
}
}

public static void main(String[] args) {
Tree root = new Tree();
// TODO
scanTree1(root);
scanTree2(root);
scanTree3(root);
scanTree4(root);
}
}

class Tree {
private Tree left;
private Tree right;
private Tree parent;
private Object data;

public Object getData() {
return data;
}

public void setData(Object data) {
this.data = data;
}

public Tree getLeft() {
return left;
}

public void setLeft(Tree left) {
this.left = left;
}

public Tree getRight() {
return right;
}

public void setRight(Tree right) {
this.right = right;
}

public Tree getParent() {
return parent;
}

public void setParent(Tree parent) {
this.parent = parent;
}
}

3. java 用遞歸創建二叉樹，非遞歸遍歷二叉樹輸出節點

我自己用遞歸寫了下，不知道能不能給你幫助：

測試類：
package tree;

import java.util.*;

public class Test {

public static void main(String[] args){
List<Tree> trees=new ArrayList<Tree>();
int id=1;
Tree tree1=new Tree(0,id++,"張三豐");
Tree tree2=new Tree(tree1.getId(),id++,"武當宋大俠宋遠橋");
Tree tree3=new Tree(tree1.getId(),id++,"武當俞二俠俞蓮舟");
Tree tree4=new Tree(tree1.getId(),id++,"武當俞三俠俞岱岩");
Tree tree5=new Tree(tree1.getId(),id++,"武當張四俠張松溪");
Tree tree6=new Tree(tree1.getId(),id++,"武當張五俠張翠山");
Tree tree7=new Tree(tree1.getId(),id++,"武當殷六俠殷梨亭");
Tree tree8=new Tree(tree1.getId(),id++,"武當莫七俠莫聲谷");
Tree tree9=new Tree(tree6.getId(),id++,"明教張無忌");
Tree tree13=new Tree(tree2.getId(),id++,"叛徒宋青書");

Tree tree10=new Tree(0,id++,"任我行");
Tree tree11=new Tree(tree10.getId(),id++,"令狐沖");
Tree tree12=new Tree(tree10.getId(),id++,"任盈盈");

trees.add(tree1);
trees.add(tree2);
trees.add(tree3);
trees.add(tree4);
trees.add(tree5);
trees.add(tree6);
trees.add(tree7);
trees.add(tree8);
trees.add(tree9);
trees.add(tree10);
trees.add(tree11);
trees.add(tree12);
trees.add(tree13);

for(int i=0;i<trees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==0){
tree.showChildTree(trees);
}
}

}

}

樹類：
package tree;

import java.util.List;

public class Tree {
private int parentId;
private int id;
private String showStr;
private String Spaces="";

public Tree() {
// TODO Auto-generated constructor stub
}
public Tree(int parentId,int id,String showStr){
this.parentId=parentId;
this.id=id;
this.showStr=showStr;
}

public void showChildTree(List<Tree> trees){
if(parentId!=0){
trees.get(id-1).setSpaces(trees.get(parentId-1).getSpaces()+" ");
}
System.out.println(trees.get(id-1).getSpaces()+showStr);
for(int i=0;i<trees.size();i++){
Tree tree=trees.get(i);
if(tree.getParentId()==id){
tree.showChildTree(trees);
}
}

}

public int getParentId() {
return parentId;
}

public void setParentId(int parentId) {
this.parentId = parentId;
}

public int getId() {
return id;
}

public void setId(int id) {
this.id = id;
}

public String getShowStr() {
return showStr;
}

public void setShowStr(String showStr) {
this.showStr = showStr;
}

public String getSpaces() {
return Spaces;
}

public void setSpaces(String spaces) {
Spaces = spaces;
}

}

效果圖：
張三豐
武當宋大俠宋遠橋
叛徒宋青書
武當俞二俠俞蓮舟
武當俞三俠俞岱岩
武當張四俠張松溪
武當張五俠張翠山
明教張無忌
武當殷六俠殷梨亭
武當莫七俠莫聲谷
任我行
令狐沖
任盈盈

4. 用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;
}
}

5. 二叉樹的後序遍歷，非遞歸

後序遍歷的非遞歸步驟類似於中序遍歷，在遍歷左子樹前將根結點指針送入棧中
但是左子樹遍歷完成後，無法訪問根結點，只有在右子樹遍歷完後，才能訪問根結點

如果不使用標志位區分第幾次到達根結點，可以利用如下的後序遍歷特徵來完成：
當棧頂元素(根)的右子樹為空(即：無右孩子)，或者是右子樹非空但是已遍歷完，即右孩子恰好是剛才訪問過的結點，此時應訪問棧頂結點，並在訪問後退棧
否則，如果棧頂元素的右孩子非空且未遍歷，此時直接訪問棧頂元素的右孩子而不退棧

演算法要點只是需要記住最近訪問過的結點即可，也就是每次訪問一個結點後，就記住這個結點

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

#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; //遍歷右子樹

}

}

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

#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; //遍歷右子樹

}

}

8. 怎樣實現二叉樹的前序遍歷的非遞歸演算法

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp]
view
plain

print?
int
(const
BiTree
&T,
int
(*VisitNode)(TElemType
data))
{
if
(T
==
NULL)
{
return
-1;
}
BiTNode
*pBiNode
=
T;
SqStack
S;
InitStack(&S);
Push(&S,
(SElemType)T);
while
(!IsStackEmpty(S))
{
while
(pBiNode)
{
VisitNode(pBiNode->data);
if
(pBiNode
!=
T)
{
Push(&S,
(SElemType)pBiNode);
}
pBiNode
=
pBiNode->lchild;
}
if(pBiNode
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
}
if
(
pBiNode->rchild
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
//如果此時棧已空，就有問題
}
pBiNode
=
pBiNode->rchild;
}
return
0;
}

9. 如何編程實現二叉樹的非遞歸遍歷

前序遍歷按照「根結點-左孩子-右孩子」的順序進行訪問。
1.遞歸實現

void preOrder1(BinTree *root) //遞歸前序遍歷
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}

2.非遞歸實現
根據前序遍歷訪問的順序，優先訪問根結點，然後再分別訪問左孩子和右孩子。即對於任一結點，其可看做是根結點，因此可以直接訪問，訪問完之後，若其左孩子不為空，按相同規則訪問它的左子樹；當訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：
對於任一結點P：
1)訪問結點P，並將結點P入棧;
2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點並進行出棧操作，並將棧頂結點的右孩子置為當前的結點P，循環至1);若不為空，則將P的左孩子置為當前的結點P;
3)直到P為NULL並且棧為空，則遍歷結束。

void preOrder2(BinTree *root) //非遞歸前序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}

二.中序遍歷
中序遍歷按照「左孩子-根結點-右孩子」的順序進行訪問。
1.遞歸實現

void inOrder1(BinTree *root) //遞歸中序遍歷
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}

2.非遞歸實現
根據中序遍歷的順序，對於任一結點，優先訪問其左孩子，而左孩子結點又可以看做一根結點，然後繼續訪問其左孩子結點，直到遇到左孩子結點為空的結點才進行訪問，然後按相同的規則訪問其右子樹。因此其處理過程如下：
對於任一結點P，
1)若其左孩子不為空，則將P入棧並將P的左孩子置為當前的P，然後對當前結點P再進行相同的處理；
2)若其左孩子為空，則取棧頂元素並進行出棧操作，訪問該棧頂結點，然後將當前的P置為棧頂結點的右孩子；
3)直到P為NULL並且棧為空則遍歷結束

void inOrder2(BinTree *root) //非遞歸中序遍歷
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}

10. 二叉樹的非遞歸遍歷

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
void visit(int e)
{
printf("->%d",e);
}
void InitBiTree(BiTree &T)// 操作結果：構造空二叉樹T
{
T=NULL;
}
void CreateBiTree(BiTree &T)
//按先序次序輸入二叉樹中結點的值,構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。
{
int number;
scanf("%d",&number); // 輸入結點的值
if(number==0) // 結點的值為空
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode)); // 生成根結點
if(!T)
exit(OVERFLOW);
T->data=number; // 將值賦給T所指結點
CreateBiTree(T->lchild); // 遞歸構造左子樹
CreateBiTree(T->rchild); // 遞歸構造右子樹
}
}

void DestroyBiTree(BiTree &T)// 初始條件：二叉樹T存在。操作結果：銷毀二叉樹T
{
if(T) // 非空樹
{
DestroyBiTree(T->lchild); // 遞歸銷毀左子樹，如無左子樹，則不執行任何操作
DestroyBiTree(T->rchild); // 遞歸銷毀右子樹，如無右子樹，則不執行任何操作
free(T); // 釋放根結點
T=NULL; // 空指針賦0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
//二叉樹T存在，Visit是對結點操作的應用函數,先序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T) //T不為空時遍歷
{
Visit(T->data); // 先訪問根結點
PreOrderTraverse(T->lchild,Visit); // 再先序遍歷左子樹
PreOrderTraverse(T->rchild,Visit); // 最後先序遍歷右子樹
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
//二叉樹T存在，Visit是對結點操作的應用函數，中序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍歷左子樹
Visit(T->data); // 再訪問根結點
InOrderTraverse(T->rchild,Visit); // 最後中序遍歷右子樹
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
// 二叉樹T存在，Visit是對結點操作的應用函數，後序遞歸遍歷T，對每個結點調用函數Visit一次且僅一次
{
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先後序遍歷左子樹
PostOrderTraverse(T->rchild,Visit); // 再後序遍歷右子樹
Visit(T->data); // 最後訪問根結點
}
}

void main()
{
char m;
BiTree T;
InitBiTree(T); // 初始化二叉樹T
do{
printf("\n");
printf("##################二叉樹的基本操作###########################\n");
printf("×××××××××1.二叉樹的創建××××××××××××××\n");
printf("×××××××××2.先序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××3.中序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××4.後序遞歸遍歷二叉樹×××××××××××\n");
printf("×××××××××5.退出程序××××××××××××××××\n");
printf("#############################################################\n");
printf("請輸入你的選擇:");
scanf("%c",&m);
switch(m) {
case '1':
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，如：（1 2 3 0 0 4 5 0 6 0 0 7 0 0 0）\n");
printf("\n請按先序次序輸入二叉樹中結點的值：");
CreateBiTree(T); // 建立二叉樹T
break;
case '2':
printf("先序遞歸遍歷二叉樹： ");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
break;
case '3':
printf("\n中序遞歸遍歷二叉樹： ");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
break;
case '4':
printf(" \n後序遞歸遍歷二叉樹：");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
break;
case '5':break;
default:
printf("輸入的字元不對，請重新輸入!");
break;

}
getchar();
}while(m!='5');

}