让二叉树无处可逃

发布时间:2024年01月23日

志不立,天下无可成之事。 ——王阳明


1、树?什么是树

1、1、基本概念

树也是属于一种数据结构,它是一种非线性的数据结构,与栈,队列和链表是不同的存在。
由n(n>=0)个有限的结点组成的具有层次关系的集合。至于为什么是树呢?其实按照结构图来看,把一颗二叉树的结构图倒过来就像一颗树了。在这里插入图片描述

在这里插入图片描述
也就是像这样。
1、树都会有一个特殊的结点,称为根节点,根节点没有父节点
2、除去根节点之后,其余的结点被分为M(M>0)个互不相交的集合T1,T2,Tm,其中每一个集合又是一棵结构类似的子树。
3、因此,树是递归定义的。(在后面的关于树之类的问题上,递归的解决方法占很大一部分)

注意:根据观察,其实真正的树,根和根之间不会相互交错。那计算机的树其实也是,子树也是不能有交集的,否则将不会是树的结构。在这里插入图片描述

1、2、树的相关概念

在这里插入图片描述

:一个节点的子树的个数。(例如A的度就是6)
叶节点或终端节点:度为0的节点称为叶子节点(就例如B,C,等等)
分支节点或非终端节点:度不为0的节点(例如 D,E,J等)
双亲结点或父节点:若一个结点有子节点,则这个结点称为其子节点的父节点:(例如A是B的父节点)
孩子结点或子节点:一个节点含有子树的根结点称为该子节点的父节点:(例如B是A的孩子节点)
兄弟节点:具有相同父节点的节点互称为兄弟节点;(B、C是兄弟节点)
树的度:一棵树中,最大的节点的度称为树的度;(树的度为6)
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次; (例如这棵树的高度为4)
堂兄弟节点:双亲在同一层的节点互为堂兄弟;(H、I互为兄弟节点)
节点的祖先:从根到该节点所经分支上的所有节点;(A是所有节点的祖先)
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。(所有节点都是A的子孙)
森林:由m(m>0)棵互不相交的树的集合称为森林;

1、3、树的表示方式

相对于线性表的表示,由于树的不确定的性质,树的存储表示会相对比较麻烦,不只是需要保存树中的数值,还要保证节点和节点之间的关系。由于树的复杂性,所以树的表示方法也会出现多元化,就比如:双亲表示法,孩子表示法,孩子双亲表示法以及孩子兄弟表示法等。在这里不方便多说,就简单的介绍几种常用的方法孩子兄弟表示法(也是一个很妙的表示方法)

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

在这里插入图片描述
这就是通过孩子找兄弟,让父节点只指向一个节点,而处于同一层的都通过,带头的兄弟来找到。

下面的这个就是我简单的写一下其余的表示方法,因为相对于其余的方法,我对于孩子兄弟法还是更喜欢一点的。
在这里插入图片描述
这里的我想到的问题,在这篇文章有详细的讲解,关于指针的,如果不熟悉,可以再看一下

1、4、树的实际运用

在这里插入图片描述

2、二叉树?只有两个分支吗?

2、1、基本概念

二叉树也是一棵节点的有限集合
1、可能为空
2、由根节点加上两棵左子树和右子树的二叉树构成。在这里插入图片描述
1、二叉树不存在度大于2的节点
2、二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序的树

二叉树也可以通过递归的方式来组成,二叉树也只能分为这几种情况在这里插入图片描述

2、2、二叉树的相关定义

特殊的二叉树
==1、满二叉树:==一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k)-1,则它就是满二叉树。
==2、完全二叉树:==完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树

2、3、二叉树的相关性质

二叉树很类似与我们高中学习的生物中的关于细胞分裂的公式。(下面的公式都是相当于根节点的层数是1的情况下)
1、一棵非空的二叉树的第i层上的节点个数最多有2^(k-1)个节点。
2、深度为h的二叉树最大节点数为2^h-1。
3、如果度为 0 的节点个数为 n0 ,度为 2 的节点个数为 n2 ,那么则有n0=n2+1
4、一个有n个节点的满二叉树,那么它的深度为log(n+1),log是以2为底
(ps:明天出一个关于树相关的问题集合,感兴趣的记得关注!)

2、4、二叉树的表示方式

看过树的介绍,不难发现,二叉树相对与树的结构多样,规则变化,二叉树相对简单,所以对于二叉树的存储方式来说也是更简单一点
1、顺序存储
顺序结构就是用数组来存储,一般来说,数组的使用**只适合表示完全二叉树,**对于不是完全二叉树时会有空间的浪费。二叉树顺序存储在物理结构上是数组,但是逻辑结构上是一棵二叉树。
正常来说,这种的数组结构都是大部分存储 堆
在这里插入图片描述
2、链式存储
用链表来表示一棵二叉树
在这里插入图片描述
在这里插入图片描述
转换成代码的形式,也就是相当于这样

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; // 当前节点值域
};

3、总结

对于二叉树其实本质上的基础就只有那么多,下面会推出二叉树的衍生的结构,堆。对于二叉树的问题和操作都会在之后推出,敬请期待。

文章来源:https://blog.csdn.net/2301_79194984/article/details/135769263
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。