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("%d\n", 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 == '\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];//假设不溢出
        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(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;
}

 
时间： 2024-08-03 19:25:36

c语言版本二叉树基本操作示例(先序 递归 非递归)_C 语言的相关文章

使用C语言求二叉树结点的最低公共祖先的方法_C 语言

算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

深入遍历二叉树的各种操作详解（非递归遍历）_C 语言

先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序.中序.后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队,还有两个操作就是求二叉树的深度.结点数... 复制代码 代码如下: #include<iostream>#include<queue>#include<stack>using namespace std;/

求大神告诉我我的二叉树后序遍历非递归哪里错了

问题描述 求大神告诉我我的二叉树后序遍历非递归哪里错了 #include using namespace std; struct binode { int data; binode *lchild,*rchild; }; binode *Q[100],*S[100]; struct element { binode *ptr; int flag; }; class bitree { public: void create_bitree(){root=creat(root);} void dele

一波二叉树遍历问题的C++解答实例分享_C 语言

题目一:   输入一颗二元树,从上往下按层打印树的每个节点,同一层按照从左往右的顺序打印. 输入样例: 8 / / 6 10 / / / / 5 7 9 11 输出样例: 复制代码 代码如下: 8 6 10 5 7 9 11 思路分析:     把一颗二叉树抽象成三个节点:根节点.左节点.右节点.     先序遍历即可得到按行输出的效果.     对于左子树只要保存其根节点,既保存了整个左子树.(右子树一样)     对于根节点之外的两个子树来说说,始终是先访问左子树的根节点,再访问右子树的根节

C语言中结构体(struct)的几种初始化方法_C 语言

本文给大家总结的struct数据有3种初始化方法      1.顺序      2.C风格的乱序      3.C++风格的乱序 下面通过示例代码详细介绍这三种初始化方法. 1)顺序 这种方法很常见,在一般的介绍C的书中都有介绍.顺序初始化的特点是: 按照成员定义的顺序,从前到后逐个初始化:允许只初始化部分成员:在被初始化的成员之前,不能有未初始化的成员. 示例: struct User oneUser = {10, "Lucy", "/home/Lucy"}; 2

C语言安全编码之数组索引位的合法范围_C 语言

C语言中的数组索引必须保证位于合法的范围内! 示例代码如下: enum {TABLESIZE = 100}; int *table = NULL; int insert_in_table(int pos, int value) { if(!table) { table = (int *)malloc(sizeof(int) *TABLESIZE); } if(pos >= TABLESIZE) { return -1; } table[pos] = value; return 0; } 其中:p

C语言单链队列的表示与实现实例详解_C 语言

1.概述: C语言的队列(queue),是指先进先出(FIFO, First-In-First-Out)的线性表.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 而单链队列使用链表作为基本数据结果,因此不存在伪溢出的问题,队列长度也没有限制.但插入和读取的时间代价会比较高 2.实例代码: /* 单链队列--队列的链式存储结构 */ typedef struct QNode { QElemType data; struct

C语言中操作进程信号的相关函数使用详解_C 语言

C语言signal()函数:设置信号处理方式头文件: #include <signal.h> 定义函数: void (*signal(int signum, void(* handler)(int)))(int); 函数说明:signal()会依参数signum 指定的信号编号来设置该信号的处理函数. 当指定的信号到达时就会跳转到参数handler 指定的函数执行. 如果参数handler 不是函数指针, 则必须是下列两个常数之一: 1.SIG_IGN 忽略参数signum 指定的信号. 2.

利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题_C 语言

跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级. 求总共有多少总跳法,并分析算法的时间复杂度. 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过): #include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3d\n&q