中序遍歷的非遞歸演算法

A. 一個數據結構問題如圖，在中序遍歷二叉樹非遞歸演算法中，圖中我標記的Bitree p，這個p什麼意思

p是Bitree型變數，查一下typedefine 語句，有關於Bitree的定義，從下面引用p->看，應該是指針型的，但是有一個專門名稱。

B. 中序遍歷樹的非遞歸演算法的空間復雜度是多少

因為都是要遍歷每一個節點，所以時空復雜度是一樣的。
時間復雜度O(n);
空間復雜度O(n)；
（n為節點數）

C. 用c語言編程實現二叉樹的中序遍歷演算法

#include<stdio.h>
#include<stdlib.h>
struct BiTNode *stack[100];
struct BiTNode//定義結構體
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序創建樹
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //前序遍歷（輸出二叉樹）
{
int i=-1;
while(1)
{
while(p!=NULL)
{
stack[++i]=p->rchild;/*printf("ok？\n");*/
printf("%c",p->data);
p=p->lchild;
}
if(i!=-1)
{
p=stack[i];
i--;
}
else
return;
}
}
void main()//主函數
{
struct BiTNode *p,*t;
later(p);
print(p);
}

D. 二叉樹的中序、前序、後序的遞歸、非遞歸遍歷演算法，應包含建樹的實現

#include "stdlib.h"
#include "iostream"
using namespace std;
#define ok 1
#define null 0
typedef char telemtype;
typedef struct bitnode
{telemtype data;<br> struct bitnode *lchild,*rchild;<br> }bitnode,*bitree;/* void visit(bitnode *p)
{printf("%c",p->data);<br> }*/
//先序建樹
bitree createbitree(void)
{char ch;bitnode *t;<br> scanf("%c",&ch);<br> if(ch=='#')<br> t=null;<br> else<br> {t=(bitnode *)malloc(sizeof(bitnode));<br> t->data=ch;<br> t->lchild=createbitree();<br> t->rchild=createbitree();<br> } return t;
}
//中序遞歸遍歷
void inorder(bitree T){
if(T)
{inorder(T->lchild);<br> printf("%c",T->data);<br> inorder(T->rchild);}
} //先序遞歸遍歷
void preorder(bitree T)
{if(T)<br> {<br> printf("%c",T->data);<br> preorder(T->lchild);<br> preorder(T->rchild);<br>}
}//後序遞歸遍歷
void Post_order(bitree T)
{if(T)<br> {<br> Post_order(T->lchild);<br> Post_order(T->rchild);<br> printf("%c",T->data);<br>}
}//先序非遞歸遍歷二叉樹
void PreTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{
cout<<p->data<<" ";
node[top]=p;
top++;
p=p->lchild; }
if(top>0){top--;p=node[top];p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}//中序非遞歸遍歷二叉樹
void InTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{

node[top]=p;
top++;
p=p->lchild; }
if(top>0){
cout<<p->data<<" ";
top--;p=node[top];
p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}//後序非遞歸遍歷二叉樹
void PostTree(bitree T)
{
bitree p,node[20];
int top=0;
p=T;
do
{
while(p!=NULL)
{
cout<<p->data<<" ";
node[top]=p;
top++;
p=p->lchild; }
if(top>0){top--;p=node[top];p=p->rchild;}
}while(top>0||p!=NULL);
cout<<endl;}void leaf(bitree T,int &count)
{
if(T)
{
if(T->lchild==NULL&&T->rchild==NULL)
count++;
else
{
leaf(T->lchild,count);
leaf(T->rchild,count);
}
}}
int deepth(bitree T)
{
int leftdep,rightdep;
if(!T)
return 0;
else
{
leftdep=deepth(T->lchild);
rightdep=deepth(T->rchild);
if(leftdep>rightdep)
return leftdep+1;
else
return rightdep+1;
}

}
void level_order(bitree T)
{}
//輸出菜單
void print_menu(){
cout<<"請選擇你要進行的操作："<<endl;
cout<<"1.先序建立二叉樹! "<<" "<<"2.中序遞歸遍歷二叉樹!"<<endl;
cout<<"3.先序遞歸遍歷二叉樹!"<<" "<<"4.後序遞歸遍歷二叉樹!"<<endl;
cout<<"5.先序非遞歸遍歷二叉樹!"<<" "<<"6.中序非遞歸遍歷二叉樹!"<<endl;
cout<<"7.後序非遞歸遍歷二叉樹!"<<" "<<"8.求葉子結點個數!"<<endl;
cout<<"9.求樹的深度! "<<" "<<"10.層序遍歷二叉樹!"<<endl;
cout<<"11.退出!"<<endl;
}
void main()
{
bitree t;
int k,c=0,d;
print_menu();
cin>>k;
while(k!=11)
{

switch(k)
{
case 1:
cout<<"請輸入樹的先序字元序列，空樹以#表示"<<endl;
t=createbitree();
cout<<"建樹成功"<<endl;
break;
case 2:
inorder(t);
break;
case 3:
preorder(t);
break;
case 4:
Post_order(t);
break;
case 5:
PreTree(t);
break;
case 6:
InTree(t);
break;
case 7:
PostTree(t);
break;
case 8:
leaf(t,c);
cout<<"葉子結點數為："<<c<<endl;
break;
case 9:
d=deepth(t);
cout<<"樹的深度為："<<d<<endl;
break;
case 10:
level_order(t);
break;
case 11:
exit(0);
default:
cout<<"不存在您選擇的項，請重新輸入："<<endl;
} //switch
print_menu();
cin>>k;
}//while
}//main

