二叉树的基本操作【C语言】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树的基本操作【C语言】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6169字，纯文字阅读大概需要9分钟。

内容图文

数据结构二叉树的基本操作设计
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXLEN 100
#define NLAYER  4

typedef struct BiTNode               // 定义二叉树节点结构
{
    char data;                       // 数据域
    struct BiTNode *LChild,*RChild;  // 左右孩子指针域
}BiTNode,*BiTree;
BiTree T;

//(1) 建立二叉树
void CreateBiTree(BiTree *bt)
{ // 按照 <先序序列>建立二叉树的二叉链表的过程
     
    char ch;
    scanf("%s",&ch); 
    if(ch=='#') {
        *bt=NULL;
        return;
    }
    else 
    {
        *bt=(BiTree)malloc(sizeof(BiTNode)); // 生成一个新结点
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->LChild));      // 生成左子树
        CreateBiTree(&((*bt)->RChild));      // 生成右子树
    }
    
}

//(2) 树型打印二叉树
void TranslevelPrint(BiTree bt)
{  //本算法实现二叉树的按层打印
    struct node
    {
        BiTree vec[MAXLEN];           // 存放树结点
        int layer[MAXLEN];            // 结点所在的层
        int locate[MAXLEN];           // 打印结点的位置
        int front,rear;
    }q;                               // 定义队列q
    int i,j,k;
    int nLocate;
    j = 1;
    k = 0;
    q.front = 0;                      // 初始化队列q队头，队尾
    q.rear = 0;
    printf(" ");
    q.vec[q.rear] = bt;               // 将二叉树根节点入队列
    q.layer[q.rear] = 1;
    q.locate[q.rear] = 20;
    q.rear = q.rear + 1;
    while(q.front < q.rear)
    {
        bt = q.vec[q.front];
        i = q.layer[q.front];        
        nLocate = q.locate[q.front];
        if(j < i)                      // 进层打印时换行
        {
            printf("\n");
            printf("\n");
            j = j + 1;            
            k = 0;
            while(k < nLocate)
            {
                printf(" ");
                k++;
            }
        }
        while(k < (nLocate-1))          // 利用结点深度控制横向位置
        {
            printf(" ");
            k++;
        }
        printf("%c",bt->data);
        q.front = q.front + 1;
        if(bt->LChild != NULL)          // 存在左子树，将左子树根节点入队列
        {        
            q.vec[q.rear] = bt->LChild;
            q.layer[q.rear] = i + 1;
            q.locate[q.rear] =(int)(nLocate - pow(2, NLAYER-i-1));
            q.rear = q.rear +1;
        }
        if(bt->RChild != NULL)         // 存在右子树，将右子树根节点入队列
        {        
            q.vec[q.rear] = bt->RChild;
            q.layer[q.rear] = i + 1;
            q.locate[q.rear] =(int)(nLocate + pow(2, NLAYER-i-1));
            q.rear = q.rear +1;
        }
    }
}

//(3) 输出结点
void Visit(char ch)
{
    printf("%c  ",ch);
}

//(4) 先序遍历二叉树
void  PreOrder(BiTree root) 
{// 先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针
    if (root!=NULL)
    {
        Visit(root ->data);       // 访问根结点
        PreOrder(root ->LChild);  // 先序遍历左子树
        PreOrder(root ->RChild);  // 先序遍历右子树
    }
}

//(5) 中序遍历二叉树
void  InOrder(BiTree root)  
{// 中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针
    if (root!=NULL)
    {
        InOrder(root ->LChild);    // 中序遍历左子树
        Visit(root ->data);        // 访问根结点
        InOrder(root ->RChild);    // 中序遍历右子树
    }
}

//(6) 后序遍历二叉树
void  PostOrder(BiTree root)  
{//后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针
    if(root!=NULL)
    {
        PostOrder(root ->LChild);  // 后序遍历左子树
        PostOrder(root ->RChild);  // 后序遍历右子树
        Visit(root ->data);        // 访问根结点
    }
}

