数据结构-二叉树(Binary Tree)
2024-10-21 05:09:18
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define TRUE 1
#define FALSE 0
#define true 1
#define false 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define OPSETSIZE 7
#define MAXQSIZE 100
typedef char TelemType;
typedef int Status;
typedef struct BiTNode
{
TelemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
typedef BiTree SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
Status InitStack(SqStack *S);
Status Push(SqStack *S, SElemType e);
Status Pop(SqStack *S, SElemType *e);
Status StackEmpty(SqStack S);
Status CreateBiTree(BiTree *T);
Status PrintElement(TelemType e);
Status visit(TelemType e);
Status PreorderTraverse(BiTree T, Status (*visit)(TelemType e));
Status InorderTraverse(BiTree T, Status (*visit)(TelemType e));
Status PostorderTraverse(BiTree T, Status (*visit)(TelemType e));
int main()
{
BiTree T;
CreateBiTree(&T);
printf("PreorderTraverse:");
PreorderTraverse(T, visit);
printf("\nInorderTraverse_1:");
InorderTraverse(T, visit);
printf("\nInorderTraverse_2:");
InorderTraverse2(T, visit);
printf("\nPostorderTraverse:");
PostorderTraverse(T, visit);
return 0;
}
Status InitStack(SqStack *S)
{
S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof (SElemType));
if (!S->base) exit (OVERFLOW);
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack *S, SElemType e)
{
if (S->top - S->base >= S->stacksize) //栈满
{
S->base = (SElemType *)realloc
(S->base, (S->stacksize + STACKINCREMENT)
* sizeof(SElemType));
if (!S->base) exit (OVERFLOW);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
} // if
*S->top++ = e;
return OK;
} //Push
Status Pop(SqStack *S, SElemType *e)
{
if(S->top == S->base)return ERROR;
*e = *--S->top;
return OK;
} //Pop
Status StackEmpty(SqStack S)
{
if (S.base == S.top)
return TRUE;
return FALSE;
}
Status CreateBiTree(BiTree *T)
{
char ch;
ch = getchar();
if (ch == ' ')
*T = NULL;
else
{
if (!(*T = (BiTNode *) malloc(sizeof (BiTNode))))
exit(OVERFLOW);
(*T)->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return OK;
}
Status PrintElement(TelemType e)
{
printf("%c ", e);
return OK;
}
Status visit(TelemType e)
{
printf("%c ", e);
return OK;
}
Status PreorderTraverse(BiTree T, Status (*visit)(TelemType e))
{
if (T)
{
if (visit(T->data))
if (PreorderTraverse(T->lchild, visit))
if (PreorderTraverse(T->rchild, visit)) return OK;
return ERROR;
}
return OK;
}
Status InorderTraverse(BiTree T, Status (*visit)(TelemType e) )
{
if (T)
{
if (InorderTraverse(T->lchild, visit))
if (visit(T->data))
if (InorderTraverse(T->rchild, visit)) return OK;
return ERROR;
}
return OK;
}
Status InorderTraverse2(BiTree T, Status (*visit)(TelemType e))
{
SqStack S;
InitStack(&S);
BiTree p = T;
while( p || !StackEmpty(S) )
{
while (p)
{
Push(&S, p);
p = p -> lchild;
}
if( !StackEmpty(S))
{
Pop(&S, &p);
if (!visit(p -> data))
return ERROR;
p = p -> rchild;
}
}
return OK;
}
Status PostorderTraverse(BiTree T, Status (*visit)(TelemType e))
{
if (T)
{
if (PostorderTraverse(T->lchild, visit))
if (PostorderTraverse(T->rchild, visit))
if (visit(T->data)) return OK;
return ERROR;
}
return OK;
}
最新文章
- Android面试题（一）
- java中字节流与字符流的区别
- 缓存Cache
- PHP之PhpDocument的使用
- Coding the Matrix (3)：矩阵
- 【CodeForces 621B】Wet Shark and Bishops
- 第十三章 调试及安全性(In .net4.5) 之 验证程序输入
- 《架构探险——从零开始写Java Web框架》这书不错，能看懂的入门书
- CSS模块化
- Qt 读写XML文件
- ExtJS实例1
- IOS基于新浪微博开放平台微博APP
- Pros and Cons of T4 in Visual Studio 2008
- App引导页面源代码的实现
- Redis中的master-slave&sentinel
- 洛谷P3233 [HNOI2014]世界树
- supersocket 遇到的Failed to initialize 和 log4net用法
- 解决MySQL5.7密码重置问题
- 2013年蓝桥杯省赛C/C++A组真题解析
- CiscoIOUKeygen