线索二叉树

基本概念



做题先遍历，得出遍历顺序好连线

中序线索二叉树的基本操作

  • 找线索二叉树的第一个结点

    1
    2
    3
    4
    5
    6
    7
    8
    TreeNode* FirstInorder(TreeNode* t)
    {
        TreeNode* p=t;
        while(p->LThread==0)//p有左孩子
            p=p->left;
        return p;

    }

  • 找线索二叉树的最后一个节点

    1
    2
    3
    4
    5
    6
    7
    8
    TreeNode* LastInorder(TreeNode* t)
    {
        TreeNode* p=t;
        while(p->LRThread==0)//p有右孩子
            p=p->right;
        return p;

    }

  • 找结点p的中根后继结点
    若p->Rthread==1,中根后继为p->right
    若p->Rthread==0,中根后继为其右子树的中根序列首结点

    1
    2
    3
    4
    5
    TreeNode* nextInorder(TreeNode* t)
    {
        if(t->Rthread==1) return t->right;
        else return FirstInorder(t->right);
    }

  • 找结点p的中根前驱节点
    若p->Lthread==1,中根前驱为p->left
    若p->Lthread==0,中跟前驱为其左子树的中根序列尾结点

    1
    2
    3
    4
    5
    TreeNode* preInorder(TreeNode* t)
    {
        if(t->Lthread==1) return t->left;
        else return LastInorder(t>left);
    }

  • 中序线索二叉树的中根遍历

    1
    2
    3
    4
    5
    6
    7
    void Inorder(TreeNode* t)
    {
        for(TreeNode* p=FirstInorder(t);p!=NULL;p=nextInorder(p))
        {
            visit(p->data);
        }
    }

  • 二叉树的中序线索化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    void Inorder_Threading(TreeNode* p)
    {
        if(p==NULL) return;
        Inorder_Threading(t->left);//左
        
        if(p->left==NULL) //中
        {
            p->Lthread=1;
            p->left=pre;
        }
        else
            p->Lthread=0;
        if(pre!=NULL&&pre->right==NULL)
        {
            pre->Rthread=1;
            pre->right=p;
        }
        else if(pre!=NULL)
            pre->Rthread=0;

        Inrder_Threading(t->right);//右
    }
    pre->Rthread=1;

关于前序后续线索二叉树

前序线索二叉树不能高效解决先根前序
后序线索二叉树不能高效解决后根后续