(29)王道数据结构-二叉树的定义

定义

二叉树是n(n≥0)个节点的有限集合：
①或者为空二叉树,即n=0
②或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树
特点:
①每个节点至多只有两棵子树
②左右子树不能颠倒(二叉树是有序树)

特殊二叉树

满二叉树:

一棵高度为h，且含有2^h - 1个节点的二叉树
特点:
①只有最后一层有叶子节点
②不存在度为1的节点
③按层序从1开始编号，节点为i的做孩子为2i，右孩子为2i + 1，节点i的父亲节点为i/2

完全二叉树:

当且仅当其每个节点都与高度为h的满二叉树编号为1~n个节点一一对应时，称为完全二叉树
特点:
①只有最后两层可能有叶子节点
②最多只有一个度为1的节点
③按层序从1开始编号，节点为i的做孩子为2i，右孩子为2i + 1，节点i的父亲节点为i/2
④i ≤ [n/2]为分支节点，i > [n/2]为叶子节点