本文共 2811 字,大约阅读时间需要 9 分钟。
n(大于等于0)个结点形成的层次结构,若n=0,则为空树;n=1,则为单结点树;当n>1时,存在一个结点作为树的根,其余结点形成根的子树(子树也是树~);两个结点之间的连线表示结点间的父子关系;
二叉树的概念及基本性质
二叉树是一棵二元树,也是一棵位置树。结点的两个子树分别称为左子树和右子树;左右子树的根结点分别称为左右儿子;
基本性质:(二叉树有很多好的性质,在设计算法时应当充分利用)
在非空二叉树中,第n层上的结点个数x满足:x小于等于2^(n-1);(n大于等于1,当n=1时即为根结点);
高为K的二叉树中,结点总数M满足M小于等于2^K-1;(K大于等于0,当K==0时为空树);
M个结点的二叉树的高h满足:h大于等于以2为底M的对数向下取整后+1;
注意,按照上面的等式,h大于等于以2为底(M+1)的对数(记为H),由于h应为整数,所以要先对H进行向下取整,如果H本身为整数,那么,h>=floor(H);如果H本身为小数,那么h>=floor(H)+1;即引入floor操作并没有办法得到一个统一的表达式;问题出在h是通过大于等于符号和H关联的,假设h严格大于H,那么即使H本身为整数,考虑到h为整数,h>=H+1=floor(H)+1;如果H为小数,那么h>=floor(H)+1也是可以的;所以就需要放缩啦;放缩的结果即为结论;
满二叉树与完全二叉树
完全二叉树的性质:
树的存储方法
特别的,完全二叉树中由于特殊性质,也可以使用数组来存储;
树的遍历方法
所谓树的遍历,其实质是结合树的存储方式并按照某种顺序访问树中所有结点,访问的过程可以将层次结构的树变为线性结构;
常见的树的遍历方法大概分为两种:广度优先法和深度优先法;(这两种方法是遍历连通图的两种方法,在图的相关总结中,会发现,树也是一种连通图~)
广度优先遍历:其核心为“按层遍历”,首先访问第一层所有结点,然后访问第二层。。。。
过程如下:从某棵树的根结点出发,首先访问该结点的所有子结点,并且按照访问子结点的顺序将子结点入队列,形成新的出发点的候选队列;当所有子结点入队列后,将候选队列中的队头元素作为新的出发点,重复该过程,直到候选队列为空,遍历就完毕啦;
深度优先遍历:其核心为只有深度优先遍历完一棵树后才进行另一棵树(通常为兄弟树)的遍历;遍历完成的标志是访问到该树中所有的结点;
过程如下:从某棵树的根结点开始,首先访问根结点,然后将其第一个子结点作为新的根结点执行深度优先遍历;当第一棵子树完毕后,再对第二棵子树执行,直到所有子树都执行完毕后这棵树的深度优先遍历就结束啦;
对于二叉树,遍历又可以分为先序遍历、中序遍历以及后序遍历,该部分内容在二叉树专题中详细记录;
普通树与二叉树的相互转化
普通树 to 二叉树:
对于一棵普通树,根结点保持不变,断开根结点同其子结点的连接,此时根结点的子树便形成森林;然后将该森林转换为一棵二叉树作为根结点的左子树,由于根结点没有兄弟结点所以根结点便没有右子树;
二叉树 to 普通树:
二叉树BT的根结点作为普通树PT的根结点;将BT根结点的左子树转换为森林,作为PT的子树;
森林与二叉树的相互转化
森林 to 二叉树:采用“左儿子右兄弟”的规则,添加一个虚拟根结点,原来森林中各个树的根结点便互为兄弟结点啦,然后把森林中最左边的子树的根结点作为二叉树的根结点;将根结点的子树(也是森林)转换为二叉树作为根结点的左子树;森林中其它的树转换为二叉树作为根结点的右子树;
二叉树 to 森林:
二叉树BT的根结点作为森林F中第一棵树的根结点;将BT根结点的右子树转换为森林,作为F中的一部分;将BT根结点的左子树转换为森林,作为第一棵树的子树;转换完毕;
其实,一棵树也是一个森林,故只需实现森林同二叉树的转换算法,即可实现树与二叉树的相互转换;
(这是自己使用Java语言(部分细节参考了Java集合类源码)实现的一套数据结构API,包括链表,栈、队列、树、图等内容,为算法学习提供基础,完善ing~)
转载地址:http://numsi.baihongyu.com/