网站的概念,各个视频网站怎么做原创作者,优秀画册设计欣赏,西安代做毕业设计网站目录
1、二叉树概念及结构
1.1、概念
1.2、特殊的二叉树
1.3、二叉树的性质
1.4、二叉树的存储结构
1.4.1、顺序存储 -- 看截图#xff1a;二叉树的顺序存储
1.4.2、链式存储 -- 非完全二叉树用这种方式存储
2、二叉树的遍历
2.1、前序、中序以及后序遍历2.2、层序遍…目录
1、二叉树概念及结构
1.1、概念
1.2、特殊的二叉树
1.3、二叉树的性质
1.4、二叉树的存储结构
1.4.1、顺序存储 -- 看截图二叉树的顺序存储
1.4.2、链式存储 -- 非完全二叉树用这种方式存储
2、二叉树的遍历
2.1、前序、中序以及后序遍历2.2、层序遍历 1、二叉树概念及结构
1.1、概念
一棵二叉树是结点的一个有限集合该集合:
为空只有一个根节点由一个根节点加上两棵别称为左子树和右子树的二叉树组成
二叉树的概念 从图中可看出
二叉树不存在度大于2的结点 -- 二叉树不一定度为2(可能是空树或者只有一个孩子)但度为2的树可以认为是二叉树二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
二叉树的几种形式 补充普通二叉树的增删查改没有价值 原因用二叉树这么复杂的结构来存储数据太麻烦不如用链表、数组...
补充任何一颗二叉树都要拆解成三部分来看 1.根 2.左子树 3.右子树 1.2、特殊的二叉树
1.满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是2^k-1(等比数列之和公比为2)则它就是满二叉树。-- 就是每一层都是满的。2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。-- 就是前K-1层都是满的最后一层不一定满(但至少有一个)但是从左到右必须连续。注完全二叉树的结点数2^(k-1) ~ 2^k-1。
注意满二叉树是一种特殊的完全二叉树。 1.3、二叉树的性质
1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。 2.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1(就是满二叉树的结点个数)。 3.对任何一棵二叉树如果度为0的节点(叶结点)个数为n0度为2的分支结点个数为n2则一定有n0n21。(举几个栗子就能找到规律了)4.若规定根节点的层数为1具有n个结点的满二叉树的深度hlog2(n1)。 5.对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有
若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点。若2i1n左孩子序号2i12i1n否则无左孩子。若2i2n右孩子序号2i22i2n否则无右孩子。
6.对于完全二叉树来说度为1的结点个数只有 1 个或 0 个。 7.如果一颗完全二叉树的结点个数为奇数说明度为 1 的结点个数为 0。 为偶数说明度为 1 的结点个数为 1。
1.4、二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
1.4.1、顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
补充 父子结点间的下标有一个规律关系 leftchild parent*21 rightchild parent*22 parent (child-1)/2 // 无所谓是左孩子还是右孩子都行 1.4.2、链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链(红黑树、AVL树)。 2、二叉树的遍历
2.1、前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。 所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 -- 根左右 2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 -- 左根右 3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 -- 左右根由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
2.2、层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。 设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发 首先访问第一层的树根节点 然后从左到右访问第2层上的节点 接着是第三层的节点 以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
补充深度优先遍历和广度优先遍历深度优先遍历前序遍历的本质就是一种深度优先遍历(dfs--Depth First Search)注中序遍历和后序遍历也算是不太正规的深度优先遍历广度优先遍历层序遍历的本质就是一种广度优先遍历(bfs--Breadth First Search)ex扫雷的展开就可以使用这两种遍历来实现(就是点一下直接打开一堆的效果)
