前言在接触树结构之前我们学习的数据结构都是基于线性存储的包括顺序表、链表、队列和栈等线性数据结构而树结构是我们认识的首个非线性数据结构它由n(n≥0)个有限节点组成具有明显的层次关系。之所以称为树是因为它的形态像一棵倒置的树根在上而叶在下。一、树的结构特征现实生活中的树木通常呈现底部生根、顶部生叶的形态如下图所示在数据结构中树的结构呈现出根在上方、叶在下方的特点如下图所示二、树的基本概念2.1树的定义树是由nn0个有限结点组成一个具有层次关系的集合应该满足如下特征①有一个特殊的结点称为根结点根结点没有前驱结点②除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合又是一棵结构与树类似的子树。③每棵子树的根结点有且只有一个前驱可以有0个或多个后继如下图所示2.2树的术语通过如下示意图来讲解树的相关概念和术语表述(1)树的节点如上图所示:A、B、C等字母代表树的各个节点特别地A是树的根节点。(2)节点的度一个结点含有的子树的个数称为该结点的度如上图所示:对于节点A而言有B、C、D为根节点的子树故A的度为3。(3)叶子结点或终端结点:不含有子树的节点被称为叶节点或者终端节点即度为0的结点如上图所示:J、F、K、L、H、I。(4)双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点如上图所示:A是B、C、D的父节点(5)孩子结点或子结点:与父节点相对应如上图所示B、C、D是A的子节点。(6)树的度树的度是树内所有结点中度数值最大的那个结点的度用数学表达式表示为树的度 max ( 所有结点的度 )。(7)结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推。(8)树的高度或深度树中结点的最大层次。(9)森林由mm0棵互不相交的树的集合称为森林2.3树的存储树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存其值又要表示结点和结点之间的关系实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里介绍一种最为常用的表示方法孩子兄弟表示法。typedef int DataType; struct Node { struct Node* firstChild1; // 第一个孩子结点 struct Node* pNextBrother; // 指向其下一个兄弟结点 DataType data; // 结点中的数据域 };如下图所示三、二叉树3.1二叉树的概念二叉树是一棵特殊的树是一个n(n0)个节点的有限集合其有如下特征①每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)②由一个根结点加上两棵别称为左子树和右子树的二叉树组成③二叉树的子树有左右之分其次序不能任意颠倒3.2二叉树的图示从上图可以看出1. 二叉树不存在度大于2的结点2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的3.3特殊的二叉树3.3.1、满二叉树满二叉树指每一层的节点数量均达到最大值的二叉树。具体而言若某二叉树的深度为h且其节点总数为2^h-1则该树即为满二叉树。对于一棵满二叉树而言假设其高度为h节点总数为N第一层有2^0个节点第二层有2^1个节点第三层有2^2个节点......第h-1层有:2^(h-2)个节点第h层有2^(h-1)个节点用N表示这棵二叉树的总节点数则有N2^02^12^2...... 2^(h-2)2^(h-1) 2^h-1。所以也可得出hlogN1对于一棵二叉树而言其深度可以被近似为h ≈ logN3.3.2、完全二叉树完全二叉树除最后一层外每一层的节点数均达到最大值最后一层的节点从左到右连续排列缺失的节点只能在右侧。对于完全二叉树满足如下特征①叶子节点仅可能出现在最下两层且最下层叶子一定靠左集中。② 适合用数组存储无需额外空间记录指针通过索引即可计算父子节点位置。③不存在只有右子节点而无左子节点的节点右子节点存在的前提是左子节点已存在。注满二叉树也被视为特殊的完全二叉树。3.4二叉树的性质二叉树的性质围绕节点数、深度、子树关系及特殊类型展开核心是 “每个节点最多 2 个子节点” 的结构约束以下是系统总结3.4.1、所有二叉树的性质①节点数与度数关系若总节点数为 N度为 0叶子、1、2 的节点数分别为 n₀、n₁、n₂则 N n₀ n₁ n₂且 n₀ n₂ 1叶子节点数比度为 2 的节点数多 1。推导过程假设二叉树有N个结点从总结点数角度考虑N n0 n1 n2 ①从边的角度考虑N个结点的任意二叉树总共有N-1条边因为二叉树中每个结点都有父节点根结点没有父节点每个节点向上与其父节点之间存在一条边因此N个结点的二叉树总共有N-1条边。因为度为0的结点没有孩子故度为0的结点不产生边;度为1的结点只有一个孩子故每个度为1的结点产生一条边;度为2的结点有2个孩子故每个度为2的结点产生两条边所以总边数为 n12*n2故从边的角度考虑N-1 n1 2*n2 ②结合① 和 ②得n0 n1 n2 - 1 n1 2*n2 即n0 n2 1②深度与节点数上限若深度为 k根节点深度为 1则该二叉树最多有 2ᵏ - 1 个节点满二叉树的情况最少有 k 个节点。二叉树最多节点的情况第 1 层 最多有2^0 个节点。第 2 层最多有2^1个节点。第 3 层最多有2^2个节点。......第 k 层最多有 2^(k-1) 个节点。最多节点的总数为:N 2^0 2^1 2^2 ... 2^(k-2) 2^(k-1) 2^k - 1个节点。二叉树最少节点的情况每层只有一个节点则k层有k个节点。③层数与节点分布第 k 层根为第 1 层最多有 2^(k-1) 个节点最少有 1 个节点。3.4.2、满二叉树的性质①所有层的节点数均达到最大值即第 k 层有 2^(k-1) 个节点总节点数 n 2ᵏ - 1k 为深度。②叶子节点全部在最底层且不存在度为 1 的节点n₁ 0叶子节点数 n₀ 2ᵏ⁻¹。③假设树的深度 k 则总节点数 n 2ᵏ - 1深度 k ≈ log₂n。3.4.3、完全二叉树的性质①节点总数 n 满足( 2ᵏ⁻¹ - 1 ) 1 n 2ᵏ-1k 为深度深度 k ≈ log₂n。②数组存储索引规则Ⅰ. 父节点 i 的左子节点为 2*i、右子节点为 2*i1Ⅱ. 子节点 j 的父节点为 j / 2索引从 1 开始。③叶子节点索引范围为 n/2 1 到 n非叶子节点为 1 到 n/2无 “只有右子节点” 的情况。④对于完全二叉树度为1的节点只有1个或者0个。四、树与二叉树的转换4.1 普通树转换为二叉树4.1.1核心方法①加线连兄弟在所有兄弟节点之间加一条连线。②抹线断父子保留最左边的孩子长子抹掉其他孩子③旋转理层次以树的根节点为轴心将整棵树顺时针旋转45度使其看起来像一棵标准的二叉树。简记兄弟相连留长子4.1.2 图解演示如图所示一棵普通树操作一兄弟间加线操作二保留长子③以根为轴心顺时针旋转45°4.2 二叉树转换为普通树4.2.1核心方法①加线认父亲对于某个节点比如 P如果它有左孩子L那么把 L 的所有右链上的节点即 L 的兄弟们都与 P 用线连起来。②抹线断兄弟抹掉二叉树中所有节点与它右孩子之间的连线。③旋转理层次整理结构使其恢复为普通树的层次。简记为左孩右右连双亲去掉原来右孩线4.2.2图解演示如图所示有一棵二叉树操作一加线认父亲操作二抹线断兄弟③旋转理层次4.3 森林转换为二叉树4.3.1核心方法①各树自转先把森林中的每一棵树各自转换为二叉树②根根相连将每棵树的根节点用线连起来③唯一树根第一棵树的根节点就是转换后整棵二叉树的根节点。简记树变二叉根相连4.3.2图解演示如图所示有如下森林操作一各树自转操作二根根相连操作三唯一树根4.4二叉树转换为森林4.4.1核心方法①抹线断开树与树的联系沿着二叉树根节点的右链一直走下去把这根链上的所有连线全部剪断。②提取确定每棵树的根断开后右链上的每一个节点现在都成为了独立的二叉树的根节点。③还原各自变回普通树对这散落出来的每一棵小二叉树分别执行 “二叉树转普通树” 的操作简记去掉根部右孩线孤立二叉再还原4.4.2图解演示如图所示一棵二叉树操作一抹线断开树与树的联系操作二提取确定每棵树的根操作三还原各自变回普通树五、小试牛刀5.1试题一1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树B 200C 198D 199解析对于任何一棵二叉树都满足这样一个性质n0度为0的节点 n2度为2的节点 1故而叶子节点即度为0的节点 个数为1991200B选项符合题意。5.2试题二2.下列数据结构中不适合采用顺序存储结构的是 A 非完全二叉树B 堆C 队列D 栈解析B、 堆基于完全二叉树连续排列的特性故而可以采用顺序结构存储C、队列对于循环队列采用顺序存储结构D、栈一般基于数组实现采用顺序结构答案为A5.3试题三3.在具有 2n 个结点的完全二叉树中叶子结点个数为 A nB n1C n-1D n/2解析对于任何一棵二叉树而言其节点总数N由度为0的节点、度为1的节点、度为2的节点所组成Nn0n1n2任意一棵二叉树满足如下性质n0n21故而2n n0 n1 n0-1 , 当且仅当 n11 时左边为偶数且右边为偶数 , 所以n0n。答案为:A5.4试题四4.一棵完全二叉树的结点数位为531个那么这棵树的高度为 A 11B 10C 8D 12解析对于一棵完全二叉树而言假设这棵树的高度为k则其节点的范围2ᵏ⁻¹ ~ 2ᵏ - 1答案为B5.5试题五5.一个具有767个结点的完全二叉树其叶子结点个数为A 383B 384C 385D 386解析对于任何一棵二叉树而言其节点总数N由度为0的节点、度为1的节点、度为2的节点所组成Nn0n1n2任意一棵二叉树满足如下性质n0n21对于N767 则有767n0n1n0-1 当且仅当n1等于0时才满足左右两边为奇数所以n10答案为B: n0384既然看到这里了不妨关注点赞收藏感谢大家若有问题请指正。