① 如何不用递归遍历二叉树
非递归的方法是用存储代替计算，就是在建立树时，实现了存储展开，相当于存储了未来需要遍历的路径，所以就快了。递归是送快递，一层层往下递，非递归是先建好区域仓库，由各地仓库储存发货，所以速度更快，但需要仓库储存（内存占用更多）。
二叉树遍历在数据结构中用得多，这种算法是从kb时代的内存来的，主要用于理解概念，提升编程时的思想用。
实际用途中
如果用于商业一般用数据库代替，根本用不到二叉树，是用存储代替计算。速度快，可以用内存数据库，如我用h2 database的Memory Mode 在java下可以实现1秒1百万次插入。用sqlite内存模式代替以前在c++需要手工管理的数据结构。数据量大一个电脑存不下时，用hadoop/spark/redis，对分布式大数据支持比较好。
如果用于计算量大的任务或内核结构，可以用矩阵数组，链表，k/v这种比较直观模式存储。
对于树和图这种在内存中复杂的数据结构，尽量不要在生产环境下使用，容易内存泄露，用简单方式代替。对于图结构，可以使用图数据库，如neo4j。对于树结构，可以在数据库中存储一棵树。实际上数据库的存储多用树，如B树、B-树、B+树、B*树。
当然如果你写加密算法，这种要求极高的程序时，还是需要考虑性能最大化的，否则一般用存储代替遍历计算，因为内存和硬盘，现在很便宜了，而cpu还是一种宝贵的资源。
② 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[cpp] view plain
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储：
[csharp] view plain
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
二叉树三种递归的遍历方法：
先序遍历 访问根节点→先序遍历左子树→先序遍历右子树
中序遍历 中序遍历左子树→访问根节点→中序遍历右子树
后序遍历 后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法：
[cpp] view plain
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法：
有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历：
[cpp] view plain
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历：
[cpp] view plain
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历：
[cpp] view plain
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法：（用队列的方法）
[cpp] view plain
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）
[cpp] view plain
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
c=pre[pre_s]; /* c储存根节点。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c); /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}
③ 二叉树中序遍历的非递归算法
#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; //遍历右子树
}
}
④ 非递归中序遍历二叉树
//以前曾写过,仅供参考,因为这是截取部分源码,
#include
"afx.h"
#include
"stdio.h"
#include"iostream.h"
#include
"iomanip.h"
#include<malloc.h>
#include<conio.h>
typedef
char
ElemType;
//定义二叉树结点值的类型为字符型
const
int
MaxLength=100;
//结点个数不超过50个
typedef
struct
BTNode{
ElemType
data;
struct
BTNode
*lchild,*rchild;
}BTNode,*
BiTree;
void
PreCreateBiTree(BiTree
&T)
//按先序次序输入，构造二叉树
{
char
ch;
ch=getchar();
//不能用cin来输入，在cin中不能识别空格。
if(ch=='
')
T=NULL;
else{
if(!(T=(BTNode
*)malloc(sizeof(BTNode))))
cout<<"malloc
fail!";
T->data=ch;
PreCreateBiTree(T->lchild);
PreCreateBiTree(T->rchild);
}
}
void
NRInOrder(BiTree
bt)
//非递归的中序遍历算法
{
BiTree
stack[MaxLength],p;
int
top;
if
(bt!=NULL)
{
top=0;
p=bt;
while(p!=NULL||top>0)
{
while(p!=NULL)
{
stack[top]=p;
top++;
p=p->lchild;
}
if
(top>0)
{
top--;
p=stack[top];
cout<<p->data<<"
";
p=p->rchild;
}
}
}
}
⑤ 二叉树非递归遍历的算法
以下为先序，中序，后序三种递归算法
#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}
void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉树的建立\n";
cout<<"\nB----------非递归先序遍历\n";
cout<<"\nC----------非递归中序遍历\n";
cout<<"\nD----------非递归后序遍历\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"请按先序次序输入结点，空结点用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉树建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍历的结果为:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍历的结果为:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"后序遍历的结果为:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"输入无效,请重新输入!\n";
}
}
}
⑥ 二叉树的遍历算法
这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
1.先序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍历左子树
{
x.ptr
=
p;
x.tag
=
L;
//标记为左子树
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec
⑦ 怎样实现二叉树的前序遍历的非递归算法
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
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;
}
⑧ 二叉树的后序遍历，非递归
后序遍历的非递归步骤类似于中序遍历，在遍历左子树前将根结点指针送入栈中
但是左子树遍历完成后，无法访问根结点，只有在右子树遍历完后，才能访问根结点
如果不使用标志位区分第几次到达根结点，可以利用如下的后序遍历特征来完成：
当栈顶元素(根)的右子树为空(即：无右孩子)，或者是右子树非空但是已遍历完，即右孩子恰好是刚才访问过的结点，此时应访问栈顶结点，并在访问后退栈
否则，如果栈顶元素的右孩子非空且未遍历，此时直接访问栈顶元素的右孩子而不退栈
算法要点只是需要记住最近访问过的结点即可，也就是每次访问一个结点后，就记住这个结点
⑨ 二叉树的非递归遍历
#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');
}
⑩ 用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
分块查找
typedef struct
{ int key;
int link;
}SD;
typedef struct
{ int key;
float info;
}JD;
int blocksrch(JD r[],SD nd[],int b,int k,int n)
{ int i=1,j;
while((k>nd[i].key)&&(i<=b) i++;
if(i>b) { printf("\nNot found");
return(0);
}
j=nd[i].link;
while((j<n)&&(k!=r[j].key)&&(r[j].key<=nd[i].key))
j++;
if(k!=r[j].key) { j=0; printf("\nNot found"); }
return(j);
}
哈希查找算法实现
#define M 100
int h(int k)
{ return(k%97);
}
int slbxxcz(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k) return(i);
else return(-1);
}
int slbxxcr(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]>0))
j++;
if(j==M) return(0);
i=(i+j)%M;
if(t[i]<=0)
{ t[i]=k; return(1); }
if(t[i]==k) return(1);
}
int slbxxsc(int t[],int k)
{ int i,j=0;
i=h(k);
while((j<M)&&(t[(i+j)%M]!=k)&&(t[(i+j}%M]!=0))
j++;
i=(i+j)%M;
if(t[i]==k)
{ t[i]=-1; return(1); }
return(0);
}
顺序查找
#define M 500
typedef struct
{ int key;
float info;
}JD;
int seqsrch(JD r[],int n,int k)
{ int i=n;
r[0].key=k;
while(r[i].key!=k)
i--;
return(i);
}
折半查找
int binsrch(JD r[],int n,int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low<=high)&&(found==0))
{ mid=(low+high)/2;
if(k>r[mid].key) low=mid+1;
else if(k==r[mid].key) found=1;
else high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}
虽然都是C++写的，万变不离其中，JAVA我现在 刚学习，就不献丑了