E. 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
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

F. 計算機中中序遍歷不懂，求解

可以看一下下面的解釋：

按照二叉樹中序遍歷的定義，無論是訪問整棵樹還是其子樹，均應該遵循先訪問根結點的左子樹，然後訪問根結點，最後訪問根結點的右子樹的規律。因此對於一棵
樹t，如果t非空，首先應該進入t的左子樹訪問，此時由於t的根結點及右子樹尚未訪問，因此必須將t保存起來，放入棧中，以便訪問完其左子樹後從棧中取出
t，進行其根結點及右子樹的訪問，在整個二叉樹中序遍歷的過程中，程序要做的工作始終分為兩個部分：當前正在處理的樹（子樹）和保存在棧中待處理的部分
（註：當棧中元素位於棧頂即將出棧時，意味著其左子樹已訪問完，出棧後應該立即訪問其根結點，再進入其右子樹的訪問），只有這兩部分的工作均完成後，程序
方能結束。根據以上分析，得到二叉樹中序遍歷的非遞歸演算法，在演算法實現時，用了鏈式存儲結構。

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

推薦這篇文章，把二叉樹的前序、中序和後續的遞歸和非遞歸演算法都講了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html

H. c語言實現二叉樹的先序,中序,後序的遞歸和非遞歸演算法和層次遍歷演算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 標准輸入輸出頭文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 數學函數頭文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉樹和銷毀二叉樹的操作一樣

