【大话数据结构C语言】25 什么是二叉树？

我的首发平台是公众号【CodeAllen】，学习交流QQ群：736386324

背景：

电视上经常有猜价格的的游戏，比较高效的方法是折半查找算法

假设是100以内的数字，则一定能在7次以内猜出来

猜数的过程可以表示为下图：

类似上述的问题，都是用树结构来建模，这种树是一种特殊的树状结构，叫做二叉树

二叉树是n（n>=0）个结点的有限集合,该集合或者为空集（称为空二叉树），或者由一个根结点和两颗互不相交的，分别称为根结点的左子树和右子树的二叉树组成

如下图就是一个二叉树

特殊的二叉树：

斜 树 \color{#FF3030}{斜树} 斜树 所有的结点都只有左子树的二叉树叫做左斜树，所有结点都是只有右子树的而二叉树叫右斜树，这两者统称为斜树 左斜树 右斜树

满 二 叉 树 \color{#FF3030}{满二叉树} 满二叉树 在一个二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树

满二叉树的特点有： 1.叶子只能出现在最下一层，出现在其他层就不可能达到平衡 2.非叶子结点的度一定是2 3.在同样的深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完 全 二 叉 树 \color{#FF3030}{完全二叉树} 完全二叉树 对于一棵具有n个结点的二叉树按层序编号，如果编号为 i（1