//(7) 输出叶子结点
void  PreOrderLeaf(BiTree root) 
{//先序遍历二叉树并输出叶子结点, root为指向二叉树根结点的指针
    if (root!=NULL)
    {
        if (root ->LChild==NULL && root ->RChild==NULL)
            printf("%c  ",root ->data);   // 输出叶子结点
        PreOrderLeaf(root ->LChild);      // 先序遍历左子树
        PreOrderLeaf(root ->RChild);      // 先序遍历右子树
    }
}

//(8) 输出叶子结点的个数
int LeafCount(BiTree root)
{
    int LeafNum;
    if(root==NULL)    
        LeafNum=0;
    else 
        if((root->LChild==NULL)&&(root->RChild==NULL))
            LeafNum=1;
        else 
            LeafNum=LeafCount(root->LChild)+LeafCount(root->RChild);    // 叶子数为左右子树的叶子数目之和
 
    return LeafNum;
}

//(9) 输出二叉树的深度
int PostTreeDepth(BiTree root)   // 后序遍历求二叉树的深度递归算法 
{
    int hl,hr,max;
    if(root!=NULL)
    {
        hl=PostTreeDepth(root->LChild);  // 求左子树的深度
        hr=PostTreeDepth(root->RChild);  // 求右子树的深度 
        max=hl>hr?hl:hr;                 // 得到左、右子树深度较大者
        return(max+1);                   // 返回树的深度 
    }
    else return(0);                      // 如果是空树，则返回0 
}

//(10) 主要工作函数。操作区用户界面
void mainwork()
{
    int yourchoice;
      
    printf("\n------------------------欢迎使用二叉树基本操作程序---------------------------\n");
    printf("\n                               菜 单 选 择                                 \n\n");
    printf("        1. 树状输出二叉树                        2. 先序遍历二叉树             \n");
    printf("        3. 中序遍历二叉树                        4. 后序遍历二叉树             \n");
    printf("        5. 输出叶子结点                          6. 输出叶子结点个数           \n");
    printf("        7. 输出二叉树的深度                      8. 退出                       \n");
    printf("\n-----------------------------------------------------------------------------\n");
    printf("请输入你的选择：");
    scanf("%d",&yourchoice);
    while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4||yourchoice==5||yourchoice==6
          ||yourchoice==7||yourchoice==8))
    {
        printf("输入选择不明确，请重输\n");
        scanf("%d",&yourchoice);
    }
    while(1)
    {
        switch(yourchoice)
        {
            case 1:    printf("树的形状为:\n");TranslevelPrint(T);  getch();        break;
            case 2:    printf("先序遍历序列为:"); PreOrder(T);    break;
            case 3:    printf("\n中序遍历序列为:");InOrder(T); break;
            case 4:    printf("\n后序遍历序列为:");PostOrder(T);    break;
            case 5:    printf("叶子结点为:"); PreOrderLeaf(T);     break;
            case 6:    printf("叶子结点个数为:%d",LeafCount(T));            break;
            case 7: printf("二叉树的深度为:%d",PostTreeDepth(T));   break;
            case 8: system("cls");    exit(0);             break;
            default:  break;
        }
    
            printf("\n------------------------欢迎使用二叉树基本操作程序---------------------------\n");
            printf("\n                               菜 单 选 择                                 \n\n");
            printf("        1. 树状输出二叉树                        2. 先序遍历二叉树             \n");
            printf("        3. 中序遍历二叉树                        4. 后序遍历二叉树             \n");
            printf("        5. 输出叶子结点                          6. 输出叶子结点个数           \n");
            printf("        7. 输出二叉树的深度                      8. 退出                       \n");
            printf("\n-----------------------------------------------------------------------------\n");

        printf("\n请输入你的选择：");
        scanf("%d",&yourchoice);
    }//endwhile(1)

}//mainwork

//(11) 主函数。创建二叉树，调用工作区模块函数
void main()
{
        printf("首先请输入二叉树的结点序列《按照 <先序序列>建立二叉树的二叉链表》：\n");
        CreateBiTree(&T);
        printf("请按菜单提示操作：\n");
        mainwork();
    
}

内容总结

