树——二叉树——线索二叉树

梦里梦外; 2023-06-13 09:35 39阅读 0赞

#### 一、线索二叉树 ####

###### (1)什么是线索化 ######

将二叉树以某种次序将其遍历， 得到线性序列， 就是将非线性结构进行**线索化**。

线索化的优点就是可以很快地得到前驱或后继。

###### 如果保存线索化的线性序列 ######

保存二叉树地线索化序列的其中一种方法就是在结点上加两个指针， 一个指向前驱一个指向后继， 这样的缺点就是存储密度大大降低。另一种方法就是加两个标记 充分利用空指针。

#### 实现方法一 ####

###### 存储结构 ######

<table> 
 <thead> 
  <tr> 
   <th>left</th> 
   <th>LTag</th> 
   <th>data</th> 
   <th>RTag</th> 
   <th>right</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

//存储结构
    typedef enum { Link, Thread} PointerTag; // 枚举 标志
    typedef struct node
    { 
        char data;
        int LTag;
        int RTag;
        struct node *left, *right;
    
    }*Node;

以这种结构构成的**二叉链表**作为二叉树的存储结构， 叫做**线索链表**，其中指向前驱和后继的指针叫做**线索**。加上线索的二叉树称之为**线索二叉树**。

###### 中序的实现代码 ######

#include<bits/stdc++.h>
    using namespace std;
    typedef enum { Link, Thread} PointerTag; // 枚举 标志
    typedef struct node
    { 
        char data;
        int LTag;
        int RTag;
        struct node *left, *right;
    
    }*Node;
    
    char preOrder[60];
    int i;
    
    // 每次建树的时候初始化左右Tag为 Link
    Node pre;// 指向上一个被访问的结点
    
    void inOrder(Node T)// 通过中序遍历 构建 中序的线索二叉树
    { 
        if(!T)return ; // 如果当前结点为空 直接返回
    
        inOrder(T->left);// 中序遍历左子树
    
        if(!T->left) // 处理当前结点的 前驱指针
        { 
            T->LTag = Thread;
            T->left = pre;
    
        }
        if(!pre->right)  // 处理上一个结点的后继指针
        { 
            pre->RTag = Thread;
        }
        pre = T;
        inOrder(T->right); // 中序遍历右子树
    }
    
    void inOrderThread(Node T)// 线索二叉树的遍历
    { 
        Node p = T->left;
    
        while(p != T)
        { 
            while(p->LTag == Link)p = p->left; // 找最左下角的
    
            print("%c", p->data); // 访问最左下角的
    
    
            while(p->RTag == Thread && p->right != T)// 如果右子树是线索 并且不指向T（T是树的根的前驱辅助结点）
            { 
                p = p->right;// 指向右子树
                printf("%c", p->data);// 访问
            }
    
            p = p->right;// 如果右右子树是儿子 那么就指向儿子 重复循环
        }
    
    }
    
    void create()
    { 
    
    }
    
    void init()
    { 
        i = 0;
    }
    
    int main()
    { 
        ios_base::sync_with_stdio(false);
        while(cin>>s)
        { 
            init();
            Node root = create();//建树
            Node T = (Node)malloc(sizeof(node));// 创建辅助的头结点
            pre = T;
            
    
        }
    
        return 0;
    }

#### 实现方法二 ####

先序的线索二叉树的代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef struct node // 结点
    { 
        char data;
        struct node *left,*right;
        struct node * last, *next;// 指向 前驱 和后继
    }node, *Node;
    int i;
    char s[56];
    Node Last;
    
    Node create()
    { 
        if(s[i] == ',')
        { 
            i++;
            return NULL;
        }
    
        Node T = (Node)malloc(sizeof(node));
        T->data = s[i++];
        T->left = create();
        T->right = create();
        T->next = NULL;
        T->last = NULL;
    
        return T;
    }
    
    void preOrder(Node T)
    { 
        if(!T)return;
    
    
        T->last = Last;
        Last->next = T;
        Last  = T;
        preOrder(T->left);
        preOrder(T->right);
    
    
    }
    int main()
    { 
        ios_base::sync_with_stdio(false);
    
        while(cin>>s)
        { 
            i = 0;
            Node root = create();
    
            Node T  = (Node)malloc(sizeof(node));
    
            T->left = NULL;
            T->right = NULL;
            T->last = NULL;
            T->next = root;
            Last = T;
            preOrder(root);
    
            Node tmp = T;
    
            while(tmp->next)
            { 
                printf("%c",tmp->next->data);
                tmp = tmp->next;
            }
        }
    
        return 0;
    }