『壹』 二叉樹的中序、前序、後序的遞歸、非遞歸遍歷演算法，層次序的非遞歸遍歷演算法的實現，應包含建樹的實現
#include <iostream>
using namespace std;//二叉樹鏈式存儲的頭文件
typedef char datatype;//結點屬性值類型
typedef struct node // 二叉樹結點類型
{
datatype data;
struct node* lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;//指向二叉樹結點指針
//下面是些棧的操作 為非遞歸實現做准備
typedef struct stack//棧結構定義
{
bintree data[100];//data元素類型為指針
int tag[100];//為棧中元素做的標記，，用於後續遍歷
int top;//棧頂指針
}seqstack;
void push(seqstack *s,bintree t)//進棧
{
s->data[++s->top]=t;
}
bintree pop(seqstack *s) //出棧
{
if(s->top!=-1)
{s->top--;
return(s->data[s->top+1]);
}
else
return NULL;
}
//按照前序遍歷順序建立一棵給定的二叉樹
void createbintree(bintree *t)
{
char ch;
if((ch=getchar())== '-')
*t=NULL;
else
{
*t=(bintnode*)malloc(sizeof(bintnode));//產生二叉樹根結點
(*t)->data=ch;
createbintree(&(*t)->lchild);//遞歸實現左孩子的建立
createbintree(&(*t)->rchild);//遞歸實現右孩子的建立
}
}
//二叉樹前序遍歷遞歸實現
void preorder(bintree t)//t是指針變數，而不是結點結構體變數
{if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
//二叉樹前序遍歷非遞歸實現
void preorder1(bintree t)
{
seqstack s;
s.top=-1;//top 的初始值為-1；
while((t)||(s.top!=-1))//當前處理的子樹不為空或者棧不為空，則循環
{
while(t)
{
cout<<t->data<<" ";//訪問當前子樹根結點
s.top++;
s.data[s.top]=t;
t=t->lchild;
}
if(s.top>-1)
{
t=pop(&s);//當前子樹根結點出棧
t=t->rchild;//訪問其右孩子
}
}
}
//二叉樹中序遍歷遞歸演算法
void inorder(bintree t)
{
if(t)
{
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
// 二叉樹中序遍歷非遞歸演算法
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL)||(s.top!=-1))
{
while(t)
{
push(&s,t);
t=t->lchild;//子樹跟結點全部進棧
}
if(s.top!=-1)
{
t=pop(&s);
cout<<t->data<<" ";//輸出跟結點，其實也就是左孩子或者有孩子（沒有孩子的結點是他父親的左孩子或者有孩子）
t=t->rchild;//進入右孩子訪問
}
}
}
//後續遞歸遍歷二叉樹
void postorder(bintree t)
{
if(t)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
};
//後序遍歷 非遞歸實現
void postorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t)||(s.top!=-1))
{
while(t)
{
s.top++;
s.data[s.top]=t;//子樹根結點進棧
s.tag[s.top]=0;//設此根結點標志初始化為0，表示左右孩子都么有訪問，當訪問完左子樹，tag變為1；
t=t->lchild;//進入左子樹訪問。（左子樹根結點全部進棧）
}
while((s.top>-1)&&(s.tag[s.top]==1))
{
t=s.data[s.top];
cout<<t->data<<" ";//沒有孩子的根結點，也就是它父親的左孩子或者右孩子
s.top--;
}
if(s.top>-1)
{
t=s.data[s.top];
s.tag[s.top]=1;//進入右孩子前，標志tag變為1；
t=t->rchild;//進入右孩子
}
else
t=NULL;
}
}
int main()
{
bintree tree;
cout<<"輸入根結點：" ;
createbintree(&tree);
cout<<"\n 前序遞歸遍歷二叉樹；";
preorder(tree);
cout<<"\n 前序非遞歸遍歷二叉樹：";
preorder1(tree);
cout<<"\n-------------------------------\n";
cout<<"\n 中序遍歷遞歸二叉樹；";
inorder(tree);
cout<<"\n 中序非遞歸遍歷二叉樹：";
inorder1(tree);
cout<<"\n----------------------------\n";
cout<<"\n 後序遞歸遍歷二叉樹：";
postorder(tree);
cout<<"\n 後序非遞歸遍歷二叉樹：";
postorder1(tree);
cout<<endl;
}
『貳』 跪求！！10分奉上！統計二叉樹結點個數的演算法 非遞歸
一般情況下，涉及二叉樹的很多操作都包含兩個方面。一方面，由於二叉樹本身的遞歸定義，因此用遞歸的思想設計其很多操作是順理成章的；另一方面，為了控制過程的深度和節約棧空間，我們有時也會考慮用非遞歸的思想設計很多關於二叉樹的操作。必須說明的是，非遞歸思想一般都需要額外棧或隊列結構的支持。下面來看一下關於統計二叉樹結點個數的非遞歸演算法設計：
1、將根結點插入隊列。
2、判斷隊列是否為空，非空執行第三步，否則執行第四步退出循環。
3、從隊列中取出一個結點，同時將取出結點的兒子結點插入隊列。此外，將計數器加1，再轉到第二步。
4、結束循環。
注意：隊列是先進先出的結構，與棧相反。
如果你根據以上仍然不能寫出完整的程序，下面的程序可作為你的參考。
int size()//返回結點數函數
{
linkqueue<node*>list;//定義元素為node*型的隊列
int sum=0;
list.push(root);
while(!list.empty())
{
node* p=list.top();//保存即將出隊的元素
list.pop();//隊列首元素出隊
if(p->lchild)//左兒子不為空，即進隊
list.push(p->lchild);
if(p->rchild)//同上
list.push(p->rchild);
sum++;//計數器增1
}
return sum;
}
要想完全把握以上程序你必須對隊列的結構有很好的理解。此外，需要說明的是，計數器是以出隊元素個數為指標進行計數的，而非進隊元素。這樣可使程序簡潔和容易理解得多。
『叄』 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
1. 先序遍歷
在先序遍歷中，對節點的訪問工作是在它的左右兒子被訪問之前進行的。換言之，先序遍歷訪問節點的順序是根節點-左兒子-右兒子。由於樹可以通過遞歸來定義，所以樹的常見操作用遞歸實現常常是方便清晰的。遞歸實現的代碼如下：
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
printf(「%d\n」, BT->Data); //對節點做些訪問比如列印
PreOrderTraversal(BT->Left); //訪問左兒子
PreOrderTraversal(BT->Right); //訪問右兒子
}
}
由遞歸代碼可以看出，該遞歸為尾遞歸（尾遞歸即遞歸形式在函數末尾或者說在函數即將返回前）。尾遞歸的遞歸調用需要用棧存儲調用的信息，當數據規模較大時容易越出棧空間。雖然現在大部分的編譯器能夠自動去除尾遞歸，但是即使如此，我們不妨自己去除。非遞歸先序遍歷演算法基本思路：使用堆棧
a. 遇到一個節點，訪問它，然後把它壓棧，並去遍歷它的左子樹；
b. 當左子樹遍歷結束後，從棧頂彈出該節點並將其指向右兒子，繼續a步驟；
c. 當所有節點訪問完即最後訪問的樹節點為空且棧空時，停止。
實現代碼如下：
void PreOrderTraversal(BinTree BT)
{
BinTree T = BT;
Stack S = CreatStack(MAX_SIZE); //創建並初始化堆棧S
while(T || !IsEmpty(S))
{
while(T) //一直向左並將沿途節點訪問（列印）後壓入堆棧
{
printf("%d\n", T->Data);
Push(S, T);
T = T->Left;
}
if (!IsEmpty(S))
{
T = Pop(S); //節點彈出堆棧
T = T->Right; //轉向右子樹
}
}
}
由以上例子可以看出，遞歸與非遞歸的本質區別就是遞歸是不斷循環調用同一過程，非遞歸是循環執行同一個動作，並且非遞歸有入棧與出棧的過程，因此更節省存儲空間。個人淺見，歡迎指正。