数据结构--线索二叉树的概念-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构--线索二叉树的概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构–线索二叉树的概念

二叉树的中序遍历序列

void InOrder(BiTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild); //递归遍历左子树
        visit(T); //访问根结点
        InOrder(T->rchild); //递归遍历右子树
    }
}

中序遍历序列:D G B E A F C

①如何找到指定结点p在中序遍历序列中的前驱?
②如何找到p的中序后继?

思路:
从根节点出发，重新进行一次中序遍历，指针q记录当前访问的结点,指针pre记录上一个被访问的结点
①当qp时，pre为前驱
②当prep时，q为后继

$\color{green}缺点:找前驱、后继很不方便;遍历操作必须从根开始$

中序线索二叉树

图示说明:

中序遍历序列:D G B E A F C

$\color{orange}n个结点的二叉树，有n+1个空链域!可用来记录前驱、后继的信息$

$\color{green}指向前驱、后继的指针称为"线索”$

线索二叉树的存储结构

图示说明:

typedef struct BiTNode
{
    ElemType data; //数据域
    struct BiTNode *lchild, *rchild; //左、右孩子指针
    struct BiTnode *parent; //父节点指针
}BiTNode, *BiTree;

typedef struct ThreadNode
{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree; //左、右线索标志