树的基础概念

树的基本公式

树的结点个数: ,表示的是所有结点度数之和加1,代表的是度为的结点数量,因为,每个结点和其孩子都由唯一的边确定,因此结点度数之和等于树中边数之和,所以统计好边的数量在加上根节点,即所有节点度数之和加1

或者可以表示为所有度的节点相加 这个很好理解,将每个度的结点都加上,得到总结点数量

叶子节点数量:叶子节点记为 可以表示为所有节点减去度大于等于1的节点

二叉树

对于独特的二叉树而言,他的性质会变得更简洁一些,因为度只有三个可能,这三种可能

非空二叉树的叶节点数等于度为2的节点数加1

对于完全二叉树,若有度数为1的结点,则只可能有一个

易错题

:已知一棵完全二叉树的第六层(根节点为第一层)有8个叶结点,则完全二叉树的结点个数最少为: 这类题的坑点在于,告诉你讲某一层的叶子结点,有两种可能6层或7层,就是有可能是上层遗留的叶子结点,也有可能是本层的新的叶子节点.

链式存储结构,在含有结点的二叉链表中,含有的空链域

由完全二叉树总结点数的奇偶性可以确定的值,但是不能根据来确定的值