c語(yǔ)言版本二叉樹(shù)基本操作示例(先序 遞歸 非遞歸)
請(qǐng)按先序遍歷輸入二叉樹(shù)元素（每個(gè)結(jié)點(diǎn)一個(gè)字符，空結(jié)點(diǎn)為'='）:
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
深度：
請(qǐng)按任意鍵繼續(xù). . .
#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{//棧結(jié)構(gòu)定義
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));
//定義棧的相關(guān)操作
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("請(qǐng)按先序遍歷輸入二叉樹(shù)元素（每個(gè)結(jié)點(diǎn)一個(gè)字符，空結(jié)點(diǎn)為'='）:\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("%d\n", depth);
system("pause");
return 0;
}
//創(chuàng)建二叉樹(shù)
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; //生成根結(jié)點(diǎn)
T->leftChild = CreateBinTree(T->leftChild);
T->rightChild = CreateBinTree(T->rightChild);
}
return T;
}
//訪問(wèn)二叉樹(shù)
Status Visit(ElemType e)
{
if (e == '\0')
{
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];//假設(shè)不溢出
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;
}
//-----------棧的相關(guān)操作--------------//
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(S.top==S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
int StackLength(SqStack S){
return S.stacksize;
}
Status GetTop(SqStack S,SElemType *e){
if(S.top == S.base)
{
return FALSE;
}
else
{
*e = *(S.top-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;
}
 |
相關(guān)文章
C語(yǔ)言循環(huán)結(jié)構(gòu)與時(shí)間函數(shù)用法實(shí)例教程
這篇文章主要介紹了C語(yǔ)言循環(huán)結(jié)構(gòu)與時(shí)間函數(shù)用法,是C語(yǔ)言中非常重要的一個(gè)技巧,需要的朋友可以參考下2014-08-08
基于Qt實(shí)現(xiàn)Android的圖案密碼效果
這篇文章主要為大家詳細(xì)介紹了如何基于Qt實(shí)現(xiàn)Android的圖案密碼效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下2024-12-12
C++ inline內(nèi)聯(lián)函數(shù)詳解
這篇文章主要介紹了C++ inline內(nèi)聯(lián)函數(shù)詳解,有感興趣的同學(xué)可以借鑒參考下2021-02-02
函數(shù)重載是函數(shù)的一種特殊情況,C++允許在同一作用域中聲明幾個(gè)功能類(lèi)似的同名函數(shù),這 些同名函數(shù)的形參列表不同,常用來(lái)處理實(shí)現(xiàn)功能類(lèi)似數(shù)據(jù)類(lèi)型不同的問(wèn)題,本文給大家介紹了C/C++中獲取重載函數(shù)地址的方法,需要的朋友可以參考下2024-04-04
C語(yǔ)言Easyx實(shí)現(xiàn)貪吃蛇詳解
這篇文章主要為大家詳細(xì)介紹了基于easyx的C++實(shí)現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
這篇文章主要介紹了論C++的lambda是函數(shù)還是對(duì)象，對(duì)于有捕獲的lambda，其等價(jià)于對(duì)象。對(duì)于沒(méi)有任何捕獲的lambda，其等價(jià)于函數(shù)，下面來(lái)看看具體的相關(guān)內(nèi)容,需要的朋友可以參考一下2022-02-02
這篇文章主要介紹了在Linux下編譯C或C++程序的教程,是C/C++入門(mén)學(xué)習(xí)中的必備知識(shí),需要的朋友可以參考下2015-07-07
C語(yǔ)言函數(shù)調(diào)用約定和返回值詳情
這篇文章主要介紹了C語(yǔ)言函數(shù)調(diào)用約定和返回值詳情，函數(shù)調(diào)用約定不同，會(huì)影響函數(shù)生成的符號(hào)名，函數(shù)入?yún)㈨樞?，形參?nèi)存的清理者，更多相關(guān)需要的小伙伴可以參考下文詳情介紹2022-07-07
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中字符串的存儲(chǔ)方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-08-08
Qt?關(guān)于容器的遍歷迭代器的使用問(wèn)題小結(jié)
Qt是一個(gè)跨平臺(tái)的 C++ 開(kāi)發(fā)庫(kù)，主要用來(lái)開(kāi)發(fā)圖形用戶界面程序，當(dāng)然也可以開(kāi)發(fā)不帶界面的命令行程序，本文重點(diǎn)給大家介紹Qt?關(guān)于容器的遍歷迭代器的使用問(wèn)題小結(jié)，感興趣的朋友一起看看吧2022-03-03