线索二叉树

xiaoxiao2021-02-28  15

树的存储结构为链式存储结构

Lchild Data Rchild

一棵结点为n的树,有2n个指针,其中有n-1个指针有实际用到,剩下的n+1没有用到,线索二叉树可以利用到剩下的n+1个空指针用来存储二叉树的前驱后驱信息。 二叉树的前序排列,二叉树的中序排列,以上这些信息。

概念:

    左指针指向前驱,右指针指向后续,左指针右指针不叫指针了,叫线索。

    Lbit Lchild Data Rchild Rbit    用这样的存储结构区分指针还是线索

    Lbit=0,Lchild是通常的指针

    Lbit=1,Lchild是线索

    同理R

如何将二叉树转化为线索二叉树

1、先把前序遍历画出

2、把每个左右空指针分别指向前序遍历的前驱后续

线索二叉树就是方便找出结点的前驱或者后续

中序线索二叉树的非叶子结点的后继是右子树的左下结点

后序线索二叉树的非叶子结点的后继结点是父节点,根结点的后继结点是null

    

转载请注明原文地址: https://www.6miu.com/read-2449968.html

最新回复(0)