2023考研：数据结构之树与二叉树的基本性质

今天小编为大家整理了数据结构之树与二叉树的基本性质，大家在备考过程中可以用来参考，帮助大家提高备考效率，树和二叉树是数据结构中的重要考点，下面介绍下树和二叉树基本性质。

基本术语

结点的度：树中一个结点的子结点个数

树的度：树中结点的最大度数

分支结点与叶子结点：度大于0的结点称为分支结点;度等于0的结点称为叶子结点

结点的深度：从根结点开始自顶向下逐层累加

树的高度或深度：树中结点的最大层数

路径：树中两个结点之间所经过的结点序列

路径长度：路径上所经过的边的条数

树的性质

性质1：树中的结点个数等于所有结点的度之和加1.

性质2：对于m度树，定义叶子结点个数为n0，度为1的结点个数为n1,…度为m的结点个数为nm, 于是有n0 = n2 +2*n3 + 3* n4 +… +(m-1)* nm + 1;

性质3：在非空m度树中，第i层上至多有mi-1个结点(i≧1)。

性质4：高度为h的m度树，最多有个结点.

性质5：具有n个结点的m度树的最小高度是 

二叉树的性质

性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。

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

性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。

性质4：树中的结点个数等于所有结点的度之和加1。

性质5：具有n个结点的二叉树的最小高度是