二叉树（完全二叉树，满二叉树，二叉树的特性，遍历方式，根据遍历方式画出完整的二叉树图相关例题）

目录

基本概念

一、二叉树（满二叉树，完全二叉树）

二、二叉树的特性

1、若规定根节点的层数为1，则一棵非空二叉树的第i层最多有2^(i-1)?个节点（i>0）

2、若规定只有根节点的二叉树的深度为1，则深度为k的二叉树的最大节点数是 2^i - 1(k>=0)

3、对于任何一棵二叉树，若叶节点数为n0,度为2的节点数为n2，则有n0 = n2+1

（对于任何一棵二叉树，叶子节点永远比度为2的节点多1个）

4、具有n个节点的完全二叉树，其深度为 log2（n+1）向上取整

5、对于具有n个节点的完全二叉树，从上到下，从左至右的顺序，从0编号。

????????若父节点的编号为i，则左孩子的编号为 2*i+1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?右孩子的编号为 2*i+2

? ? ? ? 若任意孩子编号为i，则父亲节点编号为 (i-1)/2

三、遍历方式（前序遍历，中序遍历，后序遍历，层序遍历）?

四、例题（给出遍历顺序，画出整个二叉树图）?

---

基本概念

一、二叉树（满二叉树，完全二叉树）

二、二叉树的特性

1、若规定根节点的层数为1，则一棵非空二叉树的第i层最多有2^(i-1)?个节点（i>0）

2、若规定只有根节点的二叉树的深度为1，则深度为k的二叉树的最大节点数是 2^i - 1(k>=0)

3、对于任何一棵二叉树，若叶节点数为n0,度为2的节点数为n2，则有n0 = n2+1

（对于任何一棵二叉树，叶子节点永远比度为2的节点多1个）

4、具有n个节点的完全二叉树，其深度为 log2（n+1）向上取整

5、对于具有n个节点的完全二叉树，从上到下，从左至右的顺序，从0编号。

????????若父节点的编号为i，则左孩子的编号为 2*i+1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?右孩子的编号为 2*i+2

? ? ? ? 若任意孩子编号为i，则父亲节点编号为 (i-1)/2

三、遍历方式（前序遍历，中序遍历，后序遍历，层序遍历）?

四、例题（给出遍历顺序，画出整个二叉树图）?

?