福建两学一做网站,第二波新冠感染高峰,战队头像logo免费自动生成器,html怎么做网站的背景志不立#xff0c;天下无可成之事。 ——王阳明 二叉树 1、树#xff1f;什么是树1、1、基本概念1、2、树的相关概念1、3、树的表示方式1、4、树的实际运用 2、二叉树#xff1f;只有两个分支吗#xff1f;2、1、基本概念2、2、二叉树的相关定义2、3、二叉树的相关性质2、4…志不立天下无可成之事。 ——王阳明 二叉树 1、树什么是树1、1、基本概念1、2、树的相关概念1、3、树的表示方式1、4、树的实际运用 2、二叉树只有两个分支吗2、1、基本概念2、2、二叉树的相关定义2、3、二叉树的相关性质2、4、二叉树的表示方式 3、总结 1、树什么是树
1、1、基本概念
树也是属于一种数据结构它是一种非线性的数据结构与栈队列和链表是不同的存在。 由n(n0)个有限的结点组成的具有层次关系的集合。至于为什么是树呢其实按照结构图来看把一颗二叉树的结构图倒过来就像一颗树了。 也就是像这样。 1、树都会有一个特殊的结点称为根节点根节点没有父节点 2、除去根节点之后其余的结点被分为M(M0)个互不相交的集合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的子孙) 森林由mm0棵互不相交的树的集合称为森林
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 那么则有n0n21 4、一个有n个节点的满二叉树那么它的深度为log(n1)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、总结
对于二叉树其实本质上的基础就只有那么多下面会推出二叉树的衍生的结构堆。对于二叉树的问题和操作都会在之后推出敬请期待。
