首页 / 算法 / 二叉树的非递归遍历C语言实现
二叉树的非递归遍历C语言实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的非递归遍历C语言实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2328字,纯文字阅读大概需要4分钟。
内容图文
腾讯面试中被问到二叉树的非递归遍历实现,当时记得不太清楚,回来专门复习了非递归的实现,整理代码如下:
//采用二叉链表存储方式的二叉树,非递归中序遍历C语言实现代码 #include<stdio.h> #include <malloc.h> //函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status是函数的类型,其值是函数结果状态代码 typedef int Status; #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; typedef struct{ BiTree *base; BiTree *top; int stacksize; }SqStack; Status InitStack(SqStack *S) { /* 构造一个空栈S */ (*S).base = (BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top = (*S).base; (*S).stacksize = STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { /* 若栈S为空栈,则返回TRUE,否则返回FALSE */ if(S.top==S.base) return TRUE; else return FALSE; } int StackLength(SqStack S) { /* 返回S的元素个数,即栈的长度 */ return S.top-S.base; } Status GetTop(SqStack S,BiTree *e) { /* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */ if(S.top>S.base) { *e = *(S.top-1); return OK; } else return ERROR; } Status 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(OVERFLOW); (*S).top = (*S).base + (*S).stacksize; (*S).stacksize += STACKINCREMENT; } *((*S).top)++=e; return OK; } Status Pop(SqStack *S,BiTree *e) { /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */ if((*S).top==(*S).base) return ERROR; *e=*--(*S).top; return OK; } /*按前序输入二叉树中结点的值*/ /*#表示空树,构造二叉链表表示二叉树T*/ void CreateBiTree(BiTree *T) //输入前序序列1,2,3方法为1 2 0 0 3 0 0 { int data; scanf("%d",&data); if(data == 0) *T = NULL; else { *T = (BiTree)malloc(sizeof(BiTNode)); if(!*T) exit(OVERFLOW); (*T)->data = data; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } } Status Visit(int e) { printf("%d ",e); return OK; } //中序非弟归遍历二叉树(二叉链表存储) Status InOrderTraverse(BiTree T,Status (*Visit)(int)){ SqStack S; BiTree p = T; InitStack(&S); while(p || !StackEmpty(S)){ if(p){ Push(&S,p); p = p->lchild; } else { Pop(&S,&p); if(!Visit(p->data)) return ERROR; p = p->rchild; } } return OK; } void main() { BiTree T; CreateBiTree(&T); InOrderTraverse(T,Visit); }
原文:http://blog.csdn.net/mirale/article/details/39891885
内容总结
以上是互联网集市为您收集整理的二叉树的非递归遍历C语言实现全部内容,希望文章能够帮你解决二叉树的非递归遍历C语言实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。