领购物优惠券9块9包邮
首页 > 编程语言 > C/C++教程

c语言版本二叉树基本操作示例(先序递归非递归)

   2015-08-01 0
核心提示：这篇文章主要介绍了实现二叉树的创建（先序）、递归及非递归的先、中、后序遍历

复制代码 代码如下:

请按先序遍历输入二叉树元素（每个结点一个字符，空结点为'='）:
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;
}



c语言版本二叉树基本操作示例(先序递归非递归)

c语言版本二叉树基本操作示例(先序递归非递归)
 

 
标签： 二叉树 基本操作 c语言版本 先序 递归 非递归
反对 0举报 0 评论 0
 

免责声明：本文仅代表作者个人观点，与乐学笔记（本网）无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
    本网站有部分内容均转载自其它媒体，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责，若因作品内容、知识产权、版权和其他问题，请及时提供相关证明等材料并与我们留言联系，本网站将在规定时间内给予删除等相关处理.

  • 数据结构TypeScript之二叉查找树实现详解
    目录树的结构特点面向对象方法封装二叉查找树（迭代版）二叉查找树的定义构造函数基本单元：二叉查找树节点主体：二叉查找树增加节点查找节点删除节点二叉树的遍历树的结构特点树是一种有层次的数据结构，通常用于存储具有层次性的数据。比如上下级的关系图，
    02-09 TypeScript数据结构二叉树查找
  • 数据结构与算法之二叉树 ——in dart
    用dart语言实现的二叉树，实现了插入、查找、删除，中序遍历、前序、后序遍历等功能。1 class BinaryTreeE extends Comparable {2 NodeE _root;3 int _nodeNumbers;4 5 BinaryTree() : _nodeNumbers = 0;6 7 factory BinaryTree.from(IterableE elements) {8
    02-09
  • C语言实现二叉树链式结构的示例详解
    C语言实现二叉树链式结构的示例详解
    目录前言1. 链式二叉树结构2. 二叉树的遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历2.4 层序遍历3. 常见功能3.1 二叉树结点个数3.2 二叉树叶子结点个数3.3 第K层结点的个数3.4 二叉树的深度3.5 判断是不是树是不是完全二叉树3.6 在二叉树中查找值为x的结点3.7
    02-09 C语言二叉树链式结构
  • Java二叉树查询原理深入分析讲解
    Java二叉树查询原理深入分析讲解
    目录二叉查询树结点实现原理插入实现原理遍历实现原理删除实现原理结点插入与遍历案例二叉查询树概述二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的
    02-09 Java二叉树查询
  • Go语言数据结构之二叉树可视化详解 go 二叉树遍历
    Go语言数据结构之二叉树可视化详解 go 二叉树遍
    目录题目源代码做题思路扩展左右并列展示上下并列展示总结回顾题目以图形展示任意二叉树，如下图，一个中缀表达式表示的二叉树：3.14*r²*h/3源代码package main import ("fmt""io""os""os/exec""strconv""strings") type any = interface{} type btNode stru
    02-09 Go二叉树可视化
  • go语言算法题解二叉树的最小深度 完全二叉树的
    目录题目：说明：解法：题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点。解法：func minDepth(root *TreeNode) int {if root == nil {return 0}minDepth := math.MaxIn
    02-09 go二叉树最小深度算法
  • Rust 学习之基于 RefCell 的简单二叉树
    作者：suhanyujie来源：https://github.com/suhanyujie/rust-cookbook-notetags：Rust，binary-tree，Rc，RefCelltips：如有不当之处，还请指正~最近，在力扣平台刷题时，无意中刷到了一个关于二叉树的题目：二叉树的最小深度，打算使用 Rust 实现它。不得不
    02-09
  • TypeScript获取二叉树的镜像实例
    TypeScript获取二叉树的镜像实例
    目录前言思路分析实现代码前言给定一颗二叉树，如何获取它的镜像？本文将跟大家分享这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。思路分析当我们把一张写有文字的纸放在镜子前面，你看到的内容正好与你写的内容是相反的。那么我们就可以依据照镜子的
    02-08 TypeScript二叉树镜像
  • java面试题解LeetCode27二叉树的镜像实例
    目录正文解题思路方法一：递归法方法二：辅助栈（或队列）正文LeetCode27. 二叉树的镜像 请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如输入：4/2 7 / \ /1 3 6 9 镜像输出：4/7 2 / \ /9 6 3 1示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7
    02-08 java面试LeetCode二叉树镜像
  • Python 树表查找（二叉排序树、平衡二叉树）
    Python 树表查找（二叉排序树、平衡二叉树）
    目录什么是树表查询？1. 二叉排序树1.1 构建一棵二叉排序树1.2 二叉排序树的数据结构1.3 实现二叉排序树类中的方法：3. 平衡二叉排序树3.1 二叉平衡排序树的数据结构4. 总结什么是树表查询？借助具有特殊性质的树数据结构进行关键字查找。本文所涉及到的特殊
    02-08 Python树表查找
更多>PHP教程
php-fpm进程管理的三种模式 phpfpm子进程 [PHP8] 我参加了PHP8工程师认证初学者考试beta考试
更多>C/C++教程
VScode运行C++中文终端乱码的解决方案 vscode错误提示中文 C++ LeetCode1945题解字符串转化后的各位数字之和
更多>Java教程
Java项目导出数据为 PDF 文件的操作代码 盘点Java中延时任务的多种实现方式 java 延时队列怎么实现
更多>ASP.NET
使用WebClient自动填写并提交ASP.NET页面表单的源代码 asp.net mvc多条件+分页查询解决方案 asp.net mvc多条件+分页查询解决方案
更多>JSP编程
JSP通用高大上分页代码(超管用) JSP验证码动态生成方法
点击排行
网站首页  |  关于我们  |  联系方式  |  使用协议  |  版权隐私  |  网站地图  |  网站留言  |  违规举报