① 如何不用遞歸遍歷二叉樹
非遞歸的方法是用存儲代替計算，就是在建立樹時，實現了存儲展開，相當於存儲了未來需要遍歷的路徑，所以就快了。遞歸是送快遞，一層層往下遞，非遞歸是先建好區域倉庫，由各地倉庫儲存發貨，所以速度更快，但需要倉庫儲存（內存佔用更多）。
二叉樹遍歷在數據結構中用得多，這種演算法是從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我現在 剛學習，就不獻丑了