VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > temp > python入门教程 >
  • 【自考】数据结构第四章树和二叉树,期末不挂科指南,第6篇

章节简介

前5篇博客写的都是线性结构,对于有层级结构的数据需要用树形结构来描述

本章的重要知识点

  1. 理解有关树的基本概念和二叉树的基本概念
  2. 掌握二叉树的存储结构以及遍历方法
  3. 掌握树的存储结构以及树、森林、二叉树的相互转换方法
  4. 梳理掌握哈夫曼树构造方法和哈夫曼编码的设计方法

树的基本概念

核心一句话

线性结构中一个结点至多只有一个直接后继,树形结构一个结点可以有一个或多个直接后继

认识树

看图即可,你要能区分出来哪些是树,哪些不是树

树的相关术语

  1. 结点的度:树上任意结点所拥有的子树的数目称为该结点的度

  2. 叶子:度为0的结点称为叶子或者终端结点

  3. 树的度:一棵树中所有结点的度的最大值称为该树的度,就是把所有结点的度求和

  4. 结点的层次:从根算起,根的层次为1,其余结点的层次为其双亲的层次加1

  5. 树的高度:一棵树中所有结点层次数的最大值称为该树的高度或深度

  6. 还有一些小概念:有序树、无序树

树的相关术语,一定要一开始就明确清晰,后面才好学习

二叉树

官方概念:二叉树是n(n≥0)个元素的有限集合,该集合或者为空,或者由一个根及两棵互不相交的左子树和右子树组成,其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树(它们中的任何一个都可以是空子树),并且这两棵子树之间有次序关系,交换位置就成为一棵不同的二叉树。

左子树和右子树,也有的叫做左孩子和右孩子

二叉树五种基本形态,方块表示子树

二叉树的基本运算(不写代码,了解重点函数即可)

  1. 初始化
  2. 求双亲
  3. 求左孩子
  4. 求右孩子
  5. 建二叉树
  6. 先序遍历!!!
  7. 中序遍历!!!
  8. 后序遍历!!!
  9. 层次遍历!!!
    先序遍历,中序遍历,后序遍历在考试中一般不要求手写代码,但是需要你能通过一棵树结构,输出最终的结果,这个博客结尾给大家看一下例题

二叉树性质(很重要,细碎知识点很多)

性质1:二叉树第i(i≥1)层上至多有2i-1个结点。

不需要死记硬背,实际需要的时候画一个二叉树就可以求出来了

性质2:深度为k(k≥1)的二叉树至多有2k-1个结点

依旧可以推导出来
深度为1的二叉树 结点最多为1
深度为2的二叉树 结点最多为3
深度为3的二叉树 结点最多为7
深度为k的二叉树 结点最多为2k-1

性质3:对任何一棵二叉树,若度数为0的结点(叶结点)个数为n0,度数为2的结点个数为n2,则n0 = n2+1

这个性质需要稍微推导一下
先回答一个问题,你知道树的度数,怎么计算树的结点数
例如 树的度数为2,结点树为几,这个不难想象,会出现如下情况

看到这里不难发现,存在一个公式为 树的度数+1=树的结点树
那么我们开始推导上述公式
假设 二叉树的0度,1度,2度结点个数为n0,n1,n2,结点总数为T
T = n0+n1+n2
树的度数+1 = T
树的度数怎么求?n00+n11+n22 是树的度数
继续n0
0+n11+n22 +1 = T = n0+n1+n2
===> 2n2+1=n0+n2
===>n0=n2+1

好了,上述过程,争取看明白吧

性质4:含有n个结点的完全二叉树的深度为


相关教程