5.1二叉树及其表示
树是由节点和边组成的。
1.有根树
树是由顶点(vertex)和边(edge)组成。树的每个顶点也叫节点(node)。
2.深度与层次
由树的连通性，每一节点与根都有一条路径相连：根据树的无环性，由根通往每个节点的路径必然唯一。
节点v的深度：每个节点到root的唯一通路所经过的边的数目，称作v的数目，记作depth(v)。
约定 depth(r) = 0，其中r表示根节点。
祖先：任一节点通往树根所经过的每个节点都叫做v的祖先(ancestor),v是他们的后代(descendant)。特别地，v的祖先和后代包括v本身。v本身以外的祖先/后代称为v的真祖先(proper ancestor)/真后代(proper descendant)。
父亲/孩子：u如果是v的祖先，且u比v高出一层。就称u是v的父亲。v是u的孩子。
度:v的孩子的总数，称作v的度数或者度(degree)，记作deg(v)。
叶节点：无孩子的节点称为叶节点。(leaf node)。其余节点（包括根节点，叫做内部节点）。
子树：v的所有后代及其连边所组成树称作子树(subtree)，记作subtree(v)。
3.高度
树T中所有节点深度最大值称作树的高度（height），记作height(H)。
不难理解，树的高度(height)，是由其中某个叶节点的深度决定的，特别地，本书约定，仅含单个节点的树的高度为0，空树的高度为-1。
推而广之，任一节点v所对应子树subtree(v)的高度，亦称做该节点的高度，记作height(v)。特别地，全树的高度称作根节点的高度。即height(T) = height(r)。
5.1.2 二叉树
如图，二叉树的每个节点的度都不超过2。因此在二叉树中，每个节点的左右孩子都可以以左右区分——此时，亦称作有序二叉树(ordered binary tree)。特别地，不含一度节点的树，称做真二叉树(proper binary tree)。
5.1.3多叉树
一般地，树中各节点孩子数目不确定，每个节点孩子均不超过k个的有根树，称做k叉树。
（1）父节点表示法
(2)孩子节点表示法
（3）父节点+孩子节点表示法
文章来源地址https://www.toymoban.com/news/detail-640842.html
文章来源：https://www.toymoban.com/news/detail-640842.html
到了这里，关于数据结构(c++语言版) 邓俊辉 第五章：二叉树学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
