网站维护收费标准,用一个域名免费做网站,metro风格网站,网页制作入门与进阶文章目录 一、树1. 树的概念和结构2. 树的相关术语 二、二叉树1. 概念与结构2. 满二叉树3. 完全二叉树4. 二叉树的性质5. 二叉树的存储结构 一、树
1. 树的概念和结构
之前我们学习了线性表#xff0c;今天我们再来接触一种全新的数据结构——树。 树是一种非线性的数据结构… 文章目录 一、树1. 树的概念和结构2. 树的相关术语 二、二叉树1. 概念与结构2. 满二叉树3. 完全二叉树4. 二叉树的性质5. 二叉树的存储结构 一、树
1. 树的概念和结构
之前我们学习了线性表今天我们再来接触一种全新的数据结构——树。 树是一种非线性的数据结构它是有有限个结点组成的一个具有层次关系的结构。把它称为树是因为它看起来就像一棵倒挂的树根朝上而叶朝下。
现实中的树
树形结构 关于数据结构树
它有一个根结点根结点没有前驱结点如上图的A就是这棵树的根结点。除根结点外其余结点被分为有限个互不相交的集合每一个集合都是一棵子树每棵子树有且只有一个前驱结点可以没有后继或多个后继结点。因此树是递归定义的。子树不能有交集否则就不是树形结构。一棵有n个结点的树有n - 1条边
2. 树的相关术语 父结点/双亲结点若一个结点有子结点则这个结点是其子节点的父结点。如上图A是B、C、D、E的父结点C是H的父结点。 子结点/孩子结点若一个结点含有子树则子树的根结点称为该结点的子结点。如上图B、C、D、E是A的子结点K是F的子结点。 结点的度一个结点有几个孩子它的度就是多少。如上图A的度是4C的度是2M的度是0。 树的度一棵树中所有结点的度中的最大值就是这棵树的度。如上图这棵树的度是6。 叶子结点/叶节点/终端节点度为0的结点。如上图K、G、L、M、N、D、I、O都是叶子结点。 分支结点/非终端结点度不为0的结点。如上图A、B、C、E、F、H、J都是分支结点。 兄弟结点具有相同父结点的结点互称为兄弟结点。如上图B、C、D、E互称为兄弟结点I、J互称为兄弟结点。 结点的层次从根结点开始定义根结点在第1层根结点的子结点在第2层以此类推。如上图D在第2层、N在第4层。 树的高度/深度树中结点的最大层次。如上图这棵树的高度为4。 路径从一个结点到另一个结点的结序列结点之间只能通过父子关系连接、如上图A到L的路径为A-C-H-LG到O的路径为G-C-A-E-J-O。 结点的子孙以一个结点为根结点的子树中的所有结点都称为该结点的子孙。如上图除A外所有结点都是A的子孙I、J、O都是E的子孙。 结点的祖先从根结点到一个结点所经分支上的所有结点称之为该节点的祖先。如上图A是除自己外所有结点的祖先A、B、F都是K的祖先。 森林若干棵互不相交的树的集合称为森林。 二、二叉树
1. 概念与结构
在树形结构中我们最常用的就是二叉树。二叉树由根结点、左子树、右子树组成或者为空。 二叉树的特点是
二叉树的度一定不大于2也就是二叉树的每一个结点的子结点不多于2个。二叉树的子树有左右之分次序不能颠倒。
2. 满二叉树
满二叉树是二叉树的特殊情形。一个二叉树如果每一层的结点数都达到最大值它就是满二叉树。也就是除叶子结点外每一个结点都有两个子结点。不难计算如果一个满二叉树的高度为k则它的结点总数是2k -1等比数列求和 3. 完全二叉树
完全二叉树是由满二叉树引出来的。 我们首先要知道二叉树中结点的编号方式从上到下从左到右。从第一层开始从左到右从0开始依次编号第一层编完第二层从左到右编号……直到所有结点编号完。 对于有n个结点的二叉树若每一个结点都与深度相同的满二叉树的编号从0到n的结点一一位置对应这个二叉树就是完全二叉树满二叉树也是完全二叉树。 也可以理解为完全二叉树的每一层结点个数达到最大最后一层不一定达到最大且结点是从左到右依次排列的。 比如以下这些都是完全二叉树
4. 二叉树的性质
非空二叉树的第i层上最多有2i-1个结点深度为h的二叉树的结点数不多于2h-1具有n个结点的满二叉树的深度为log2(n1)
5. 二叉树的存储结构
二叉树既可以用顺序结构存储也可以用链式结构存储我们之后都要学习。 本篇完感谢阅读
