⑴ 二叉树的非递归遍历
#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;
}
要想完全把握以上程序你必须对队列的结构有很好的理解。此外，需要说明的是，计数器是以出队元素个数为指标进行计数的，而非进队元素。这样可使程序简洁和容易理解得多。