本文主要是介绍数据结构 第5章 树与二叉树(一轮习题总结),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
数据结构 第5章 树与二叉树
- 5.1 树的基本概念
- 5.2 二叉树的概念
- 5.3 二叉树的遍历和线索二叉树
- 5.4 树、森林
- 5.5 树与二叉树的应用
5.1 树的基本概念(3 4 7)
5.2 二叉树的概念(2 14 19 22)
5.3 二叉树的遍历和线索二叉树
5.4 树、森林
5.5 树与二叉树的应用
5.1 树的基本概念
- T3
树的路径长度:从树根到每个结点的路径长度总和
区分:哈弗曼树的带权路径长度 - T4
重点理解(树的基本术语):
度:每个结点的分支数;度>0是分支节点,度=0是叶结点/终端结点
高度:=层数,根结点为第一层,h=1;eg:结点数为3的满二叉树h=2
路径:两结点路径长度/树的路径长度(总和)
5.2 二叉树的概念
- T1
含有n个结点的完全二叉树的高度为:log(n+1)向上取整 或 logn向下取整+1
eg:n=4,h=3 - T2
(判断)结点按完全二叉树层序编号的二叉树中,第i个结点的左孩子编号为2i。
错误,可能没有左孩子,若有为2i,层序编号从1开始 - T10 T19
一棵完全二叉树第六层有n个叶子结点,共有多少叶子结点?(易错)
此处有两种情况:最少(只有六层,第六层不满)、最多(有七层,第六层满第七层不满) - T14
二叉树/完全二叉树的特点:n0=n2+1
完全二叉树的特点:n1=0或1
(以上结论,常用于:根据叶结点,计算完全二叉树的结点数)
5.3 二叉树的遍历和线索二叉树
5.4 树、森林
5.5 树与二叉树的应用
这篇关于数据结构 第5章 树与二叉树(一轮习题总结)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!