【数据结构】线索二叉树

博主： Fivk
发布时间：2021 年 07 月 27 日
996 次浏览
3344字数
分类：数据结构

线索二叉树有什么用呢？
</div>

将树转换成线性表。

将遍历信息在首次遍历时线索化，则可以在需要是直接获得节点的前驱和后继。

</div>

### 中序线索链表的建立——构造函数

1. 建立二叉链表，将每个节点的左右标志置为0；
2. 遍历二叉链表，建立线搜；
   1. 如果二叉链表p为空，则空操作返回；
   2. 对p的左子树建立线搜；
   3. 对根节点p建立搜索；
      1. 若p没有右孩子，则为p加上前驱线索；
      2. 若pre没有右孩子，则为pre加上后续线索；
      3. 令pre指向刚刚访问的节点p；
   4. 对p的左子树建立线索。

```cpp
void ThreadBiTree::inThred(ThreadNode *p)
{
    if(p==NULL)
        return;
    inThread(p->lchild);    //左子树线索化

//核心：处理根节点

// 1.建立p的前序线索

if(p->lchild==NULL)
    {
        p->ltag=1;
        p->child=pre;
    }

// 2.建立pre的后续线索

if(pre!=NULL && pre->child==NULL)
    {
        p->rtag=1;
        pre->rchild=p;
    }

// 3.令pre指向刚刚访问的节点p

pre=p;

inThread(p->rchild);    //右子树线索化

}
```

思考：pre指针应该如何定义？

</div>

**pre指针的定义方法**

* pre定义成全局变量（C/C++语言）[不推荐]
* pre定义属性（C++/Java语言）

**使用类封装**

```cpp
class ThreadBiTree
{
private:
    ThreadNode *root;
    ThreadNode *pre;
public:
    ThreadBiTree();     //构造函数，建立中序线索链表
    ~ThreadBiTree();    //析构函数，释放各节点的存储结构空间
    ThreadNode *next(ThreadNode *p);    //查找p的后继
    void inOrder(); //中序遍历线索链表
private:
    ThreadNode *creat(ThreadNode *bt);
    void inThread(ThreadNode *p);   //线索化二叉树
}
```

其中构造函数定义：

```cpp
ThreadBiTree()
{
	//构造二叉树
	pre=NULL;
	root=creat(root);
	inThread(root);
}
```

* pre定义成静态变量

```cpp
void ThreadBiTree::inThred(ThreadNode *p)
{
    static ThreadNode *pre=NULL;
    if(p==NULL)
        return;
    inThread(p->lchild); 
    if(p->lchild==NULL)
    {
        p->ltag=1;
        p->child=pre;
    }
    if(pre!=NULL && pre->child==NULL)
    {
        p->rtag=1;
        pre->rchild=p;
    }
    pre=p;
    inThread(p->rchild);

}
```

</div>

线索链表中，第一个节点左孩子为空，最后一个节点的右孩子为空。

</div>

### 中序线性链表类的声明

```cpp
class ThreadBiTree
{
private:
    ThreadNode *root;   //指向线索链表的头指针
public:
    ThreadBiTree(); //构造函数，建立中序线索链表
    ~ThreadBiTree();    //析构函数，释放各节点的存储空间
    ThreadNode *next(ThreadNode *p);    //查找p的后继
    void inOrder(); //中序遍历线索链表
privaet:
    ThreadNode *creat(ThreadNode *bt);
    void inThread(ThreadNode *p);   //线索化二叉树

}
```

### 中序线索链表查找后继

1. 如果节点p的右标志为1，则表明该结点的右指针是线索；
2. 如果节点p的右标志为0，则表明该节点有右孩子。根据中序遍历的操作定义，它的后继结点应该是遍历其右子树时第一个访问结点，即右子树中最左下节点。

![](https://blog.fivk.cn/usr/uploads/2021/07/3438485116.png)

```cpp
// 中序线索链表查找后继
ThreadNode * ThreadBiTree::next(ThreadNode *p)
{
    if(p->rtag==1)  //右标志为1，可直接得到后继结点
        q=p->rchild;
    else{           //有标志为0，则要查找到左子树最左下角的结点
        q=p->rchild;
        while(q->ltag==0)   //查找最左下结点位置
        q=q->lchild;
    }
    return q;
}
```

### 中序线索链表的遍历

```cpp
// 中序线索链表的遍历算法
void ThreadBiTree::inOrder()
{
    ThreadNode *p;
    if(root==NULL)
        return;
    p=root;
    while(p->ltag==0)   //查找中序遍历的第一个结点p
        p=p->lchild;
    visit(p->data);     //访问第一个结点
    while(p->rchild!=NULL)  //当p存在后续，依次访问后继结点
    {
        p=next(p);
        visit(p->data);
    }
}
```

总结：

1. 线索化是提高重复访问非线性结构效率的重要手段之一。
2. 这里建立的是全线搜索树，有些应用中只需要建立左右线索中的一种。

</div>

![](https://blog.fivk.cn/usr/uploads/2021/07/2779524908.png)

最后修改：2021 年 09 月 12 日

如果觉得我的文章对你有用，请随意赞赏

【数据结构】线索二叉树

Fivk • 2021 年 07 月 27 日

线索二叉树有什么用呢？
</div>

将树转换成线性表。

将遍历信息在首次遍历时线索化，则可以在需要是直接获得节点的前驱和后继。

</div>

### 中序线索链表的建立——构造函数

```cpp
void ThreadBiTree::inThred(ThreadNode *p)
{
    if(p==NULL)
        return;
    inThread(p->lchild);    //左子树线索化

//核心：处理根节点

// 1.建立p的前序线索

if(p->lchild==NULL)
    {
        p->ltag=1;
        p->child=pre;
    }

// 2.建立pre的后续线索

if(pre!=NULL && pre->child==NULL)
    {
        p->rtag=1;
        pre->rchild=p;
    }

// 3.令pre指向刚刚访问的节点p

pre=p;

inThread(p->rchild);    //右子树线索化

}
```

思考：pre指针应该如何定义？

</div>

**pre指针的定义方法**

* pre定义成全局变量（C/C++语言）[不推荐]
* pre定义属性（C++/Java语言）

**使用类封装**

其中构造函数定义：

```cpp
ThreadBiTree()
{
	//构造二叉树
	pre=NULL;
	root=creat(root);
	inThread(root);
}
```

* pre定义成静态变量

}
```

</div>

线索链表中，第一个节点左孩子为空，最后一个节点的右孩子为空。

</div>

### 中序线性链表类的声明

}
```

### 中序线索链表查找后继

![](https://blog.fivk.cn/usr/uploads/2021/07/3438485116.png)

### 中序线索链表的遍历

总结：

1. 线索化是提高重复访问非线性结构效率的重要手段之一。
2. 这里建立的是全线搜索树，有些应用中只需要建立左右线索中的一种。

</div>

![](https://blog.fivk.cn/usr/uploads/2021/07/2779524908.png)

【数据结构】线索二叉树

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【微服务】多级缓存

【Typecho 】网站更换域名

【知识总结】@mapper和@repository区别

【微服务】SpringCloud（上）

【踩坑日志】端口被占用导致Tomcat报错或者springboot启动报错

【数据结构】线索二叉树