《算法导论》第10章 二叉树.pptx

二叉树

线性结构和树形结构数组链表二叉树多叉树

生活中的树形结构

树的基本概念1、节点、根节点、父节点、子节点、兄弟节点2、一棵树可以没有任何节点，称为空树3、一棵树可以只有一个节点，这个时候这棵树只有根节点4、子树、左子树，右子树5、节点的度：子树的个数6、叶子节点：度为0的节点7、非叶子节点：度不为0的节点

树的基本概念1、层数：根节点在第一层，根节点的子节点在第二层，依此类推2、节点的高度：从当前节点到最远叶子节点的路径上的节点总数3、树的高度：所有节点高度中的最大值

二叉树的特点1、每个节点的度最大为2（即一个节点最多拥有两棵子树）2、左子树和右子树是有相对顺序的3、非空二叉树的第i层，最多有2i-1个节点4、在高度为h的二叉树上最多有2h-1个节点

满二叉树满二叉树：最后一层节点的度都为0，其它节点的度都为2在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多假设满二叉树的高度为h，那么第i层的节点数量：2i-1叶子节点数量：2h-1总节点数量n=20+21+22+…+2h-1=2h-1h=log2(n+1)

完全二叉树完全二叉树：叶子节点只会出现在最后两层，且最后一层的叶子节点都从左向右填充。

完全二叉树的高度假设完全二叉树的高度为h，那么至少有2h-1个节点（20+21+22+…+2h-2+1）最多有2h-1个节点（20+21+22+…+2h-1，满二叉树）总结点数量为n2h-1=n2hh-1=log2nhh=floor(log2n)+1

二叉树的遍历代码

二叉树的遍历逻辑

谢谢！