二叉树有几种实现方式
时间:2020-08-14 22:00:13
作者:重庆seo小潘
来源:
二叉树 五种基本形态:空二叉树、只有根节点的二叉树、只有根节点和左子树TL的二叉树、只有根节点和右子树TR的二叉树、具有根节点、左子树TL和右子树TR的二叉树 其它二叉树:斜二叉树、满二叉树、完美二叉树 实现方式:顺序存储、链式存储 二叉树的顺序存储
二叉树
五种基本形态:空二叉树、只有根节点的二叉树、只有根节点和左子树TL的二叉树、只有根节点和右子树TR的二叉树、具有根节点、左子树TL和右子树TR的二叉树
其它二叉树:斜二叉树、满二叉树、完美二叉树
实现方式:顺序存储、链式存储
二叉树的顺序存储,指的是使用顺序表(数组)存储二叉树。需要注意的是,顺序存储只适用于完全二叉树。换句话说,只有完全二叉树才可以使用顺序表存储。因此,如果我们想顺序存储普通二叉树,需要提前将普通二叉树转化为完全二叉树。
二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时,每个结点除了存储结点本身的数据外,还应设置两个指针域lchild和rchild,分别指向该结点的左孩子和右孩子。