二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数

#include #include #include

#define STACK_INT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define OK 1

#define ERROR 0 #define TRUE 1 #define FALSE 0

#define OVERFLOW -2 typedef char TElemType; typedef int Status;

typedef char SElemType;

//二叉树的二叉链表存储表示 typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; //左右孩子指针 }BiTNode, *BiTree;

//用于存储二叉树结点的栈 typedef struct {

BiTree *base; BiTree *top;

int stacksize; //当前已分配的存储空间 }SqStack;

//定义链式队列结点 typedef struct QNode {

BiTree Queuedata; struct QNode * next; }QNode,* QueuePtr; //定义链式队列 typedef struct {

QueuePtr front; // QueuePtr rear; }LinkQueue;

//创建存储二叉树结点的空栈 Status InitStack(SqStack &S) {

S.base = (BiTree *) malloc(sizeof(BiTree)); if(!S.base) exit(OVERFLOW); S.top = S.base;

S.stacksize = STACK_INT_SIZE; return OK; }

//存储二叉树结点的栈的取栈顶元素 Status GetTop(SqStack &S, BiTree &e) {

//若栈不空，则用e返回S的栈顶元素 if(S.top == S.base) return ERROR; e = *(S.top-1); return OK; }

//存储二叉树结点的栈的入栈操作 Status Push(SqStack &S, BiTree e) {

//插入元素e为栈顶元素

if(S.top - S.base >= S.stacksize) { //若栈满，则追加存储空间 S.base = (BiTree *) realloc(S.base, STACKINCREMENT)*sizeof(BiTree)); if(!S.base) return ERROR; S.top = S.base + S.stacksize;

S.stacksize += STACKINCREMENT; }

*S.top = e; S.top++; return OK; }

//用于存储二叉树结点的栈出栈操作 Status Pop(SqStack &S,BiTree &e) {

//删除S的栈顶元素，并用e返回 if(S.base == S.top) return ERROR; S.top--; e = *S.top; return OK; }

//判断存储二叉树结点的栈是否为空 Status StackEmpty(SqStack S) {

// 若栈S为空栈，则返回TRUE，否则返回FALSE if(S.top == S.base) return TRUE; else return FALSE;

(S.stacksize +

}

//先序顺序创建一颗二叉树

Status PreOrderCreateBiTree(BiTree &T) {

//按先序次序输入二叉树中结点的值 //构造二叉链表表示的二叉树T char ch;

scanf(\

if(ch == '0') T = NULL; else {

//if(!(T = (BiTree ) malloc(sizeof(BiTree)))) exit(OVERFLOW);//作用和下一语句的作用相同，注意两者的区别

if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; //生成根结点

PreOrderCreateBiTree(T->lchild); //构造左子树 PreOrderCreateBiTree(T->rchild); //构造右子树 }

return OK;

} //CreateBiTree

//递归先序遍历二叉树 void PreOrder ( BiTree bt ) {

if ( bt ) {

printf(\先访问根节点 PreOrder ( bt->lchild );//遍历左子树 PreOrder ( bt->rchild ); //遍历右子树 } }

//递归中序遍历二叉树 void Inorder ( BiTree bt ) {

if ( bt ) {

Inorder ( bt->lchild ); //遍历左子树 printf(\访问根节点 Inorder ( bt->rchild );//遍历右子树 } }

//递归后序遍历二叉树 void LastOrder ( BiTree bt ) {

if ( bt )

{

LastOrder( bt->lchild );//遍历左子树 LastOrder( bt->rchild );//遍历右子树 printf(\访问根节点 } }

//非递归先序遍历二叉树 方法一： Status PreOrderTraverse(BiTree T) {

SqStack s; BiTree P=T; InitStack(s);

while ( P!=NULL || !StackEmpty(s)) {

if (P!=NULL) {

printf(\

Push(s,P); //访问完之后将根节点入栈 P=P->lchild; }

else {

Pop(s,P);

P=P->rchild; } }

return OK; }

//非递归先序遍历二叉树 方法二： Status PreOrderTraverse2(BiTree T) {

SqStack s; BiTree P=T; InitStack(s);

Push(s,P); //先将根节点入栈 while ( !StackEmpty(s)) {

Pop(s,P);

if (P!=NULL) {

printf(\访问根节点

Push(s,P->rchild);// 先进栈，后访问，所以这里先让右子树进栈 Push(s,P->lchild);