本文共 720 字,大约阅读时间需要 2 分钟。
在理解完全二叉树之前,首先要弄清楚完全二叉树和满二叉树的区别。
1.什么是满二叉树?
(1)满二叉树所有分支节点都有左孩子节点和右孩子节点;(只有度为0和度为2的节点)
(2)满二叉树的所有叶子节点都在最下一层。
2.什么是完全二叉树?
(1)叶子节点只在层次最大的两层出现;
(2)最下面一层的叶子节点都依次排列在该层最左边的位置上;
(3)如果有度为1的节点,只可能有一个,且该节点只有左孩子而无右孩子;
(4)按层序编号后,一旦出现某个节点为叶子节点或者只有左孩子,则编号大于它的节点均为叶子节点。
可见,满二叉树是完全二叉树的一种特例。
关于完全二叉树还有一个特点(5)当节点总数为奇数时,度为1的节点个数=0,当节点总数为偶数时,度为1的节点个数=1
3.什么是线索二叉树?
引入线索二叉树是为了加快查找结点前驱和后继的速度。
线索二叉树是加上线索后的链表结构,它是二叉树在计算机内部的一种存储结构,是一种物理结构。
对于具有n个节点的二叉树,采用二叉链存储结构时,每个节点有两个指针域,总共有2n个指针域,又由于这n个节点中只有树根节点没有被指,所以有2n-(n-1)=n+1个空链域。
4.什么是二叉排序树?
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字;
同时,左右子树又各是一棵二叉排序树。
5.二叉树的存储结构
依据二叉树的性质,完全二叉树和满二叉树采用顺序存储比较合适;
但由于顺序存储对空间利用率较低,因此,一般二叉树都采用链式存储结构
6.要构造一棵树,必须知道它的中序遍历
1、前序+中序
2、后序+中序
3、层序+中序
知道以上3种情况的任意一种都可以构造出该树
转载地址:http://fjssi.baihongyu.com/