Hi,大家好,我是编程小6,很荣幸遇见你,我把这些年在开发过程中遇到的问题或想法写出来,今天说一说数据结构之满二叉树「建议收藏」,希望能够帮助你!!!。
二叉树:二叉树是n(n>=0)个结点的有限集合,它或为空(n=0), 或是由一个根及两棵互不相交的左子树和右子树组成,且树中左子树和右子树也均为二叉树;二叉树可以是空集合, 左子树 、右子树也可以为空
二叉树的特点:
二叉树具有下列重要性质:
二叉查树的遍历方式:
满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,深度为k(k>=1)且有(2^k)-1个结点的二叉树就是满二叉树
满二叉树的性质:
完全二叉树:深度为K的二叉树中,K-1层结点数是满的2^(k-2),K层结点是左连续的(即结点编号是连续的);高度为h(h>=2)的完全二叉树至少有2^(h-2)个叶子结点。
完全二叉树的性质:
满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树
1、顺序存储:利用数组
如图:完全二叉树的顺序存储我们只需需要至上而下,至左而右给各个节点编号,该编号就是元素在数组中的索引;
如图非完全二叉树:我们需要增加虚拟节点,如果一个高度为h并且节点个数也是h的右支树,却需要2^h-1个存储空间, 所以该存储方式比较浪费空间
2、链式存储:利用链表
如图:二叉链表表示法 ,二叉链表,只能由父节点推导子节点,不能逆向
如图:三叉链表表示法,三叉链表相较于二叉链表,多了一个指向双亲的指针域,增加了空间但是对于树的操作来说更加灵活。
上一篇
已是最后文章
下一篇
已是最新文章