2024-11-25 二叉树的定义
一、基本概念
1.二叉树是n(n>=0)个结点的有限集合:
① 或者为空二叉树，即n=0。
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点： ①每个结点至多只有两棵子树。
②左右子树不能颠倒（二叉树是有序树）
（二叉树是递归定义的二叉树）
五种状态：
1.空二叉树 2.只有左子树 3.只有右子树 4.只有根节点 5.左右子树都有
二、几种特殊的二叉树
1.满二叉树：以可高度为h，且还有2^h-1个结点的二叉树。
特点：①只有最后一层有叶子结点
②不存在度为1的结点
③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;结点i的父节点为[i/2](如果有的话,向下取整)--可以用顺序存储来实现。
2.完全二叉树：当且仅当其每个结点都与高度为h满二叉树中编号为1~n的结点一一对应时，称为完全二叉树
特点：①只有最后两层可能有叶子结点
②)最多只有一个度为1的结点
③同上③
④i<|n/2]为分支结点，i>|n/2]为叶子结点
（对于完全二叉树来说，如果某一个结点只有一个孩子，必然是左孩子。)
3.二叉排序树： 一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。（可用于元素的排序、搜索）
4.平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1.（有更高的搜素效率）
-----左边相比于右边，查找相同的数字，遍历的结点要少很多。
总结：