二叉树先序非递归遍历C语言算法
在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(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;
}
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序,中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n<=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head->data=*pre;
head->lchild=head->rchild=null;
ordsit=0;
while(ord[ordsit]!=*pre)
{
ordsit++;
}
head->lchild=create(pre+1,ord,ordsit);
head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head->lchild );
printf("%c",head->data );
inorder(head->rchild );
}
}
//中序非递归遍历
void inorder1(struct node *head)
{
struct node *p;
struct node *stack[20];
int top=0;
p=head;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
printf("%c ",p->data );
p=p->rchild ;
}
}
//主函数
int main()
{
struct node * head;
char pre[30],ord[30];
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("
");
inorder1(head);
printf("
");
}
//测试事例;
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写,原版
vc++ 6.0实验通过
怎么样,老板,第一次上百度知道,好激动
给点面子
给分!给分啊
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值(一个字符),空格字符表示空树,
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}
#include<stdio.h>
#include<stdlib.h>
#define MS 10
struct BTreeNode
{
char data;
struct BTreeNode * left;
struct BTreeNode * right;
};
void InitBTree(struct BTreeNode * * BT)
{
* BT=NULL;
}
void CreatBTree(struct BTreeNode * * BT,char * a)
{
struct BTreeNode * p;
struct BTreeNode * s[MS];
int top=-1;
int k;
int i=0;
* BT=NULL;
while(a[i])
{
switch(a[i])
{
case ' ':break;
case '(':
if(top==MS-1)
{
printf("栈空间太小,需增加MS的值!\n");
exit(1);
}
top++;s[top]=p;k=1;
break;
case ')':
if(top==-1)
{
printf("二叉树广义表字符串有错!\n");
exit(1);
}
top--;break;
case ',' : k=2;break;
default :
if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z'))
{
p=malloc(sizeof(struct 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;
}
}
else {printf("二叉树广义表字符串有错!\n");exit(1);}
}
i++;
}
}
void Preorder(struct BTreeNode * BT)
{
struct BTreeNode * s[10];
int top=-1;
struct BTreeNode * p=BT;
while(top!=-1||p!=NULL)
{
while(p!=NULL)
{
top++;
s[top]=p;
printf("%c",p->data);
p=p->left;
}
if(top!=-1)
{
p=s[top];
top--;
p=p->right;
}
}
}
void main()
{
struct BTreeNode * p;
char * a="A(B(C),D(E(F,G),H(,I)))";
InitBTree(&p);
CreatBTree(&p,a);
printf("结点的访问序列为:\n");
Preorder(p);printf("\n");
}
#define LEN sizeof(struct tree)
#define NULL 0
#include<stdio.h>
#include<malloc.h>
struct tree
{
char data;
struct tree *lchild,*rchild;
};
//创建二叉树
struct tree *creat()
{
char c;
struct tree *t;
c=getchar();
if(c==' ')
t=NULL;
else
{
t=(struct tree*)malloc(LEN);
t->data=c;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
//前序遍历
void Preprint(struct tree*t)
{
if(t!=NULL)
{
printf("%c->",t->data);
Preprint(t->lchild);
Preprint(t->rchild);
}
}
//中序遍历
void Inprint(struct tree*t)
{
if(t!=NULL)
{
Inprint(t->lchild);
printf("%c->",t->data);
Inprint(t->rchild);
}
}
//后序遍历
void Postprint(struct tree*t)
{
if(t!=NULL)
{
Postprint(t->lchild);
Postprint(t->rchild);
printf("%c->",t->data);
}
}
main()
{
struct tree *t;
printf("Please input tree in order:\n");
t=creat();
printf("The result of Preorder traversal is\n");
Preprint(t);
printf("^\nThe result of Inorder traversal is\n");
Inprint(t);
printf("^\nThe result of Postorder traversal is\n");
Postprint(t);
printf("^\n");
getch();
}
先序遍历和后序遍历是什么
2、首先访问根结点然后遍历左子树,最后遍历右子树,在遍历左、右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树;3、也称先根遍历、前序遍历。二、后序遍历 1、后序遍历是二叉树遍历的一种,有递归算法和非递归算法两种。在二叉树中,先左后右再根;2、后序遍历首先遍历左子树,然后...
非递归的二叉树前序遍历算法有什么用途
2.1 递归算法会有更多的资源需要压栈和出栈操作(不仅仅是参数,还有函数地址等)2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效 3. 使用循环代替递归算法,通常可以获得更好的执行效率和空间效率,在二叉树层次较深的情况下,采用非递归方式遍历能够有效的提升遍历的性能。
程序改错:非递归先序遍历二叉树
printf("%c\\t",p->data);\/\/它的左子树访问完了,输出自身(中序嘛)p=p->rchild;\/\/开始访问右子树 } \/\/\/如果有右孩子,就以它为树根,重新循环 \/\/\/如果没有右孩子,且栈空(达到了下面一行的退出条件),说明树遍历完成,不能在进入if语句 }while(top>0||p!=null);\/\/--- \/\/---...
二叉树先序非递归遍历C语言算法
\/*---非递归---先序建立二叉树---*\/ bitree *createprebitree(){char ch;bitree *ht,*p,*q;sqstack *s;s=malloc(sizeof(bitree)); \/\/加上这一句为s 初始化开辟空间 ch=getchar();if(ch!='#'&&ch!='\\n') \/* 输入二叉树先序顺序 是以完全二叉树的先序顺序 不是...
C语言中,递归先序遍历和非递归先序遍历的有何区别?各自优缺点?_百度...
BiTNode));T->data=p;T->lchild=CreateBiTree(T->lchild);T->rchild=CreateBiTree(T->rchild);} return (T);} void PreOrder(BiTree T)\/\/先序 { if(T!=NULL){ printf("%c",T->data);PreOrder(T->lchild);PreOrder(T->rchild);} } void LevelOrder(BiTree T)\/\/层次遍历 ...
【图解】数据结构代码领背-二叉树的后序遍历(递归法、非递归法)
非递归法则采用栈实现。以相同例题,步骤如下:1. 先将1, 2, 4入栈,(4, 2, 1)。2. 读取栈顶4,无右子树,访问并出栈。3. 再读取2,有未访问的右子树5,入栈。(5, 2, 1)。4. 检查5无左子树,访问后出栈。5. 重复以上过程,直至栈为空且所有节点访问完毕。总结来说,后序遍历...
二叉树的遍历非递归算法中应注意哪些问题
先序非递归算法 【思路】假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针?方法1:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶...
...层次序的非递归遍历算法的实现,应包含建树的实现。
createbintree(&(*t)->rchild);\/\/递归实现右孩子的建立 } } \/\/二叉树前序遍历递归实现 void preorder(bintree t)\/\/t是指针变量,而不是结点结构体变量 {if(t){ cout<<t->data<<" ";preorder(t->lchild);preorder(t->rchild);} } \/\/二叉树前序遍历非递归实现 void preorder1(b...
先序遍历二叉树的非递归算法
InitStack(S);\/\/初始化栈 p=T;\/\/取栈顶 while(P||!StackEmpty(S)){ \/\/P存在或者栈非空 if(p) { \/\/p非空,即左子树或者右子树存在 Push(S,p); \/\/将左子树入栈 p=p->lchild; \/\/取下一个左子树 } else{ Pop(S,p); \/\/出栈,相当于先序遍历了,因为左子树都TMD...
怎么判断二叉树的根结点
判断二叉树根结点方法:1、前序遍历:一个输出的就是根节点;2、后序遍历:较后一个输出就是根节点;3、中序遍历:非递归情况可以控制栈的输出,若是层遍历,即一个输出的就是根节点。根结点:树的一个组成部分,也叫树根,所有非空的二叉树,都有且仅有一个根结点,它是同一棵树中除本身外...
边油安洛: /* 非递归法遍历二叉树 C语言 VC 6.0 */#include "stdio.h"#include "stdlib.h" typedef char Datatype; typedef struct BinTNode{ Datatype data; struct BinTNode *lchild, *rchild; }BinTree,*PBinTree; typedef struct stnode{ //栈的结构 Datatype data; ...
贡山独龙族怒族自治县18837064909: 求二叉树的遍历算法 - ?
边油安洛: 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...
贡山独龙族怒族自治县18837064909: 求教由二叉树的前序遍历序列建立二叉树的非递归算法 - ?
边油安洛: #include /*如发现bug请给我留言*/ #include#include#define LEN sizeof(struct node) struct node { char data; struct node *lchild,*rchild; }; struct node *build() { struct node *stack[20]={NULL},*root,*temp,*p; char c; int i=-1; c=getch(); if(c=='0') return ...
贡山独龙族怒族自治县18837064909: 二叉树的创建与非递归遍历用c语言 - ?
边油安洛: #include<stdio.h>#include<stdlib.h> typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; bitree create_tree() //先序创建 { char a;bitree root; scanf("%c",&a); fflush(stdin); if(a=='#')return NULL; else { root=(bitnode *)...
贡山独龙族怒族自治县18837064909: 二叉树的先序遍历C++非递归算法 - ?
边油安洛: template<class ElemType>//声明类模板 void NonRecurPreOrderHelp(BinTreeNode<ElemType>*r, void(*Visit)(ElemType&))//传递一个模板类型二叉树节点的指针作为参数 { BinTreeNode<ElemType>*cur=r;//接收传递进来的节点指针(作为遍历...
贡山独龙族怒族自治县18837064909: 二叉树的先序遍历算法 - -----将其用c语言编写程序 - ?
边油安洛: void preorder(BiTree T) { if(p!=NULL){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);} }
贡山独龙族怒族自治县18837064909: 先序遍历二叉树的递归和非递归算法 运用C语言或C++?
边油安洛: #define null 0 typedef struct node { elementtype data; struct node *RChild,*LChild; }BitNode,*BiTree; void PreOrder(BiTree root) {/*先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针 时间复杂度为O(n)*/ if(root!=null) { Visit(root->data); PreOrder(root->LChild); PreOrder(root->RChild); } }
贡山独龙族怒族自治县18837064909: 求二叉树的非递归后序遍历的c语言代码? - ?
边油安洛: #include<iostream> #include<stdio.h> #define N 10 using namespace std;char *a;typedef struct NODE{char data;struct NODE *lch, *rch,*parent; } *BINTREE,Node;void visit(char data){ printf("%5c",data); }void preorder(BINTREE T){ // 先...
贡山独龙族怒族自治县18837064909: c语言:在二叉树中,用非递归算法求节点所在的层次数 - ?
边油安洛: 先一层一层的遍历二叉树 用一个辅助的数据结构队列 队列! 注意 这个很重要 队首放节点 队尾取出节点 比如:根节点放入队列 (开始只有这个一个节点在队列中) 然后呢 从队尾取出这个根节点 然后打散 把他的左右孩子放入对首(这时候有2...
贡山独龙族怒族自治县18837064909: 急求二叉树的C语言的非递归算法全解过程.谢谢!!! - ?
边油安洛: #include <iostream> using namespace std;#define MAX 100 class btree { public: char data; btree *lchild; btree *rchild; }; btree *creatree() //非递归建立二叉树 {char ch;int front = 1,rear = 0; //初始化队列btree *root,*s,*Q[MAX];root=NULL;...