typedef struct BiTNode
{
int data; // 結點的值
BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;

int Nil=0; // 設整型以0為空
void visit(int e)
{ printf("%d ",e); // 以整型格式輸出
}
void InitBiTree(BiTree &T)
{ // 操作結果：構造空二叉樹T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 演算法6.4：按先序次序輸入二叉樹中結點的值(可為字元型或整型，在主程中定義)，
// 構造二叉鏈表表示的二叉樹T。變數Nil表示空(子)樹。修改
int number;
scanf("%d",&number); // 輸入結點的值
if(number==Nil) // 結點的值為空
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是對結點操作的應用函數。修改演算法6.1
// 操作結果：先序遞歸遍歷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()
{
BiTree T;
InitBiTree(T); // 初始化二叉樹T
printf("按先序次序輸入二叉樹中結點的值,輸入0表示節點為空，輸入範例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉樹T
printf("先序遞歸遍歷二叉樹：\n");
PreOrderTraverse(T,visit); // 先序遞歸遍歷二叉樹T
printf("\n中序遞歸遍歷二叉樹：\n");
InOrderTraverse(T,visit); // 中序遞歸遍歷二叉樹T
printf("\n後序遞歸遍歷二叉樹：\n");
PostOrderTraverse(T,visit); // 後序遞歸遍歷二叉樹T
}

I. 以二叉鏈表為存儲結構，分別寫出前序、中序、後序遍歷二叉樹的遞歸與非遞歸演算法。（數據結構）

#include<iostream.h>
#include<stdlib.h>

typedef char ElemType;

struct BTreeNode
{
ElemType data;
BTreeNode*left;
BTreeNode*right;
};

void InitBTree(BTreeNode*& BT)
{
BT=NULL;
}
void CreateBTree(BTreeNode*& BT,char*a)
{
const int MaxSize=1000;
BTreeNode*s[MaxSize];
int top=-1;
BT=NULL;
BTreeNode*p;
int k;
int i=0;
while (a[i])
{
switch(a[i])
{
case ' ':
break;
case'(':
if(top==MaxSize-1)
{
cout<<"棧空間太少，請增加MaxSize的值！"<<endl;
exit(1);
}
top++; s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
cout<<"二叉樹的廣義表出錯!"<<endl; exit(1);
}
top--;
break;
case ',':
k=2;
break;
default:
p=new BTreeNode;
p->data=a[i];p->left=p->right=NULL;
if(BT==NULL) BT=p;
else
{
if(k==1) s[top]->left=p;
else s[top]->right=p;
}
}
i++;
}
}
bool EmptyBTree (BTreeNode*BT)
{
return BT==NULL;
}
void PreOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
cout<<BT->data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);

}
}
void InOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
cout<<BT->data<<' ';
InOrder(BT->right);
}
}
void PostOrder(BTreeNode* BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
cout<<BT->data<<' ';
}
}
void LevelOrder(BTreeNode* BT)
{
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while (front!=rear)
{
front=(front+1)%MaxSize;
p=q[front];
cout<<p->data<<' ';
if(p->left!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL)
{
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
}
void PrintBTree(BTreeNode*BT)
{
if(BT!=NULL)
{
cout<<BT->data;
if(BT->left!=NULL || BT->right!=NULL )
{
cout<<'(';
PrintBTree(BT->left);
if(BT->right!=NULL)
cout<<',';
PrintBTree(BT->right);
cout<<')';
}
}
}
void ClearBTree(BTreeNode*&BT)
{
if(BT!=NULL)
{
ClearBTree(BT->left);
ClearBTree(BT->right);
delete BT;
BT=NULL;
}
}

void main()
{
BTreeNode* bt;
InitBTree(bt);
char b[50];
cout<<"輸入二叉樹的廣義表字元串"<<endl;
cin.getline(b,sizeof(b));
CreateBTree(bt,b);
PrintBTree(bt); cout<<endl;
cout<<"前序："; PreOrder(bt);cout<<endl;
cout<<"中序："; InOrder(bt); cout<<endl;
cout<<"後序: "; PostOrder(bt); cout<<endl;
cout<<"按層："; LevelOrder(bt); cout<<endl;

}

J. 數據結構書上一道 中序遍歷二叉樹T的非遞歸演算法有些地方不明白 望能解答下

問題1：上面是個循環語句，但不是把棧頂的元素始終賦給p，而是取棧頂元素p，並將p的左子樹進站
問題2：這個訪問的是哪個結點的數據啊？
棧頂元素，
問題3：此時p不是已經賦給出棧的那個元素了嗎 為什麼還能p-->rchild
訪問完p後，去遍歷p的右子樹p->rchild