科研之友
微信
新浪微博
Facebook
分享链接
摘要
目前,对二叉树存储结构主要有顺序存储结构和链式存储结构(二叉链表) 2种。其中顺序存储结构主要用于完全二叉树,而链式存储结构可用于所有的二叉树,是比较常用的存储结构。但是这种二叉链式存储结构由于叶子结点指针域不能被利用,存在大量的空指针而导致整个树存储密度低下。同时,应用这种二叉链式存储,对二叉树进行遍历、结点查询等操作时,需要用到显式或隐式栈,进而增加各种算法额外的空间,导致空间复杂度较高,而且各种操作过程也相对较复杂。为了提高二叉树的存储密度,降低各种处理算法的空间复杂度,简化对二叉树的遍历、结点查询、线索化等有关操作的具体实现过程,结合完全二叉树存储的思想,采用增加虚拟结点的方式对二叉树的实际结点编号,提出改进的二叉树存储结构——顺序表存储结构。
- 单位
