C语言二叉树的概念结构详解

目录
  • 1、树的概念及结构(了解)
    • 1.1树的概念:
    • 1.2树的表示法:
  • 2、二叉树的概念及结构
    • 2.1二叉树的概念
    • 2.2特殊的二叉树
    • 2.2二叉树的性质
    • 2.3二叉树的顺序存储
    • 2.4二叉树的链式存储
  • 3、二叉树链式结构的实现
    • 3.1二叉树的前中后序遍历
    • 3.2求二叉树的节点个数
    • 3.3求二叉树的叶子节点个数
    • 3.4销毁二叉树

1、树的概念及结构(了解)

1.1树的概念:

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

  • 有一个特殊的结点,称为根结点,根节点没有前驱结点。
  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。
  • 树是递归定义的。

子树是不相交的;除了根节点之外,每个节点有且仅有一个父节点;一棵N个节点的树有N-1条边。

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为3

叶节点或终端节点:度为0的节点称为叶节点; 如上图:J、F、K、L、H、I节点为叶节点

非终端节点或分支节点:度不为0的节点; 如上图:B、C、D、E..等节点为分支节点

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为3

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙

森林:由m(m>0)棵互不相交的多颗树的集合称为森林;(数据结构中的学习并查集本质就是 一个森林)

1.2树的表示法:

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式, 如:双亲表示法,孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法。(我们本期主要讲解二叉树)

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

2、二叉树的概念及结构

2.1二叉树的概念

一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子 树和右子树的二叉树组成。

二叉树的特点:

1. 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。

2. 二叉树的子树有左右之分,其子树的次序不能颠倒。

2.2特殊的二叉树

1、满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉 树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

2、完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对 于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

2.2二叉树的性质

1、若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2、若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1.

3、对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2 + 1.

2.3二叉树的顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2.4二叉树的链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,我们本期用的是二叉链,后期到高阶数据结构如红黑树等会用到三叉链。

代码结构搭建:

typedef char BTDataType;
typedef struct BinaryTreeNode
{
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
}BTNode;

3、二叉树链式结构的实现

3.1二叉树的前中后序遍历

如果这个地方看不明白的可以去画递展开归图,如果画展开递归图还不明白就得去复习下C语言的递归章节了!

3.2求二叉树的节点个数

同理我们一样可以使用递归的方法:

