首页 > 代码库 > 二叉树的非递归遍历C语言实现
二叉树的非递归遍历C语言实现
腾讯面试中被问到二叉树的非递归遍历实现,当时记得不太清楚,回来专门复习了非递归的实现,整理代码如下:
//采用二叉链表存储方式的二叉树,非递归中序遍历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 =http://www.mamicode.com/= 0)>
二叉树的非递归遍历C语言实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。