二叉树的建立及其递归遍历(C语言实现)

二叉树的建立及其递归遍历(C语言实现)最近在学习数据结构中树的概念,迟迟不得入门,应该是自己的懒惰和没有勤加练习导致的,以后应该多加练习以下是我对二叉树的一些总结内容二叉树的特点有:-每一个节点最多有两棵子树,所以二叉树中不存在度大于2的节点,注意,是最多有两棵,没有也是可以的左子树和右子树是有顺序的,次序不能颠倒,这点可以在哈夫曼编码中体现,顺序不同编码方式不同-即使树中某个节点中只有一个子树的花,也要区分它…

大家好,又见面了,我是你们的朋友全栈君。

最近在学习数据结构中树的概念,迟迟不得入门,应该是自己的懒惰和没有勤加练习导致的,以后应该多加练习

以下是我对二叉树的一些总结内容
二叉树的特点有:

  • 每一个节点最多有两棵子树,所以二叉树中不存在度大于2的节点,注意,是最多有两棵,没有也是可以的
    左子树和右子树是有顺序的,次序不能颠倒,这点可以在哈夫曼编码中体现, 顺序不同编码方式不同

-即使树中某个节点中只有一个子树的花,也要区分它是左子树还是右子树
二叉树一般有五种形态
1.空二叉树
2.只有一个根节点
3.根结点只有左子树
4.根节点只有右子树
这里写图片描述这里写图片描述

二叉树的性质
1:在二叉树的第i层上最多有2^(i-1)个节点
2:深度为K的二叉树之多有2^(k-1)个节点

注:这里的深度K意思就是有K层的二叉树

3:对于任何一棵二叉树T,如果其终端节点有No个,度为2的节点数有N2,则No=N2+1
4: 具有n个节点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)

1,二叉树的存储结构(二叉链表)

//二叉树的存储结构,一个数据域,2个指针域
 typedef struct BiTNode
{
     char data;
     struct BiTNode *lchild,*rchild;
  }BiTNode,*BiTree;

2,首先要建立一个二叉树,建立二叉树必须要了解二叉树的遍历方法。,我在这里展示的是二叉树的递归建立方式

//我在这里实现的是,二叉树的前序遍历方式创建,如果要使用中序或者后序的方式建立二叉树,只需将生成结点和构造左右子树的顺序改变即可
 void CreateBiTree(BiTree *T)
  { 
   
      char ch;
      scanf("%c",&ch);
      if(ch=='#')
          *T=NULL;
      else
     { 
   
         *T=(BiTree  )malloc(sizeof(BiTNode));
         if(!*T)
             exit(-1);
          (*T)->data=ch;
          CreateBiTree(&(*T)->lchild);
         CreateBiTree(&(*T)->rchild);
      }
 }

这里写图片描述
3。二叉树的遍历方式(递归建立)

void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{ 
   
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{ 
   
   if(T==NULL)
       return ;
   InOrderTraverse(T->lchild);
    printf("%c ",T->data);
   InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{ 
   
    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c ",T->data);
}

4.完整代码

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode
{ 

char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{ 

if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{ 

if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{ 

if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
void CreateBiTree(BiTree *T)
{ 

char ch;
scanf("%c",&ch);
if(ch=='#')
*T=NULL;
else
{ 

*T=(BiTree  )malloc(sizeof(BiTNode));
if(!*T)
exit(-1);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
int main()
{ 

BiTree T;
CreateBiTree(&T);
PreOrderTraverse (T);
InOrderTraverse(T);
PostOrderTraverse(T);
return 0;
}

对知识点的补充:
(1)建立二叉树时,这里是以前序遍历的方式,输入的是扩展二叉树,也就是要告诉计算机什么是叶结点,否则将一直递归,当输入“#”时,指针指向NULL,说明是叶结点。

如图为扩展二叉树:(前序遍历为:ABDG##H###CE#I##F##)
这里写图片描述

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130189.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Pycharm安装使用TensorFlow[通俗易懂]

    Pycharm安装使用TensorFlow[通俗易懂]众多深度学习的初学者都会面临环境搭建的问题,本文根据亲身经历说明几个关键步骤:1.安装Pycharm,其中社区版免费,可以直接去pycharm官网下载安装https://www.jetbrains.com/pycharm/download/2.安装Anaconda,初学者不用急于安装最新版本的Anaconda(尤其是硬件设备并非最新的初学者,因为我注意到很多初学者的设备就是自己的笔记本或者台式机,一些并没有独立显卡,或者是NVIDIA730之类的台式机显卡,无法使用最新的深度学习包,以及一些CUD

  • C# SqlTransaction的使用[通俗易懂]

    C# SqlTransaction的使用[通俗易懂]Sqltransaction是用在多sql任务写数据库时的Codeusing(SqlConnectionconn=newSqlConnection(SqlHelper.ConnectionString)){conn.Open();…

  • sql数据库查询语句大全_sql基本语句大全

    sql数据库查询语句大全_sql基本语句大全1、今天select*from表名whereto_days(时间字段名)=to_days(now());2、昨天SELECT*FROM表名WHERETO_DAYS(NOW())-TO_DAYS(时间字段名)<=13、近7天SELECT*FROM表名whereDATE_SUB(CURDATE(),INTERVAL7DAY)<=date(时间字段名)4、近30天SELECT*FROM表名where

  • java怎么输出数组的下标_java数组获取指定元素

    java怎么输出数组的下标_java数组获取指定元素/** *输出数组指定元素的下标 */ publicstaticvoidmain(String[]args){ //定义一个数组 int[]array=newint[]{123,456,789,321,654,987}; intindex=printArray(array,321); System.out.println(“321对应的下标是:”+index); //查询没有的数据 intindex1=printArray(array,1..

    2022年10月11日
  • 在活动目录中,转移和占用操作主机角色(转移)

    在活动目录中,转移和占用操作主机角色(转移)

  • python怎么读取excel文件_python如何读取文件夹下的所有文件

    python怎么读取excel文件_python如何读取文件夹下的所有文件python读取excel文件如何进行python编程语言拥有着比较强大的excel读写能力,我们只需要安装xlrd,xlwt这两个库就可以了。那么python读取excel文件如何进行,今天就为大家分享下python读取excel文件的具体操作方法,快来了解下吧!1、首先说明我是使用的python3.5,我的office版本是2010,首先打开dos命令窗,安装必须的两个库,命令是:pip3installxlrdPip3installxlwt2、准备好excel,例如我的一个工作文件,我

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号