int TreeSize(BTNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.3求二叉树的叶子节点个数

int TreeLeafSize(BTNode* root)
{
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3.4销毁二叉树

void DestoryTree(BTNode* root)
{
    if (root == NULL)
        return;
    DestoryTree(root->left);
    DestoryTree(root->right);

    free(root);
    root = NULL;
}

还剩一个二叉树的层序遍历,我把思路给大家讲一下,看完了可以自己去实现一下,如果实现不了或者有疑问随时可以联系我哦!

层序遍历:设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然 后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问 树的结点的过程就是层序遍历。

可以借助栈来实现,上一层带下一层的思路!

二叉树的实现到这里就结束了,可能小伙伴还有疑问,为什么二叉树没有增删查改,因为用二叉树进行增删查改是没意义的,搜索二叉树才是需要用到的,再者像复杂的VAL树和红黑树就得等到后期讲完C++配合着C++一起讲了,这只是非线性的入门!

到此这篇关于C语言二叉树的概念结构详解的文章就介绍到这了,更多相关C语言二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

  • C语言实现线索二叉树的前中后创建和遍历详解

    目录 1.结构 1.1初始化tag 2.基本操作 2.1先序创建二叉树 2.2.先序线索化 2.2.1.先序遍历 2.3.中序线索化 2.3.1中序遍历 2.4.后序线索化 2.4.1后序遍历 总结 1.结构 #include<stdio.h> #include<stdlib.h> #define false 0 #define true 1 using namespace std; typedef struct BTnode{ int data; struct BTnode *l

  • C语言关于二叉树中堆的创建和使用整理

    目录 一.堆的创建 1.向上调整算法建堆 2.向下调整算法建堆 二.堆排序 1.建堆 2.利用堆删除思想来进行排序 一.堆的创建 下面我们先看一段代码: void HeapSort(int* a, int size) { // 建小(da)堆 HP hp; HeapInit(&hp); // O(N*logN) for (int i = 0; i < size; ++i) { HeapPush(&hp, a[i]);// O(N)空间复杂度 } HeapPrint(&hp);

  • C语言二叉树的概念结构详解

    目录 1.树的概念及结构(了解) 1.1树的概念: 1.2树的表示法: 2.二叉树的概念及结构 2.1二叉树的概念 2.2特殊的二叉树 2.2二叉树的性质 2.3二叉树的顺序存储 2.4二叉树的链式存储 3.二叉树链式结构的实现 3.1二叉树的前中后序遍历 3.2求二叉树的节点个数 3.3求二叉树的叶子节点个数 3.4销毁二叉树 1.树的概念及结构(了解) 1.1树的概念: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • C++语言实现hash表详解及实例代码

    C++语言实现hash表详解 概要: hash表,有时候也被称为散列表.个人认为,hash表是介于链表和二叉树之间的一种中间结构.链表使用十分方便,但是数据查找十分麻烦:二叉树中的数据严格有序,但是这是以多一个指针作为代价的结果.hash表既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便. 打个比方来说,所有的数据就好像许许多多的书本.如果这些书本是一本一本堆起来的,就好像链表或者线性表一样,整个数据会显得非常的无序和凌乱,在你找到自己需要的书之前,你要经历许多的查询过程:而如果

  • C语言数据结构之堆排序详解

    目录 1.堆的概念及结构 2.堆的实现 2.1堆的向下调整算法 2.2堆的向上调整算法 2.3建堆(数组) 2.4堆排序 2.5堆排序的时间复杂度 1.堆的概念及结构 如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树(二叉树具体概念参见——二叉树详解)的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大

  • 基于JS脚本语言的基础语法详解

    JS脚本语言的基础语法:输出语法  alert("警告!");  confirm("确定吗?");   prompt("请输入密码");为弱类型语言: 开始时要嵌入JS代码:<script type="text/javascript"></script>: 关于写程序是需注意的基本语法: 1.所有的字符全都是英文半角的: 2.大部分情况下每条语句结束后要加分号: 3.每一块代码结束后加换行:4.程序前呼

  • Linux 下C语言连接mysql实例详解

    Linux 下C语言连接mysql实例详解 第一步: 安装mysql, 参考:http://www.jb51.net/article/39190.htm 第二步: 安装mysql.h函数库 sudo apt-get install libmysqlclient-dev 执行之后就可以看到/usr/include/MySQL目录了 然后开始我们的链接. 首先看我的数据库 mysql> show databases; +--------------------+ | Database | +----

  • C语言文件复制实例详解

    C语言文件复制实例详解 文件复制,在Linux中,将生成的read.o 重新文件拷贝一份复制到ReadCopy.o中,并且更改ReadCopy.o文件的操作权限.使其能够正常运行. 实例代码: #include <stdio.h> int main(){ FILE *r_file = fopen ("read.o","rb"); FILE *w_file = fopen ("ReadCopy.o","w"); ch

  • C语言 全局变量和局部变量详解及实例

    C语言 全局变量和局部变量详解 核心内容: 1.局部变量和全局变量 变量按照作用域分为:全局变量和局部变量 全局变量的作用域:从定义位置开始到下面整个程序结束. 局部变量的作用域:在一个函数内部定义的变量只能在本函数内部进行使用. OK,上面的效果用Java语言实现一下: public class App1 { public static int k = 10;//相当于全局变量 public static void main(String[] args) { int i = 10;//局部变量

  • JVM内存管理之JAVA语言的内存管理详解

    引言 内存管理一直是JAVA语言自豪与骄傲的资本,它让JAVA程序员基本上可以彻底忽略与内存管理相关的细节,只专注于业务逻辑.不过世界上不存在十全十美的好事,在带来了便利的同时,也因此引入了很多令人抓狂的内存溢出和泄露的问题. 可怕的事情还不只如此,有些使用其它语言开发的程序员,给JAVA程序员扣上了一个"不懂内存"的帽子,这着实有点让人难以接受.毕竟JAVA当中没有malloc和delete.没有析构函数.没有指针,刚开始接触JAVA的程序员们又怎么可能接触内存这一部分呢,更何况有不

  • C语言柔性数组实例详解

    本文实例分析了C语言柔性数组的概念及用法,对于进一步学习C程序设计有一定的借鉴价值.分享给大家供大家参考.具体如下: 一般来说,结构中最后一个元素允许是未知大小的数组,这个数组就是柔性数组.但结构中的柔性数组前面必须至少一个其他成员,柔性数组成员允许结构中包含一个大小可变的数组,sizeof返回的这种结构大小不包括柔性数组的内存.包含柔数组成员的结构用malloc函数进行内存的动态分配,且分配的内存应该大于结构的大小以适应柔性数组的预期大小.柔性数组到底如何使用? 不完整类型 C和C++对于不完

随机推荐