二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。
//层次遍历代码
template
void BinTree::view()
{
if (IsNull()) return;
deque*> q;
TreeNode* temp;
q.push_back(root);
while(!q.empty())
{
temp = q.front();
q.pop_front();
coutdata;
if (temp->Left!=NULL)
q.push_back(temp->Left);
if (temp->Right!=NULL)
q.push_back(temp->Right);
}
cout<<endl;
}
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 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
问题来自《数据结构》(严蔚敏、吴伟民著,C语言描述,清华大学出版社,1997年4月第1版),第6章树与二叉树,6.3遍历二叉树和线索二叉树。
遍历二叉树的非递归算法,教材的描述如下(见130页):
仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。例如,从中序遍历递归算法执行过程中递归工作栈的状态可见:(1)工作记录中包含两项,其一是递归调用的语句编号,其二是指向根结点的指针,则当栈顶记录中的指针非空时,应遍历左子树,即指向左子树根的指针进栈;(2)若栈顶记录中的指针值为空,则应退至上一层,若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点;(3)若是从右子树返回,则表明当前曾的遍历结束,应继续退栈。从另一角度看,这意味着遍历右子树时不再需要保存当前层的根指针,可直接修改栈顶记录中的指针即可。由此可得两个中序遍历二叉树的非递归算法如下:
=============================================================
算法一:
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//采用二叉链表存储结构,Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit。
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(s))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)) //访问结点,向右一步
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse 算法一
============================================================
============================================================
算法二:
Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e))
{
//采用二叉链表存储结构,Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit。
InitStack(S);
p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}//if 根指针进栈,遍历左子树
else
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
p=p->rchild;
}//else 根指针退栈,访问根结点,遍历右子树
}//while
}InOrderTraverse() 算法二
============================================================
我的问题是,文字描述中提到的“从中序遍历递归算法执行过程中递归工作栈的状态可见:……”的这一部分。我不明白什么是“栈顶记录中的指针”,什么是“工作记录”。不明白第(2)句话中,先说“栈顶记录中的指针值为空”的时候怎么怎么样,后面为什么又会有对“栈顶记录中指针所指的根结点”的访问?这不是前后矛盾的吗?在读完后面的代码并作了认真的分析之后,仍不明白这一段话到底描述了一个什么样的过程,不理解转化成非递归过程的具体实现。请达人指教。
问题补充:参考:
对代码中与栈有关的函数的说明:
InitStack(&S) 构造一个空栈S;
Push(&S,e) 栈已存在时,插入元素e为新的栈顶元素;
StackEmpty(S) 栈已存在时,若为空栈返回TRUE,否则返回FALSE;
GetTop(S,&e) 栈已存在且非空时,用e返回S的栈顶元素;
Pop(&S,&e) 栈S存在且非空时,删除栈顶元素,并用e返回其值;
——摘自该书45页。
中序遍历二叉树的操作递归定义:
若二叉树为空,则空操作;
否则
(1) 中序遍历左子树;
(2) 访问根结点;
(3) 中序遍历右叉树;
——摘自该书128页。
递归过程转为非递归过程的实质:
将原由系统管理的递归工作栈改为由程序员管理。在非递归过程中,递归工作栈同样起着两个作用:其一是将递归调用室的实在参数和返回地址传递给下一层递归;其二是保存本层参数和局部变量,以便从下一层返回本层时继续恢复使用。如果将栈的每一层视为一项待处理的事务,则栈顶记录则是当前急待处理的事务。
——摘自《数据结构》PASCAL语言描述,严蔚敏、吴伟民著,清华大学出版社。
//利用栈将二叉树递归算法转化为非递归算法
#define struct_sizes 20
#define adds 10
typedef struct bitnode//二叉树的定义
{
int data;//二叉树元素数据类型
struct bitnode *lchild,*rchild;//左右孩子
}*bitree;
typedef struct
//顺序栈的定义
{
bitree *base;//栈底指针
bitree *top;//栈顶指针
int stacksize;
}sqstack;
int initstack(sqstack &S)//新建一个空栈
{
S.base=(bitree *)malloc(struct_sizes*sizeof(bitree));
if(!S.base)return 0;
S.top = S.base;
S.stacksize = struct_sizes;
return 1;
}//initstack
int stackempty(sqstack S)
//判断栈是否为空
{
if(S.base==S.top)return 1;
else return 0;
}
int push(sqstack &S,bitree e)//进栈
{
if(S.top - S.base >= S.stacksize)//栈满重新分配空间
{
S.base = (bitree *)realloc(S.base,(S.stacksize + adds) * sizeof (bitree));
if(!S.base)return 0;
S.top = S.base + S.stacksize;
S.stacksize += adds;
}
*(S.top++)=e;
return 1;
}//push
int pop(sqstack &S,bitree &e)//出栈
{
if(S.top == S.base)return 0;
e = * --S.top;
return 1;
}//pop
int gettop(sqstack S,bitree &e)//取栈顶元素
{
if(S.top == S.base) return 0;
e = *(S.top - 1);
return 1;
}//gettop
int mid_travel(bitree T)//递归二叉树中序遍历
{
if(!T)return 0;
else
{
if(T->lchild)mid_travel(T->lchild);
printf(" %d",T->data);
if(T->rchild)mid_travel(T->rchild);
}
return 1;
}
int mid_norecursion(bitree T)
//中序遍历二叉树T的非递归算法,打印每个数据
{
sqstack S;
bitree p;
if(!T)return 0;
initstack(S);push(S,T);//根指针进栈
while(!stackempty(S))
{
while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头
pop(S,p); //空指针退栈
if(!stackempty(S))//访问结点,向右一步
{
pop(S,p);printf(" %d",p->data);
push(S,p->rchild);
}
}
return 1;
}
参考资料:http://zhidao.baidu.com/question/16519850.html
文件 main.cpp 代码如下:
#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
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树:
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树:
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么?
二叉树有两种存储结构:顺序存储和链式存储
顺序存储: (对完全二叉树来说,可以充分利用存储空间,但对于一般的二叉树,只有少数的存储单元被利用)
[cpp] view plaincopy
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储:
[csharp] view plaincopy
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
二叉树三种递归的遍历方法:
先序遍历 访问根节点→先序遍历左子树→先序遍历右子树
中序遍历 中序遍历左子树→访问根节点→中序遍历右子树
后序遍历 后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法:
[cpp] view plaincopy
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法:
有两种方法:①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历:
[cpp] view plaincopy
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历:
[cpp] view plaincopy
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历:
[cpp] view plaincopy
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法:(用队列的方法)
[cpp] view plaincopy
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
已知先序和中序求后序的算法:(已知后序和中序求先序的算法类似,但已知先序和后序无法求出中序)
[cpp] view plaincopy
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序,pre_s为先序的起始位置,pre_e为先序的终止位置。 */
/* 其中in[]表示中序,in_s为中序的起始位置,in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s~pre_e]、in[in_s~in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子树,完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
c=pre[pre_s]; /* c储存根节点。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c); /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}
// 二叉树的建立和遍历算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char TElemtype;
typedef struct Tnode
{
TElemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*BTree;
void createTree(BTree &T);//创建一颗二叉树
void preorder(BTree T);//二叉树的递归先序遍历
void inorder(BTree T);//二叉树的递归中序遍历
void postorder(BTree T);//二叉树的递归后序遍历
void levelorder(BTree T);//二叉树的非递归层次遍历
int main( )
{
BTree T;
printf("请输入先序数据,创建二叉树,@为空\n");
createTree(T);
printf("the preorder is :\n");
preorder(T);
printf("\n");
printf("the inorder is :\n");
inorder(T);
printf("\n");
printf("the postorder is :\n");
postorder(T);
printf("\n");
printf("the levelorder is :\n");
levelorder(T);
printf("\n");
return 0;
}
void createTree(BTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='@')
T=NULL;
else
{
T=(Tnode*)malloc(sizeof(Tnode));
if(!T)
exit (0);
T->data=ch;
createTree(T->lchild );
createTree(T->rchild );
}
}//creatTree
void preorder(BTree T)
{
if(T)
{
printf("%c",T->data );
preorder(T->lchild);
preorder(T->rchild );
}
}//preorder
void inorder(BTree T)
{
if(T)
{
inorder(T->lchild );
printf("%c",T->data );
inorder(T->rchild );
}
}//inorder
void postorder(BTree T)
{
if(T)
{
postorder(T->lchild );
postorder(T->rchild );
printf("%c",T->data );
}
}//postorder
void levelorder(BTree T)
{
int x=0,y=0;
BTree p,Q[100];
if(T)
{
y++;
Q[y]=T;
}
while(x!=y)
{
x++;
p=Q[x];//访问P节点
printf("%c",p->data );
if(p->lchild )//p节点的左右孩子进队列
{
y++;
Q[y]=p->lchild ;
}
if(p->rchild )
{
y++;
Q[y]=p->rchild ;
}
}
}//levelorder
怎么写二叉树的先序遍历、中序遍历、后序遍历?
后序遍历 左子树 2、后序遍历右子树 3、访问根节点 下面介绍一下例子与方法:1、画树求法:第一步,根据前序遍历的特点,我们知道 根结点 为G 第二步,观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。第三步,观察左子树ADEF,左子树的中...
二叉树前序中序后序的概念是什么?
根据二叉树的前序序列和中序序列可以画出这个二叉树,然后再根据画出的二叉树进行后序排列即可,没有办法只管从两组序列里直接得出。有序树:树中任意节点的 子结点之间有顺序关系,这种树称为有序树。无序树:树中任意节点的 子结点之间没有顺序关系,这种树称为无序树,也称为自由树。二叉树、...
根据先序和中序序列生成二叉树
在二叉树中,有三种主要的遍历方式(假设父节点为N,左孩子为L,右孩子为R):先序遍历:N -> L -> R 中序遍历:L -> N -> R 后序遍历:L -> R -> N 假设现有一颗二叉树如上图所示,上述二叉树的先序遍历和中序遍历结果为:先序遍历:ABCDEF 中序遍历:CBDAEF 分析: 先序遍历...
任何一棵二叉树的叶结点在前序、中序、后序序列中的相对次序( )。
【答案】:A 任何一颗二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序是不发生改变的,因为根据三个遍历的次序和特点:前序是根左右、中序是左根右、后序是左右根,因此相对次序发生变化的都是子树的根,也就是分支结点。
为什么二叉树的前序遍历和中序遍历对应入栈和出栈次序
前序遍历是按照根左右的顺序访问的。假设首先进栈的节点是p,前序序列是访问该节点p以后该结点p进栈,然后去访问p的左子树,访问p的左子树的时候,也是先访问左子树根节点即p的左孩子,然后根节点入栈。先一路从根压到最左边的结点,左子树都处理完了,才开始访问右子树。中序遍历是按照左根右的...
在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序...
首先将根结点入队,然后不断进行如下操作:从队列中出队一个结点,访问它,将其左右子节点入队。直到队列为空,表示所有结点都被遍历完成。3、深度遍历:深度遍历是一种沿着树的深度方向自上而下、自左而右进行遍历的方式。它通常使用栈或递归来实现。深度遍历可以细分为前序深度遍历、中序深度遍历和后...
在一棵二叉树先序遍历、中序遍历、后序遍历所产生序列中,所有叶子结 ...
【答案】:B 本题算法与数据结构基本知识。遍历就是按照某条路径访问树中每个结点,使每个结点被访问仅且一次。(1)先序遍历(D L R):访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历(L D R):中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历(L R D):后序...
C++中二叉树的前序(后序、中序)遍历分别是什么意思?相应的树图怎么看...
二叉树的遍历是指按照一定次序访问树中所有结点,并且每个节点仅被访问一次的过程。1、先序遍历(前序)(1)访问根节点;(2)先序遍历左子树;(3)先序遍历右子树。2、中序遍历 (1)中序遍历左子树;(2)访问根节点;(3)中序遍历右子树。3、后序遍历 (1)后序遍历左子树;(2)后序...
设二叉树的前序序列为ABCDEF,中序序列为BDFECA ,则该二叉树的后序序列...
此类题目由前序、中序依次分析 由前序可知 此二叉树根节点为A 则由中序序列知 BCDEF 为左子树 注意:由前序确定根节点及父节点,由中序序列确定左右子树!!!此时二叉树为 再将 BCDEF 作为新序列分析,此时由前序知父(根)节点为B 由中序知 DFEC 为右子树 此时二叉树为 继续再将 CDEF...
已知二叉树的中序序列,后序序列,怎么求前序序列
确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点左边和右边都为空,则根节点已经为叶子节点。递归求解树。将左子树和右...
梁废拨云: #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 ...
南昌县13288095931: 求二叉树的遍历算法 - ?
梁废拨云: 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...
南昌县13288095931: .二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现. - ?
梁废拨云: #include using namespace std;//二叉树链式存储的头文件 typedef char datatype;//结点属性值类型 typedef struct node // 二叉树结点类型 { datatype data; struct node* lchild,*rchild; }bintnode; typedef bintnode *bintree; bintree root;//指向二叉树...
南昌县13288095931: 二叉树的中序、前序、后序的递归、非递归遍历算法,应包含建树的实现 - ?
梁废拨云: #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",...
南昌县13288095931: 设计一个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 // 清空二...
南昌县13288095931: 建立一棵二叉树,要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历. - ?
梁废拨云: 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码.Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf("%d ",T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...
南昌县13288095931: 二叉数的前序、中序、后续三种方式的递归与非递归的算法. - ?
梁废拨云: 小哥分这么少=============tree.cpp=============#include<iostream>#include<queue>#include<stack>#include<fstream> using namespace std;#include"tree.h"//构造二叉树 template<class T> bool bitree<T>::insert(const T& e) { btnode<T...
南昌县13288095931: C语言版数据结构 如何理解二叉树的前、中、后序的递归和非递归遍历?? - ?
梁废拨云: 就我看来递归遍历是很容易理解的,除非你不懂C语言递归,难理解的也就是后序非递归遍历.分2步,1、理解前中后遍历流程;2、看算法,回味遍历流程.
南昌县13288095931: 二叉树前序遍历与中序遍历非递归程序思路怎么是一样的? - ?
梁废拨云: 大体思路差不多,但节点访问位置不一样, 先序的话,是先访问,然后节点压栈,移到左子树,至节点空退栈,移到右子树. 而中序的话,是先节点压栈,移到左子树,至节点空退栈,访问节点,然后移到右子树另外,所谓前序、中序、后序遍历,全称是前根序遍历,中根序遍历,后根序遍历,不管哪种遍历,访问左子树 一定在 访问右子树之前,不同的就是根的访问时机.所以三种递归/或非递归,程序思路都是一样的.
南昌县13288095931: 二叉树遍历,递归与非递归,前序中序后序遍历,C代码 - ?
梁废拨云: #include<stdio.h> #include<stdlib.h> typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }bitnode,*bitree;//二叉树节点类型和节点指针类型 bitree create()//先序创建 { bitree root=NULL; char c; scanf("%c",&c); fflush(stdin); if(c=='#')...