c语言版本二叉树基本操作示例
在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。本文特意为大家收集整理了c语言版本二叉树基本操作示例,希望大家喜欢!
复制代码 代码如下:
请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):
ABD==E==CF==G==
先序递归遍历:
A B D E C F G
中序递归遍历:
D B E A F C G
后序递归遍历:
D E B F G C A
层序递归遍历:
ABCDEFG
先序非递归遍历:
A B D E C F G
中序非递归遍历:
D B E A F C G
后序非递归遍历:
D E B F G C A
深度:
请按任意键继续. . .
复制代码 代码如下:
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct BTNode
{
ElemType data;
struct BTNode *leftChild;
struct BTNode *rightChild;
}BTNode, *BinTree;
typedef BinTree SElemType;
typedef struct{//栈结构定义
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
BinTree CreateBinTree(BinTree T);
Status Visit(ElemType e);
Status Depth(BinTree T);
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
//定义栈的相关操作
Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(const SqStack *S);
Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
int main()
{
int depth;
BinTree Tree = NULL;
Status(*visit)(ElemType e) = Visit;
printf_s("请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):n");
Tree = CreateBinTree(Tree);
printf_s("n先序递归遍历:n");
PreOrderRecursionTraverse(Tree,visit);
printf_s("n中序递归遍历:n");
InOrderRecursionTraverse(Tree,visit);
printf_s("n后序递归遍历:n");
PostOrderRecursionTraverse(Tree,visit);
printf_s("n层序递归遍历:n");
LevelOrderRecursionTraverse(Tree,visit);
printf_s("n先序非递归遍历:n");
PreOrderNoneRecursionTraverse(Tree,visit);
printf_s("n中序非递归遍历:n");
InOrderNoneRecursionTraverse(Tree,visit);
printf_s("n后序非递归遍历:n");
PostOrderNoneRecursionTraverse(Tree,visit);
printf_s("n深度:n");
depth = Depth(Tree);
printf_s("%dn", depth);
system("pause");
return 0;
}
//创建二叉树
BinTree CreateBinTree(BinTree T)
{
char ch;
scanf_s("%c", &ch);
if (ch == '=')
{
T = NULL;
}
else
{
if (!(T=(BTNode *) malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
T->data = ch; //生成根结点
T->leftChild = CreateBinTree(T->leftChild);
T->rightChild = CreateBinTree(T->rightChild);
}
return T;
}
//访问二叉树
Status Visit(ElemType e)
{
if (e == '')
{
return ERROR;
}
else
{
printf_s("%c ", e);
}
return OK;
}
//先序遍历递归算法
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
if (!Visit(T->data))
{
return ERROR;
}
PreOrderRecursionTraverse(T->leftChild, Visit);
PreOrderRecursionTraverse(T->rightChild, Visit);
}
return OK;
}
//中序遍历递归算法
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
InOrderRecursionTraverse(T->leftChild, Visit);
if (!Visit(T->data))
{
return ERROR;
}
InOrderRecursionTraverse(T->rightChild, Visit);
}
return OK;
}
//后序遍历递归算法
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
PostOrderRecursionTraverse(T->leftChild, Visit);
PostOrderRecursionTraverse(T->rightChild, Visit);
if (!Visit(T->data))
{
return ERROR;
}
}
return OK;
}
//层序遍历递归算法
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
if (T)
{
BTNode *Q[100];//假设不溢出
int front = -1,rear = -1;
if (T)
{
Q[++rear] = T;
printf_s("%c", T->data);
while (front != rear)
{
BTNode *p;
if (!(p = (BTNode *)malloc(sizeof(BTNode))))
{
exit(OVERFLOW);
}
p = Q[++front];
if (p->leftChild)
{
Q[++rear] = p->leftChild;
printf("%c",p->leftChild->data);
}
if (p->rightChild)
{
Q[++rear] = p->rightChild;
printf("%c",p->rightChild->data);
}
}
}
}
return OK;
}
Status Depth(BinTree T)
{
int a,b;
if (!T)
{
return ERROR;
}
else
{
a = Depth(T->leftChild) + 1;
b = Depth(T->rightChild) + 1;
return a > b ? a : b;
}
}
//先序遍历非递归算法
Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p;
InitStack(&S);
Push(&S, T);
while (!StackEmpty(S))
{
Pop(&S, &p);
if (!Visit(p->data))
{
return ERROR;
}
if (p->leftChild)
{
Push(&S, p->rightChild);
}
if (p->rightChild)
{
Push(&S, p->leftChild);
}
}
DestroyStack(&S);
return OK;
}
//中序遍历非递归算法
Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p;
InitStack(&S);
Push(&S, T);
while (!StackEmpty(S))
{
while (GetTop(S,&p) && p)
{
Push(&S, p->leftChild);
}
Pop(&S, &p);
if (!StackEmpty(S))
{
Pop(&S, &p);
if (!Visit(p->data))
{
return ERROR;
}
Push(&S, p->rightChild);
}
}
DestroyStack(&S);
return OK;
}
//后序便利非递归算法
Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
SqStack S;
SElemType p, q;
InitStack(&S);
Push(&S,T);
while(!StackEmpty(S))
{
while(GetTop(S,&p)&&p&&(p->leftChild||p->rightChild))
{
Push(&S,p->rightChild);
Push(&S,p->leftChild);
}
if(!StackEmpty(S)){
Pop(&S,&p);
if (p)
{
if(!Visit(p->data))
{
return ERROR;
}
}
else
{
Pop(&S,&p);
if(!Visit(p->data))
{
return ERROR;
}
}
while (GetTop(S,&q)&&q&&p==q->rightChild)
{
Pop(&S,&p);
if(!Visit(p->data))
{
return ERROR;
}
GetTop(S,&q);
}
}
}
DestroyStack(&S);
return OK;
}
//-----------栈的相关操作--------------//
Status InitStack(SqStack *S){
S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S->base)
{
exit(0);
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S){
if(!S)
{
exit(0);
}
free(S->base);
return OK;
}
Status ClearStack(SqStack *S){
if(!S)
{
return FALSE;
}
S->top = S->base;
return OK;
}
Status StackEmpty(SqStack S){
if(==)
{
return TRUE;
}
else
{
return FALSE;
}
}
int StackLength(SqStack S){
return ksize;
}
Status GetTop(SqStack S,SElemType *e){
if( == )
{
return FALSE;
}
else
{
*e = *(-1);
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(0);
}
S->top = S->base+S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
return OK;
}
Status Pop(SqStack *S,SElemType *e){
if(S->top==S->base)
{
return ERROR;
}
*e = *(--S->top);
return OK;
}
-
C语言数组的定义及引用
引导语:数组是在程序设计中,为了处理方便,把具有相同类型的若干变量按有序的形式组织起来的一种形式。以下是本站小编分享给大家的C语言数组,希望大家喜欢!1.1一维数组的定义、初始化和引用1.一维数组的定义方式为:类型说明符数组名[常量表达式](1)数组名的命名方法...
-
2017年3月计算机二级C语言考试摸底测试题
以下是yjbys考试网小编整理的2017年3月计算机二级C语言考试摸底测试题,希望对大家有所帮助,祝大家计算机二级考试顺利通过。一、选择题(每小题1分。)(1)程序流程图中带有箭头的线段表示的是()。A.图元关系B.数据流C.控制流D.调用关系(2)结构化程序设计的基本原则...
-
C语言转义字符和格式控制符参考
导语:字符型常量所表示的值是字符型变量所能包含的值。我们可以用ASCII表达式来表示一个字符型常量,或者用单引号内加反斜杠表示转义字符。下面是C语言转义字符和格式控制符参考,欢迎学习:转义字符参考:a:蜂鸣,响铃:回退:向后退一格f:换页:换行,光标到下行行首:回车,光...
-
计算机c语言基础知识
C语言程序设计是高效计算机专业学生必修的一门基础课程,那么你对计算机c语言了解多少呢?下面是小编整理的计算机c语言基础知识,欢迎大家阅读参考。计算机c语言的特性C语言是世界上最流行、使用最广泛的高级程序设计语言之一。在操作系统和系统使用程序以及需要对...