⑴ 二叉樹的非遞歸遍歷
#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');
}
⑵ 二叉樹後序遍歷非遞歸演算法程序跪求解釋
一，大循環中的第一個循環，當前節點一直往左走一直走到頭，並且把走過的節點壓棧，這個循環遍歷完成後，棧裡面都是左邊走過但是右邊還沒有走過的節點
二，從最左邊那個沒有更左的那個節點，它位於棧頂，因為這時棧頂不是一個右節點，第二個循環跳過，然後把棧頂結點的右節點標記為r並以此作為根節點重復之前的操作
回溯：
因為一直往下層走，總會遇到既沒有左節點有沒有右節點的節點，就是葉子節點，就開始往回退 取他的右節點，取之前會把該節點標記為r，但是他沒有右節點，為null，就會跳過第一個循環，來到第二個，那麼這個葉子就從棧中pop掉，新的棧頂結點是那個葉子的父節點，如果沒有右節點，那他就成了葉子，更簡單，如果有右節點，那麼繼續二
一步一步推就是這樣子，需要考慮所有情況，會把問題想復雜，但是利用遞歸的思想就好想了
參考遞歸演算法
void preOrder2(BinTree *root)
{
preOrder(root->lchild);
preOrder(root->rchild);
}
第一個函數就是第一個小循環，只走左邊，然後把新得到的節點作為根節點，繼續調用第一個函數，得到左節點，然後再作為根節點，直到左節點為空；
第二個函數就是最後一個if，非遞歸演算法中是從棧頂取，就是左邊走過了的節點，相當於遞歸中，第一個函數執行完已經返回，然後取他的右節點作為根節點，繼續遞歸
⑶ 二叉樹中序遍歷的非遞歸演算法
#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; //遍歷右子樹
}
}
⑷ 怎麼用非遞歸演算法編寫二叉樹的插入函數和構造函數
我沒有測試，你測試看看對不對。
bilist * insert(bilist ** r, bilist * s)
{
bilist * p = *r;
while (p != NULL)
p = (s->key < p->key) ? p->lchild : p->rchild;
return (*(&p) = s);
}
⑸ 《數據結構》遍歷二叉樹的非遞歸演算法的疑問。
首先敬仰一下樓主的勤奮！
我主要針對第二個演算法說，我覺得上面這段話也是在講第二個演算法。其實兩個演算法差不太多。
1. 棧頂記錄中的指針其實就是指棧頂，每次push()進去或者pop()出來的那個p。他代表的是正在訪問的節點得下一個節點。比如，訪問一個樹t的左子樹t->lchild時，棧頂就是t；訪問t->lchild->lchild時，棧頂就是t->lchild。訪問t->rchild時，棧頂為NULL；訪問t->lchild->rchild時，棧頂為t；訪問t->rchild->lchild時，棧頂也是t；訪問t->rchild->rcchild時，棧頂仍為NULL。他的意義就是，在訪問完了當前的子樹之後，就會去訪問棧頂記錄的指針對應的節點的數據。
2. 關於「工作記錄」那個詞，我覺得還是別深究了。那段話意思是要仿照編譯器把遞歸編譯成迭代的思路來自己寫迭代演算法，可是實際上後面給出的演算法里根本沒有嚴格執行上述思路，寫出來的演算法並不是嚴格意義上的可以一般性替換遞歸的迭代演算法。所以追究那個詞也沒意義，明白迭代遍歷的演算法怎麼用就夠了。等以後對遞歸有了更深刻的認識，自然就明白了。其實就是函數遞歸調用自身之前像中斷那樣保存自己的工作環境和進度。
3. （2）句並不矛盾。他說「指針為空時」和「指針指向的xxx」中間不是有句「退回上一層」么，那就表示pop()，於是原來那個在棧頂的空指針彈出去了，原來在第二位的指針現在到了棧頂。於是後面那句指的是對這個指針進行操作。
⑹ 怎樣實現二叉樹的前序遍歷的非遞歸演算法
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
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;
}
⑺ 數據結構考試，二叉樹的中序遍歷的非遞歸演算法是什麼
第一題：
boolInOrderTraverse(BinNode*Node,void(*fun)(BinNode*Node))
{
StackS;//聲明棧
InitBtStack(&);//初始化棧
while(!StackIsEmpty(&S)||Node)//棧空且節點為NULL是遍歷完成
{
while(Node->lchild)//如果<節點左子樹非空>則進棧,直到左子樹為空的節點
{
Push(&S,&Node);
Node=Node->lchild;
}//while
(*fun)(Node);//訪問該節點(左子樹為空的節點)
Node=Node->rchlid;//轉向其右子樹
while(!StackIsEmpty(&S)&&!Node)//如果棧非空且右子樹為空,彈出並退{//回棧頂節點,訪問之,一直到右子樹非空的節點
Pop(&S,&Node);
(*fun)(Node);//訪問之
Node=Node->rchlid;//轉向其右子樹(出棧節點的左子樹必然已被遍歷）
}//while
}//while
DestroyStack(&S);
returntrue;
}//InOrderTraverse
第二題：
第一個while是把棧S的中的元素臨時轉移到棧T中，直到遇到等於e的(e出棧S但沒有進棧T）。
第二個while是把棧T中的元素全部放回棧S中。
結果是：刪除了S棧中<離棧頂最近,值為e>的元素。
第三題：stack
第四題：
前序串的K應該是D。
樹的構型：
A
/
BF
/\
ECG
/
DHJ
I
後序序列：EDCBIHJGFA
根據後序序列易得線索：
E:lchild=NULLright=&D
C:lchild=&D
D:lchild=&Eright=&C
F:lchild=&G
H:lchild=&I
I:lchild=&Bright=&H
J:lchild=&Hright=&G
⑻ 建立二叉樹，實現前序遍歷的非遞歸演算法及遞歸演算法<有追加>
找本數據結構書，自己看去。
/////////////////////////////////
地球人都知道遍歷二叉樹不用遞歸就只能用棧了
另：
hope1262你說的那個是堆，數組存儲二叉樹，他的這個明顯不是
////////////////////////////////
遞歸在編譯器實現的時候也是用堆棧實現的。遞歸的時候是從上向下的，而由於堆棧是先進後出，所以壓棧的時候要先壓後面的結點。
一棵樹分為左子樹、根和右子樹，所以先把右子樹壓入棧，輸出根，然後再壓入左子樹，壓左子樹時又重復這一過程了，直左子樹為空；這時開始從棧中把之前壓入的右子樹pop出來，再重復上面的過程，直到棧為空。
代碼：
void PreOrder(BiTNode *BT)
{
push(BT);
while(!IsEmpty)
{
pop(BT);
while(BT)
{
VISIT(BT);
push(BT->rchild);
BT=BT->lchild;
}
}
}
你的代碼自己改吧，記得先把根壓進棧。
⑼ 二叉排序樹的問題
二叉樹遍歷遞歸演算法：
#include<iostream>
#include<vector>
using namespace std;
struct bitree{
char data;
bitree *lchild;
bitree *rchild;
} ;
void create(bitree *&root){
char ch;
cin>>ch;
if(ch=='#') root=NULL;
else {
root=new bitree;
root->data=ch;
create(root->lchild );
create(root->rchild );
}
}
void preorder(bitree* root)
{ if(root==NULL) return;
else{
cout<<root->data;
preorder(root->lchild);
preorder(root->rchild); }
}
int main(int argc, char* argv[])
{ bitree *root;
create(root);
preorder(root);
}
二叉樹遍歷非遞歸演算法：
#include<iostream>
#include<vector>
using namespace std;
struct bitree{
char data;
bitree *lchild;
bitree *rchild;
} ;
struct element{
bitree *ptr;
int flag;
};
void create(bitree *&root){
char ch;
cin>>ch;
if(ch=='#') root=NULL;
else {
root=new bitree;
root->data=ch;
create(root->lchild );
create(root->rchild );
}
}
int main(int argc, char* argv[])
{
bitree *routine,*root;
create(routine);
root=routine;
vector <bitree*> a;
//char ch;
cout<<"前序遍歷結果：";
while(!a.empty()||root!=NULL)
{ while(root!=NULL)
{ cout<<root->data ;
a.push_back(root);
root=root->lchild;
}
if(!a.empty())
{ root=a.back();
a.pop_back();
root=root->rchild ; }
}
cout<<endl;
cout<<"中序遍歷結果：";
root=routine;
while(!a.empty()||root!=NULL)
{ while(root!=NULL)
{ a.push_back(root);
root=root->lchild;
}
if(!a.empty())
{ root=a.back();
cout<<root->data ;
a.pop_back();
root=root->rchild ; }
}
cout<<endl;
cout<<"層序遍歷結果: ";
root=routine;
vector<bitree*> c;
if(root==NULL) return 1;
c.push_back(root);
unsigned int count=0;
while(count<c.size())
{
cout<<c[count]->data;
if(c[count]->lchild!=NULL) c.push_back(c[count]->lchild);
if(c[count]->rchild!=NULL) c.push_back(c[count]->rchild);
++count;
}
cout<<endl;
cout<<"後序遍歷結果：";
root=routine;
vector <element>b;
while(!b.empty()||root!=NULL)
{ while(root!=NULL)
{ element etree;
etree.ptr=root;
etree.flag=1;
b.push_back(etree);
root=root->lchild;
}
while(!b.empty()&&b.back().flag==2) {
root=b.back().ptr ;
b.pop_back() ;
cout<<root->data ;
if(root==routine) return 1;
}
if(!b.empty())
{ b.back().flag=2;
root=b.back().ptr->rchild ;
}
}
}
求二叉樹的深度：
#include<iostream>
#include<vector>
using namespace std;
struct bitree{
char data;
bitree *lchild;
bitree *rchild;
} ;
void create(bitree *&root){
char ch;
cin>>ch;
if(ch=='#') root=NULL;
else {
root=new bitree;
root->data=ch;
create(root->lchild );
create(root->rchild );
}
}
int main(int argc, char* argv[])
{
bitree *root;
create(root);
cout<<"層序編歷結果：";
vector<int> n;
vector<int>b(5,0);
vector<bitree*> c;
if(root==NULL) return 1;
c.push_back(root);
unsigned int count=0;
while(count<c.size())
{ int num=0;
cout<<c[count]->data;
if(c[count]->lchild!=NULL) {c.push_back(c[count]->lchild); ++num; }
if(c[count]->rchild!=NULL) {c.push_back(c[count]->rchild); ++num; }
++count;
n.push_back(num);
}
cout<<endl;
for(int i=0;i<n.size();++i)
cout<<n[i]<<" ";
int total=1;
b[0]=n[0] ;
for(int r=1,i=1;r<n.size();++i){
int ti=0;
for(int k=r;k<=b[i-1]+r-1;++k){
b[i]=b[i]+n[k];
++ti; }
++total;
r=r+ti; }
cout<<endl<<"二叉樹的深度是：";
cout<<total;
}
以上的代碼是個人編寫的
QQ：547758555
歡迎訪問我的blog:
http://blog.sina.com.cn/u/1254793361
⑽ 跪求！！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;
}
要想完全把握以上程序你必須對隊列的結構有很好的理解。此外，需要說明的是，計數器是以出隊元素個數為指標進行計數的，而非進隊元素。這樣可使程序簡潔和容易理解得多。