网站开发国内外研究背景,广告公司怎么设置网站关键字,如何配置iis网站,重庆给商家企业做网站点击蓝字关注我们前言在之前的数据结构学习中#xff0c;我们学习了顺序表、链表、栈、队列这几种结构它们都是用链表或者数组的方式来实现的#xff0c;主要考察我们对结构体的运用今天让我们来学习一个新的数据结构#xff0c;也就是下面这副图里面的树啊不好意思#xf… 点击蓝字关注我们前言在之前的数据结构学习中我们学习了顺序表、链表、栈、队列这几种结构它们都是用链表或者数组的方式来实现的主要考察我们对结构体的运用今天让我们来学习一个新的数据结构也就是下面这副图里面的树啊不好意思图拿错了????是下面这个才对1.什么是树1.1树的概念树是一种非线性的数据结构它是由n个有限节点组成的具有一定层次关系的集合。把它叫做树是因为它看起来的确像一个树的根部当然也可以理解为是树干在上树叶在下的结构有一个特殊的节点被称为根节点也就是树的开头除了根节点外其余节点都是,个互不相交的集合。每一个集合都是一颗与树的结构类似的子树每一个节点只能有一个前驱但是可以有很多个后驱 因此树是递归定义的树中的子节点不能有交集上图中的B节点不能有G这个孩子因为G已经有父母C了同理G节点也不能同时拥有两对父母子节点之间也不能相连如E和F不能相连1.2树的相关知识点节点的度一个节点含有的子树的个数称为该节点的度如下图A的度为6叶节点或终端节点度为0的节点称为叶节点图中B、C、H、I…等节点为叶节点非终端节点或分支节点度不为0的节点如上图中D、E、F、G…等节点为分支节点简单的说就是有娃的节点就是分支节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点如上图D是H的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点如上图H是D的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点如下图P、Q是兄弟节点树的度一棵树中最大的节点的度称为树的度示例中树的度为6即A的度节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次示例中树的高度为4堂兄弟节点双亲在同一层的节点互为堂兄弟如下图H、I互为兄弟节点节点的祖先从根到该节点所经分支上的所有节点示例中A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为该节点的子孙。示例中所有节点都是A的子孙森林由mm0棵互不相交的树的集合称为森林多个不相交的树就是森林1.3树的代码表示表示树的方式有很多种比如下面这种#define N 5 //指定树的度为5
struct TreeNode
{int data;struct TreeNode* subs[N];//用指针数组存放孩子节点的指针
};但这种方法不够优给大家展示一个用的最广泛的方法——孩子兄弟表示法typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};通过这种方法父亲节点只需要保存它的第一个娃其他娃就让大娃的兄弟节点来找也就是家长只用管老大老大管老二老二管老三依次往下……实际写代码的结构大概是下图这样2.二叉树在实际中二叉树是使用较多的一种树的结构2.1概念二叉树是度为2的树它是一个特殊的树二叉树不存在度大于2的节点二叉树是有序树它的娃子树有左右之分次序不能颠倒所以二叉树都是由下面各类节点组成的树2.2特殊的二叉树满二叉树如果每一个层的节点数都达到最大值那这个二叉树就是满二叉树。也就是说满二叉树的层数为k且节点总数是2k-1满二叉树的节点数是一个等比数列公式2 0 2 1 2 2 . . . 2 k − 1 1 ∗ ( 1 − 2 k ) / ( 1 − 2 ) 2 k − 1 2^02^12^2...2^{k-1}1*(1-2^k)/(1-2)2^k -1 202122...2k−11∗(1−2k)/(1−2)2k−1完全二叉树完全二叉树是效率很高的数据结构。对于深度为K有n个节点的二叉树当且仅当每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称为完全二叉树。简单说来完全二叉树的最后一层不一定满但必须要从左到右连续满二叉树是一个特殊的完全二叉树2.3二叉树的性质若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2(i-1)个结点若规定根节点的层数为1则深度为h的二叉树的最大结点数是2h-1对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2则有n0 n21若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2(n1) 。(ps是log以2为底n1为对数)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子2.4几个选择题1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为
A 不存在这样的二叉树
B 200 √
C 198
D 199
//叶子节点的数量 总比度为2的节点多12.在具有 2n 个结点的完全二叉树中叶子结点个数为
A n √
B n1
C n-1
D n/2
//N0N1N22n
//2N0N1-12n
//N1只有0和1两种可能因为n为整数2n为偶数所以2N02nN0n3.一棵完全二叉树的节点数位为531个那么这棵树的高度为
A 11
B 10 √
C 8
D 12
//假设高度是h
//完全二叉树节点最多2^h -1
// 最少2^(h-1)-1 1
//可以通过这两个公式推断出h103.二叉树的存储结构二叉树一般可以使用两种结构存储一种顺序结构一种链式结构3.1顺序存储顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。现实使用中只有堆才会使用数组来存储下一篇博客会带大家认识堆这个特殊的树形结构和内存里面那个堆????没啥关系哈看到这张图你肯定想问如果用数组结构存储那还怎么还原出一颗树????呢这里我们需要理解物理存储和逻辑结构的关系二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树那怎么计算这种情况下的父亲和娃呢leftchildparent*21rightchildparent*22parent(child-1)/2怎么样是不是忽然感觉妙级了3.2链式存储这就就没啥好说的啦使用一个简单的二叉链就能构成二叉树typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft; // 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点的值
}结语嘿嘿嘿本篇博客到这里就结束啦*声明本文于网络整理版权归原作者所有如来源信息有误或侵犯权益请联系我们删除或授权事宜。戳“阅读原文”我们一起进步
