网站建设三方合同范本,外贸网站 在线留言,大专网站建设的论文范文,凡科网官网首页1. 树概念2.二叉树的概念1.2二叉树的性质 3.二叉树遍历3.2前序遍历3.2 中序遍历3.3 后序遍历 1. 树概念
树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层次关系的集合#xff0c;有二叉树#xff0c;N叉树等等。
子树… 1. 树概念2.二叉树的概念1.2二叉树的性质 3.二叉树遍历3.2前序遍历3.2 中序遍历3.3 后序遍历 1. 树概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合有二叉树N叉树等等。
子树是互不相交的比如B不能连接CD不能连接E除了根节点外每个节点有且只有一个父节点。A是B、C、D、E的父节点B是F、G的父节点一颗有N个节点的树有N-1条边。 下图有10个节点9条边 在树结构中度是指一个节点的子节点个数的最大值。如果一个节点没有子节点则其度为0;如果一个节点只有一个子节点则其度为1;如果一个节点有两个子节点则其度为2,以此类推。【二叉树不存在度大于2的节点上图是个N叉树】 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为4B的度为2F的度为0树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为4叶子结点或终端结点度为0的结点称为叶结点 如上图C、F、G、H、等节点为叶结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点B是F的父节点同样也是G的父节点。孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点C是A的孩子节点…根结点一棵树中没有父结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推。上图树的层次是3层树的高度或深度树中结点的最大层次 如上图树的高度为3非终端结点或分支结点度不为0的结点 如上图B、D、E…等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点共同的父节点是A堂兄弟结点在同一层的结点互为堂兄弟如上图G、H互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先B是F的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林
2.二叉树的概念
二叉树是一种树形结构其中每个节点最多有两个子节点。 二叉树的递归定义为二叉树是一棵空树或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树左子树和右子树又同样都是二叉树。 二叉树有左右之分次序不能颠倒因此二叉树是有序树。如上图从上到下从左往右依次为1、2、3、4、5、6。所谓有序是指从左往 . **满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。**也就是说如果一棵 二叉树的层数为K且结点总数是 2 k − 1 2^k-1 2k−1 则它就是满二叉树。 完全二叉树: 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n 个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 1.2二叉树的性质 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)i0个结点 若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 2 k − 1 2^k-1 2k−1 (k0) 对任何一棵二叉树, **如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21,**也就是叶子节点比非叶子节点多1个。 具有n个结点的完全二叉树的深度K为 l o g 2 ( n 1 ) log2(n1) log2(n1) 上取整。 根据第二点性质可以推导出2^k -1 n -- 2^k n1这个k就等于第4点中提到的k因为k为log2(n1)那么也就是求2的多少次方等于k假设有9个节点91 等于10,2的3次方等于8,2的4次方等于16,向上取整就是取4。该二叉树深度为4。 对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i 的结点有 若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点【知道孩子序号求父节点】若2i1N左孩子序号2i1否则无左孩子若2i2n右孩子序号2i2否则无右孩子。
3.二叉树遍历
二叉树的遍历是指从根节点出发按照某种次序依次访问二叉树中的所有节点使每个节点被且仅被访问一次。二叉树的遍历方式主要有先序遍历、中序遍历、后序遍历、层次遍历。
先序遍历根节点 - 左子树 - 右子树中序遍历左子树 - 根节点 - 右子树后序遍历左子树 - 右子树 - 根节点层次遍历按照从上到下顺序访问每个节点
3.2前序遍历 先序遍历根节点 - 左子树 - 右子树依次打印节点 遍历结果1、2、 4 、 5、 3 、6 首先访问根节点1,打印1然后递归地访问左子树和右子树。在左子树中打印2站在节点2的视角也是一棵二叉树节点2是这棵二叉树的根节点于是又要先访问节点2的左子树打印4站在节点4的角度节点4是根节点节点4也有左子树和右子树于是又要再去访问节点4的左子树4的左子树为空递归回来访问节点4的右子树右子树为空递归回来。然后访问节点2的右子树
递归回来此时站在根节点1的视角它的左子树遍历完了于是访问右子树站在右子树的视角它此时也是一个独立 的二叉树,打印3后于是要访问节点3的左子树和右子树。
以此类推如下图因此每个节点可以当做是一个二叉树由多个小的二叉树结合成一个大的二叉树。 3.2 中序遍历 中序遍历左子树 - 根节点 - 右子树依次打印节点 遍历结果4、 2 、5、 1、6、3 **还是一样的图只是访问的根节点的时机不一样前序遍历先打印根节点中序遍历先打印最左的一个节点后续遍历最后打印根节点**进来先访问到了根节点1不打印直到把左子树走完此时遍历到了节点44没有左子树于是递归回来打印4,4没有右子树递归回来打印2只有把节点2的左子树遍历完后才会打印2依次类推。所以只有把每个节点的左子树遍历完才会打印当前节点然后再去遍历右子树右子树也有它的左子树同理。
3.3 后序遍历 后序遍历左子树 - 右子树 - 根节点 遍历结果4、 5、 2、 6、 3、 1 根据前中后序遍历得出后序遍历只有当左子树和右子树遍历完才会回来打印根节点。 遍历开始遇到1不能打印只有把1的左子树和右子树遍历完才能打印1
走到节点2不能打印要先把节点2的左子树和右子树遍历完才能打印2
走到4由于4的左子树和右子树为空递归回来打印4
走到5由于5的左子树和右子树为空递归回来打印5
此时再递归回来就可以打印节点2了因为2的左子树和右子树都遍历完了。
依次类推最后才能打印根节点1。
得出一个规律前序遍历的第一个打印的节点肯定是根节点后序遍历最后打印的节点肯定是根节点。【重点】 根据上述规律做出这道题 1.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为() A: adbce B: decab C: debac D: abcde 根据规律可以画出如下图
根据后序遍历最后一个打印的节点是a,那么a肯定就是这颗二叉树的根节点再根据中序遍历按照a的位置划分左右子树a的左边是a的左子树a的右边是a的右子树由于a的右边有多个节点不确定哪个节点是a的孩子节点所以要继续化简于是得出 再根据后序遍历的倒数第二个节点因为后序遍历中的a已经被刨除出去了所以当前后序遍历的最后一个节点是c再根据规律后序遍历的最后一个节点肯定是根节点按照c的位置划分出中序遍历的左右子树在中序遍历中c的左边是c的左子树c的右边是c的右子树由于c的左右皆剩下1个节点那么这两个节点就是c的孩子节点于是得出
因为后序遍历中的a已经被刨除出去了所以当前后序遍历的最后一个节点是c再根据规律后序遍历的最后一个节点肯定是根节点按照c的位置划分出中序遍历的左右子树在中序遍历中c的左边是c的左子树c的右边是c的右子树由于c的左右皆剩下1个节点那么这两个节点就是c的孩子节点于是得出 答案是D
