上海珍岛网站建设,社区团购平台排名,最新网站建设常见问题,客户管理系统内容Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 本章来记录下最近新学习的树的基础概念以及基础公式大概会分为几个章节讲完。
目录
1.初识树
树的相关定义:
在结构中的存储:
2.二叉树的概念
特殊的二叉树:
满二叉树:
完全二叉树:
二叉树公式: 题目:
完结撒花 1.初识树
树之所以被称为树是因为
现实生活中的树是长这样的 数据结构中树是长这样的看起来就像将其倒过来而形成的。所以在数据结构中我们把长这样形状由一个根若干个节点与叶子组合起来且各个节点之间有且只有一条路到达根称为树 除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继。 也就是说每一颗子树都是不相交的。 这里引入一些概念 除根节点外每个节点有且只有一个父节点 一颗N个节点的树有N-1条边 树的相关定义:
节点的度:该节点拥有的子树个数.如A为6
叶子:度为0的节点
父亲节点/孩子节点:若一个节点有子节点,则该节点为子节点的父亲节点,反之该子节点为孩子节点
兄弟节点:两个拥有同样父亲的节点
节点层次/树的深度(高度):该节点距离根的层数称为层次,根为第一层.深度为最大的层次
节点祖先:从根到该节点所经分治的所有节点.例如A为所有节点的祖先
节点子孙:与祖先定义相反:以某节点为根,则其所有子节点都为其节点子孙 在结构中的存储:
因为树的定义为:一个节点可以拥有若干个子节点.所以我们没有办法通过一个节点来直接记录其所有子节点.所以我们通常才用以下这种模式来记录. 也就是一个节点中有两个指针分别指向子节点与其兄弟节点.还有一个变量来存储数据
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};2.二叉树的概念
相比于树,二叉树具有以下特点:每个数的度为[0,1,2]三种可能,也就是一个节点最多有两个子节点.
且二叉树的两个节点顺序不能颠倒,具有左右节点的概念 特殊的二叉树:
满二叉树:
同一层下都有/无子节点,在概念上来看就是,节点总数为2^k-1其就为满二叉树 完全二叉树:
除去最后一层,为满二叉树,最后一层从左向右分布子节点.满二叉树为特殊的完全二叉树 二叉树公式:
根的深度为1,部分教材上为0,但若这棵树是空树(没有节点)按照教材上的定义,此时深度还是为0嘛?所以统一按1来计算
双亲节点计算:(child-1)/2
左儿子:(parent*21)
右儿子:(parent*22) 对于一颗非空二叉树,其一层上最多有2^(h-1)个节点,反之其深度为log(n1)
深度为h的二叉树,其节点最大总数为2^h-1,
二叉树度为0的节点为n0,度为1的节点为n1,度为2的节点为n2,则有以下关系:n0n21 题目: 用到n0n21的公式,则n0200 用到n0n21的公式,2nn21n2n1 根据完全二叉树的定义,n1只会有0个或者1个.所以n0n
完结撒花 本篇博客的内容【数据结构:树的概念】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
