Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
本章来记录下最近新学习的树的基础概念以及基础公式，大概会分为几个章节讲完。
1.初识树
树之所以被称为树是因为
现实生活中的树是长这样的：
数据结构中树是长这样的，看起来就像将其倒过来而形成的。所以在数据结构中，我们把长这样形状（由一个根，若干个节点与叶子组合起来，且各个节点之间有且只有一条路到达根）称为树
除根节点外，其余结点被分成M(M>0)个互不相交的集合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*2+1)
右儿子:(parent*2+2)
对于一颗非空二叉树,其一层上最多有2^(h-1)个节点,反之其深度为log(n+1)
深度为h的二叉树,其节点最大总数为2^h-1,
二叉树度为0的节点为n0,度为1的节点为n1,度为2的节点为n2,则有以下关系:n0=n2+1
题目:
用到n0=n2+1的公式,则n0=200
用到n0=n2+1的公式,2n=n2+1+n2+n1 根据完全二叉树的定义,n1只会有0个或者1个.所以n0=n
完结撒花：
🌈本篇博客的内容【数据结构:树的概念】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