以上是互联网集市为您收集整理的二叉树的基本操作【C语言】全部内容，希望文章能够帮你解决二叉树的基本操作【C语言】所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/987374.html

来源：【匿名】

【上一篇】堆排序【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【二叉树的基本操作【C语言】】教程文章相关的互联网学习教程文章

下面实现几种串的基本操作，这些操作是构成串其他复杂操作的基石。因为相对简单，功能和分析的说明均在代码实现中。/*动态分配存储结构*/ typedef struct {char *ch;int length; }Str;/*赋值操作*/int strAssign(Str &str, char *ch) {if(str.ch)free(str.ch); //释放原串空间int len = 0;char *c = ch;while(*c) //求ch串长度 {len++;c++;}if(len == 0) //如果ch为空串，则直接返回空串 {str.ch = NULL;str.length = 0;r...

算法与数据结构--图的实现、基本操作及应用

#include<iostream> #include<queue> #include<stack> using namespace std;#define INFINITY DBL_MAX //无穷大 #define MAX_VERTEX_NUM 20 //最大顶点个数 enum GraphKind //图的类型 {DG,DN,UDG,UDN//有向图、有向网、无向图、无向网 };//弧结构 typedef struct ArcCell {double adj;//权值，无权图用1表示 }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵图结构struct MGraph {int vexs[MAX_VERTEX_NUM];//顶点集合...

<二叉树的基本操作>【代码】

#include<stdio.h> #include<stdlib.h> #include<string.h>#define num 100 #define OK 1typedef int Status; typedef char DataType;typedef struct node {DataType data;struct node *lchild,*rchild; }BinTNode,*BinTree;Status CreateBiTree(BinTree &bt) {//按照先序遍历次序递归建立二叉树。//ABC@@DE@G@@F@@char ch;scanf("%c",&ch);if(ch == ‘@‘) bt = NULL;else{bt = (BinTNode*)malloc(sizeof(BinTNode));bt->data ...

【算法与数据结构专场】BitMap算法基本操作代码实现【代码】【图】

上篇我们讲了BitMap是如何对数据进行存储的，没看过的可以看一下【算法与数据结构专场】BitMap算法介绍这篇我们来讲一下BitMap这个数据结构的代码实现。回顾下数据的存储原理一个二进制位对应一个非负数n，如果n存在，则对应的二进制位的值为1，否则为0。这个时候，我们的第一个问题：我们在使用byte,int,short,long等这些数据类型在存储数据的时候，他们最小的都要占用一个字节的内存，也就是8个bit，也就是说，最小的操作单位是8...

蓝桥杯ACM训练Day4——算法2-8~2-11：链表的基本操作【代码】

题目描述链表是数据结构中一种最基本的数据结构，它是用链式存储结构实现的线性表。它较顺序表而言在插入和删除时不必移动其后的元素。现在给你一些整数，然后会频繁地插入和删除其中的某些元素，会在其中某些时候让你查找某个元素或者输出当前链表中所有的元素。输入输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，...

数组的基本操作和冒泡算法直接选择排序反转排序【代码】【图】

目录数组一、数组定义方法二、数组包括的数据类型三、获取数组长度读取某索引赋值四、数组遍历五、数组切片六、数组替换七、数组删除八、数组追加元素九、向函数传数组参数十、排序算法1、冒泡排序算法2、直接选择排序3、反转排序数组一、数组定义方法方法一：数组名=（value0 value1 value2 …）方法二: 数组名=（[0]=value [1]=value [2]=value …)方法三：列表名=“value0 value1 value2 …” 数组名=（$列表名）方法四： ...

数据结构二叉树的建立与基本操作C/C++

typedef struct Node {char data;struct Node * leftChild;struct Node * rightChild; } Node;Node * preCreateBt(Node *); void preOrderTransverse(Node*); void inOrderTransverse(Node*); void postOrderTransverse(Node*); int getLeafNumber(Node*); int getNumber(Node*); int getHigh(Node*); bool findData(Node*, char); void inOrderByStack(Node *);int main(void)// ABEH###C#D##MN### {Node * btn = NULL;btn = preC...