首页 > 代码库 > C语言非递归实现二叉树的先序、中序、后序遍历
C语言非递归实现二叉树的先序、中序、后序遍历
#include <stdio.h> #include <stdlib.h> #define INIT_STACK_SIZE 100 #define STACKINCREMENT 10 //*****二叉树的二叉链表存储结构*****// typedef struct BiNode { char data; struct BiNode *lchild, *rchild; int visitcount; //访问次数(后序遍历会用到) }BiNode, *BiTree; typedef struct { BiNode **base; BiNode **top; int stacksize; }SqStack; //*****初始化栈*****// void InitStack(SqStack &S) { if (!(S.base = (BiNode **)malloc(sizeof(BiTree) * INIT_STACK_SIZE))) { return; } S.top = S.base; S.stacksize = INIT_STACK_SIZE; return; } //*****元素进栈*****// void Push(SqStack &S, BiNode *e) { if (S.top - S.base >= S.stacksize) { if (!(S.base = (BiNode **)realloc(S.base, sizeof(BiTree) * (STACKINCREMENT + S.stacksize)))) { return; } S.stacksize += STACKINCREMENT; } *S.top++ = e; return; } //*****元素出栈*****// void Pop(SqStack &S, BiNode **e) { if (S.base == S.top) { return; } *e = *--S.top; return; } //*****取栈顶元素*****// int GetTop(SqStack S, BiNode **e) { if (S.base == S.top) { return 0; } *e = *(S.top - 1); return 1; } //*****判断栈是否为空*****// int StackEmpty(SqStack S) { if (S.top == S.base) return 1; else return 0; } //*****按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树构造二叉链表表示的二叉树T*****// void CreateBiTree(BiTree &T) { char ch; scanf("%c", &ch); if(ch == ' ') { T = NULL; } else { if(!(T = (BiNode *)malloc(sizeof(BiNode)))) { return; } T->data = http://www.mamicode.com/ch; //生成根结点 >以如下二叉树为例,给出按先序次序输入二叉树中结点的值(字符),从而按照本文给出的算法构造二叉树。
输入字符的顺序是:-+a空格空格*b空格空格-c空格空格d空格空格/e空格空格f空格空格,即可验证本文给出的遍历算法。
C语言非递归实现二叉树的先序、中序、后序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。