网站建设内部流程图,ftp怎么重新上传网站,万网放网站,客厅设计说明200字目录 前言1. 树型结构1. 1 树的概念1.2 树的特点1.3 树的相关术语 2. 二叉树#xff08;binary tree#xff09;2.1 二叉树的概念2.2 二叉树中的特殊树2.2.1 满二叉树2.2.2 完全二叉树 2.3 二叉树的性质 3. 二叉树的遍历3.1 前序遍历3.2 中序遍历3.3 后序遍历3.4 层序遍历 总… 目录 前言1. 树型结构1. 1 树的概念1.2 树的特点1.3 树的相关术语 2. 二叉树binary tree2.1 二叉树的概念2.2 二叉树中的特殊树2.2.1 满二叉树2.2.2 完全二叉树 2.3 二叉树的性质 3. 二叉树的遍历3.1 前序遍历3.2 中序遍历3.3 后序遍历3.4 层序遍历 总结 前言
因为二叉树是一种特殊的树所以想要学习好二叉树必须了解树型结构知道树的基本概念。所以正式开始学习之前在前面为大家引入了树的概念。
1. 树型结构
1. 1 树的概念 树是一种非线性的数据结构它是有n个节点构成的集合把它称为树是因为这种结构看起来就像一个倒挂的树根在上面叶在下面。 1.2 树的特点 有一个特殊的节点没有前驱节点我们将此称为根节点。树是递归定义的。树的任何节点都可以有任意后继但是它们不会交叉。树是一个非线性数据结构。 1.3 树的相关术语 根节点一个特殊节点没有前驱节点上图第一个1 。节点的度一个节点拥有的子树的多少就是该节点的度上图9的度为2 。树的度一棵树最大节点的度就是树的度 上图最大的节点的度为3 则树的度为3 。叶节点又称叶子节点终端节点度为零的节点上图3、4等都是叶节点。父节点又称双亲节点父亲节点一个节点有子节点则就是这是字节点的父节点上图9是3的父节点。子节点又称孩子节点一个节点下面与连接的节点就是子节点上图3是9的子节点。节点的层次根节点为第一层根节点的子节点为第二层以此类推。树的高度或深度树中最大的节点的层次。 2. 二叉树binary tree
2.1 二叉树的概念 二叉树是一种树形数据结构是一种特殊的树二叉树中每个节点最多只能有两个子节点并且二叉树的次序是不可颠倒的是一颗有序树。 2.2 二叉树中的特殊树 二叉树是一种特殊的树而特殊树中还会有特殊。 2.2.1 满二叉树
一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵 二叉树的层数为K且结点总数是 则它就是满二叉树。
2.2.2 完全二叉树
完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n 个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
2.3 二叉树的性质 二叉树是由节点和边构成的树形结构每个节点最多有两个子节点分别称为左子节点和右子节点没有子节点的节点称为叶子节点。二叉树有一个根节点其它节点都是根节点的子节点。根节点没有父节点。对于一个有n个节点的二叉树设其高度为h则h的取值范围为1到n且h为log2(n1)向上取整。在二叉树的第i层上最多有2^(i-1)个节点。若深度为h的二叉树满足每个节点都有两个子节点且所有叶子节点都在第h层或h-1层则称该树为满二叉树。满二叉树的节点数为2^h-1。若深度为h的二叉树最后一层只有叶子节点其它层都是满的则称该树为完全二叉树。完全二叉树的节点数在1到2^(h-1)之间。若二叉树的左右子树可以交换位置且仍为同一棵树则该二叉树为镜像二叉树。1. 二叉树是由节点和边构成的树形结构每个节点最多有两个子节点分别称为左子节点和右子节点没有子节点的节点称为叶子节点。 《一些练习的题》 1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 3.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 4.一棵完全二叉树的节点数为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 答案 1.B 2.A 3.B 4.B 3. 二叉树的遍历 二叉树的遍历是一个重要的点是一个必须要掌握的点遍历分为前中后序遍历层序遍历四种。我们将使用这张图详细介绍一下。 遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的操作之一是二叉树上进行其它运算之基础。 3.1 前序遍历
前序遍历的遍历顺序访问根结点—根的左子树—根的右子树。 遍历结果123456 如上图遍历根节点1然后遍历左子树2一直遍历到左子树为null。然后返回途中遍历右子树3的右子树为null。然后返回到22的右子树为null返回到根节点1。1的左树已经遍历一遍所以继续遍历1的右子树4然后先遍历左子树55的左右都为空则返回遍历4的右子树6。6的左右都为空原路返回到根节点遍历结束。
3.2 中序遍历
根的左子树—根节点—根的右子树。 遍历结果321546
3.3 后序遍历
根的左子树—根的右子树—根节点。 遍历结果325641
3.4 层序遍历
除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 遍历结果124356 一些练习选择题 某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为() A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为() A: E B: F C: G D: H设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为() A: adbce B: decab C: debac D: abcde某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为() A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 【参考答案】 1. A 2. A 3. D 4. A 总结 这篇博客主要为大家带来树及二叉树的基本概念性质遍历方式等下篇博客将为大家带来代码的实现以及应用。 期待大家关注! 最后祝大家61快乐天天开心
