5、2_1_二叉树的定义和基本术语.pdf

《5、2_1_二叉树的定义和基本术语.pdf》由会员分享，可在线阅读，更多相关《5、2_1_二叉树的定义和基本术语.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/7王道考研/1本节内容二叉树定义基本术语王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM知识总览知识总览22020/3/7王道考研/2王道考研/CSKAOYAN.COM二叉树的基本概念二叉树的基本概念二叉树是n（n0）个结点的有限集合： 或者为空二叉树，即n = 0。 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。特点：每个结点至多只有两棵子树 左右子树不能颠倒（二叉树是有序树）结点A的左子树BDGH二叉树是递归定义的数据结构BADGHCEIFLKJ左子树右子树（空二叉树）结点A的右子树注意区别：度为2的有序

2、树3王道考研/CSKAOYAN.COM二叉树的五种状态二叉树的五种状态空二叉树只有根节点只有左子树只有右子树左右子树都有42020/3/7王道考研/3王道考研/CSKAOYAN.COM几个特殊的二叉树几个特殊的二叉树124376581110913121514满二叉树。一棵高度为h，且含有2h - 1个结点的二叉树特点：只有最后一层有叶子结点不存在度为 1 的结点按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 /2 （如果有的话）124376581110913121514完全二叉树。当且仅当其每个结点都与高度为h的满二叉树中编号为1n的结点一一对应时

3、，称为完全二叉树特点：只有最后两层可能有叶子结点最多只有一个度为1的结点同左 i /2 为分支结点， i /2 为叶子结点5王道考研/CSKAOYAN.COM几个特殊的二叉树几个特殊的二叉树124376581110913121514不是“完全二叉树”如果某结点只有一个孩子，那么一定是左孩子62020/3/7王道考研/4王道考研/CSKAOYAN.COM几个特殊的二叉树几个特殊的二叉树二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。13191191250262166左子树706030右子树50262166706030左子树右子树二叉排序树可用于元素的排序、搜索68插入新元素687王道考研/CSKAOYAN.COM几个特殊的二叉树几个特殊的二叉树平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。50262166706030平衡二叉树能有更高的搜索效率682621305060666870左子树深度=2右子树深度=3左子树深度=1右子树深度=6胖胖的、丰满的树82020/3/7王道考研/5王道考研/CSKAOYAN.COM知识回顾与重要考点知识回顾与重要考点9