C语言深入浅出解析二叉树
目录
- 树概念及结构
- 相关概念
- 树的表示
- 树在实际中的运用（表示文件系统的目录树结构）
- 二叉树概念及结构
- 概念
- 需要注意的特殊二叉树
- 二叉树的性质
- 二叉树的存储结构
- 顺序存储
- 链式存储
- 总结
树概念及结构
树是一种 非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合
把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
注意：
- 有一个特殊的结点，称为根结点，根节点没有前驱结点
- 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <=m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继 因此，树是递归定义的。
如图：
注意：
- 树形结构中，子树之间不能有交集，否则就不是树形结构
- 除了根节点外，每个节点有且只有一个父节点
- 一棵树N个节点的树有N-1条边
相关概念
如图：
- 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
- 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
- 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点
- 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
- 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
- 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙 森林：由m（m>0）棵互不相交的树的集合称为森林；
树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间
的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的 孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
如图：
树在实际中的运用（表示文件系统的目录树结构）
二叉树概念及结构
概念
- 二叉树由一个根节点加上左子树和右子树组成：
- 二叉树度最大为2（度可以为0,1,2）
- 二叉树的子树有左右之分，次序不能颠倒（有序树）（没有左树，一定没有右树；有左树，不一定有右树）
需要注意的特殊二叉树
满二叉树：
一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树
也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树
完全二叉树：
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的（特殊的完全二叉树）
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
二叉树的性质
- 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有2^（i-1）个结点
- 若规定根节点的层数为 1 ，则 深度为 h的二叉树的最大结点数是2^h-1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2（n+1）（是log以2为底，n+1为对数）
二叉树的存储结构
存储结构类型：
顺序存储
顺序结构存储就是使用 数组来存储 ，一般使用数组只适合表示完全二叉树（不完全二叉树有空间的浪费）而现实中使用中只有堆才会使用数组来存储
注：二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树
如图：
链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。
例：
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}；
总结
这只是二叉树的基本知识，之后我们还会详细解析二叉数的递归实现和有关题目。
到此这篇关于C语言深入浅出解析二叉树的文章就介绍到这了,更多相关C语言 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C语言实现二叉树层次遍历介绍
目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree
-
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语言中二叉树的后序遍历详解
目录 一.二叉树的后序遍历.(递归) 二.二叉树的后序遍历(迭代) 总结 首先我们从两个方面讲解二叉树的后序遍历(递归+迭代) 一.二叉树的后序遍历.(递归) 思想: 首先我们从二叉树的根节点开始先遍历其左孩子,①接着同样继续遍历其左孩子的左孩子,直到某个左孩子节点的左孩子为NULL时,②开始遍历其右孩子,如果其为NULL则访问该节点的值域,并返回其双亲节点重复第二步的操作,如果其不为NULL则以该节点为根节点重复第一步的操作.直到访问完所有节点时结束递归. 代码: void BTreePost
-
C语言平衡二叉树详解
目录 调整措施: 一.单旋转 二.双旋转 AVL树的删除操作: 删除分为以下几种情况: 1.要删除的节点是当前根节点T. 2.要删除的节点元素值小于当前根节点T值,在左子树中进行删除. 3.要删除的节点元素值大于当前根节点T值,在右子树中进行删除. 总结 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.这个方案很好的解决了二叉查找树退化成链表的
-
C语言数据结构系列篇二叉树的遍历
目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.
-
C语言数据结构之二叉链表创建二叉树
目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右
-
C语言二叉树的遍历示例介绍
在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef
-
C语言数据结构之二叉树详解
目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵
-
C语言深入浅出解析二叉树
目录 树概念及结构 相关概念 树的表示 树在实际中的运用(表示文件系统的目录树结构) 二叉树概念及结构 概念 需要注意的特殊二叉树 二叉树的性质 二叉树的存储结构 顺序存储 链式存储 总结 树概念及结构 树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合 把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 注意: 有一个特殊的结点,称为根结点,根节点没有前驱结点 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1.T2.
-
C语言数据结构详细解析二叉树的操作
目录 二叉树分类 二叉树性质 性质的使用 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 求二叉树的节点数 求二叉树叶子结点个数 求二叉树的最大深度 二叉树的销毁 二叉树分类 满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树.也可以理解为每一层的结点数都达到最大值的二叉树. 完全二叉树 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下.从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为
-
Java 深入浅出解析面向对象之抽象类和接口
目录 抽象类 声明抽象类 声明抽象方法 案例 使用规则 接口 声明接口 案例 接口特性 抽象类和接口的区别 抽象类 java语言,声明类时 abstract class Db{} 说明Db类为抽象类. java语言中,抽象方法是说没有方法的实现(方法体)此方法为抽象方法,只有抽象类和接口中才可以有抽象方法. 声明抽象类 声明抽象类很简单,加个abstract关节字就行. public abstract class AA { } 声明抽象方法 在抽象类中声明一个抽象方法,抽象方法没有方法体,就是说
-
C语言数据结构之二叉树的非递归后序遍历算法
C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,
-
C语言中计算二叉树的宽度的两种方式
C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo
-
C语言实现线索二叉树的定义与遍历示例
本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN
-
C语言基础解析之分支与循环语句
目录 - if语句:if(表达式) 悬空else问题 - switch语句 要注意的细节 switch中的的default子句: - while循环语法结构 - for循环语法结构 - do while循环 循环练习题 - 题目一(阶乘) - 题目二(阶乘和) - 题目三(二分查找) - 题目四(两边往中间渐变) - 题目五(密码登录) - 题目六(猜数字游戏) - goto语句 - getchar与putchar用法 - if语句:if(表达式) // 括号里面放一个表达式 //表达式的结果
-
深入浅出解析Java ThreadLocal原理
目录 1.了解ThreadLocal 简介 使用 2.源码解析 – 探究实现思路 threadLocals变量与ThreadLocalMap set(T value) 方法 get() 方法 remove() 方法 实现思路总结 3.InheritableThreadLocal与继承性 ThreadLocal的不可继承性 InheritableThreadLocal实现继承性的源码剖析 如何理解这个继承性 总结 4.存在的内存泄露问题 使用强引用会如何? 使用弱引用会如何? set().get(
-
C语言 链式二叉树结构详解原理
目录 前言 二叉树节点声明 二叉树的遍历 构建二叉树 1.前序遍历 2.中序遍历 3.后序遍历 二叉树节点的个数 二叉树叶子节点的个数 二叉树第K层节点个数 二叉树的高度/深度 二叉树查找值为x的节点 整体代码 前言 二叉树不同于顺序表,一颗普通的二叉树是没有增删改查的意义.普通的二叉树用来存储数据是不方便的.但是二叉树的一些基本实现结构,例如前序遍历,中序遍历...等等都是对我们学习更深层次的二叉树打下夯实的基础. 二叉树节点声明 typedef char BTDataType; typede
-
C语言 深入浅出讲解指针的使用
目录 一.利用指针倒序字符串 二.题目实例 三.总结 一.利用指针倒序字符串 void _reversal(char* left, char* right) { while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } 通过上述代码不难看出,left与right分别代表一个字符数组的首端和尾端,通过中间变量 tmp进行首尾交换,left++中的left是char*类型,同