中序遍历的非递归算法

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