1. IT分享知识网首页
  2. 未分类

数据结构与算法–二叉树之线索二叉树（前序、中序、后序）思路以及代码实现。

老牧童 • • 未分类

数据结构与算法–二叉树之线索二叉树（前序、中序、后序）思路以及代码实现。本文详细介绍了线索二叉树的概念和实现 包括先序 后序和中序线索二叉树的建立及遍历方法

大家好，欢迎来到IT知识分享网。

线索二叉树

1.先序线索二叉树

在这里插入图片描述
思路：
沿类似于上图中的先序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。

关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（+）加号的看出路径，可以得到先序遍历的顺序为：
1 2 4 5 3 6 8 7

我们以图中结点4为例子：
4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从先序遍历的顺序看出，4的前驱结点为2，4的后继结点为5，其他同理可得，所以得到如图的连线。
在这里插入图片描述

我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：

在这里插入图片描述
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。

rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。

data:用来存储数据。

在这里插入图片描述
和我们使用的是先序遍历的递归很像。顺序为：
根结点->左子树->右子树
代码如下：

void _preThread(BTNode<T> *p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    //当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空 if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } //当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空 if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } //根结点 pre=p; //左子树 if(p->lTag==0) _preThread(p->lchild,pre); //右子树 if(p->rTag==0) _preThread(p->rchild,pre); } }

虽然我们实现了先序线索二叉树 ，但是要使用它来遍历打印出数据。
思路：
首先指向根结点，然后根结点的，左子结点，左子结点的左子结点…不为空的话，就沿路打印出所到结点；然后当左结点为空时，指向它的右子结点（部分右子结点是他的后继结点）；然后继续判断左结点是否为空，这样循环就可以打印出我们想要的数据了。

打印路径：如图红色线条
因为我们没有用前驱结点，我就把它删掉了。后面的后序遍历我们就只使用前驱结点，没使用后继结点。
在这里插入图片描述

代码表示：

 //线索二叉树前序遍历 void preThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root=_root; _preThread(root,p); while(root!=NULL) { 
    while(!root->lTag) { 
    cout<<root->data<<" "; root=root->lchild; } cout<<root->data<<" "; root=root->rchild; } cout<<endl; }

整体代码：

#include<iostream> using namespace std; #define maxSize 10 template<class T> struct BTNode { 
    T data; T lTag; T rTag; BTNode<T>* lchild; BTNode<T>* rchild; BTNode(const T& x) :data(x) ,lTag(0) ,rTag(0) , lchild(NULL) , rchild(NULL) { 
   } }; template<class T> class binary_tree { 
    typedef BTNode<T> node; public: binary_tree(T* a, size_t n, const T&invalid) { 
    size_t index = 0; _root = _create_tree(a, n, invalid, index); } //创建一棵二叉树 BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index) { 
    BTNode<T>* root = NULL; if (a[index] != invalid) { 
    root = new BTNode<T>(a[index]); root->lchild = _create_tree(a, n, invalid, ++index); root->rchild = _create_tree(a, n, invalid, ++index); } return root; } //线索二叉树前序遍历 void preThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root=_root; _preThread(root,p); while(root!=NULL) { 
    while(!root->lTag) { 
    cout<<root->data<<" "; root=root->lchild; } cout<<root->data<<" "; root=root->rchild; } cout<<endl; } void _preThread(BTNode<T> *p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } pre=p; if(p->lTag==0) _preThread(p->lchild,pre); if(p->rTag==0) _preThread(p->rchild,pre); } } protected: node *_root; }; //测试部分 void test_binary_tree() { 
    int array[] = { 
    1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'}; binary_tree<int> t(array, sizeof(array) / sizeof(int), '^'); t.preThread(); } int main(void) { 
    test_binary_tree(); system("pause"); }

2.后序线索二叉树

因为和前序二叉树有点像，所以就先说明后序线索二叉树。
在这里插入图片描述
思路：
沿类似于上图中的后序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。

关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（-）负号的看出路径，可以得到后序遍历的顺序为：
4 5 2 8 6 7 3 1

我们以图中结点4为例子：
4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从后序遍历的顺序看出，4的没有前驱结点，4的后继结点为5，其他同理可得，所以得到如图的连线。
在这里插入图片描述

我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：

在这里插入图片描述
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。

rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。

data:用来存储数据。

和我们前面的先序线索二叉树非常类似，只是代码的顺序不同，因为这个是左子树->右子树->根结点
代码如下：

void _postThread(BTNode<T> *p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    //左子树 _postThread(p->lchild,pre); //右子树 _postThread(p->rchild,pre); //当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空 if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } //当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空 if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } //根结点 pre=p; } }

虽然我们实现了后序线索二叉树 ，但是要使用它来遍历打印出数据。
思路：
因为我们和先序遍历一样的方向，难以达到我们想要的效果，如果我们从与它相反的路径来看的话，我们所想要解决问题是不是就很明确，和我们先序遍历的解决方法和类似，不过打印出的数据是逆后序遍历，所以我们需要一个自定义栈来存储逆后序遍历，出栈则为后序遍历。

打印路径：如图红色线条
因为我们没有用后继驱结点，我就把它删掉了。
在这里插入图片描述
代码表示：

void postThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root2=_root; BTNode<T> *stack[maxSize]; int top=-1; _postThread(root2,p); while(root2!=NULL) { 
    while(!root2->rTag) { 
    stack[++top]=root2; root2=root2->rchild; } stack[++top]=root2; root2=root2->lchild; } while(top!=-1) { 
    p=stack[top--]; cout<<p->data<<" "; } cout<<endl; }

整体代码：

#include<iostream> using namespace std; #define maxSize 10 template<class T> struct BTNode { 
    T data; T lTag; T rTag; BTNode<T>* lchild; BTNode<T>* rchild; BTNode(const T& x) :data(x) ,lTag(0) ,rTag(0) , lchild(NULL) , rchild(NULL) { 
   } }; template<class T> class binary_tree { 
    typedef BTNode<T> node; public: binary_tree(T* a, size_t n, const T&invalid) { 
    size_t index = 0; _root = _create_tree(a, n, invalid, index); } //创建一棵二叉树 BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index) { 
    BTNode<T>* root = NULL; if (a[index] != invalid) { 
    root = new BTNode<T>(a[index]); root->lchild = _create_tree(a, n, invalid, ++index); root->rchild = _create_tree(a, n, invalid, ++index); } return root; } //线索二叉树后序遍历 void postThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root2=_root; BTNode<T> *stack[maxSize]; int top=-1; _postThread(root2,p); while(root2!=NULL) { 
    while(!root2->rTag) { 
    stack[++top]=root2; root2=root2->rchild; } stack[++top]=root2; root2=root2->lchild; } while(top!=-1) { 
    p=stack[top--]; cout<<p->data<<" "; } cout<<endl; } void _postThread(BTNode<T> *p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    _postThread(p->lchild,pre); _postThread(p->rchild,pre); if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } pre=p; } } protected: node *_root; }; //测试部分 void test_binary_tree() { 
    int array[] = { 
    1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'}; binary_tree<int> t2(array, sizeof(array) / sizeof(int), '^'); t2.postThread(); } int main(void) { 
    test_binary_tree(); system("pause"); }

3.中序线索二叉树

在这里插入图片描述
思路：
沿类似于上图中的中序遍历路径行走，如果发现左孩子结点或右孩子结点为空（也就是度为1或者0的结点），把它们的左空孩子结点指向它的前驱结点，把它们的右空孩子结点指向它的后继结点。当没有前驱或者后继结点时不用指。

关于如何找到它们的前驱或后继结点？
如下图：
我们可以通过图中（=）等于号的看出路径，可以得到中序遍历的顺序为：
4 2 5 1 8 6 3 7

我们以图中结点4为例子：
4为叶子结点，所以它的左右孩子结点都为空结点，我们可以从后序遍历的顺序看出，4的没有前驱结点，4的后继结点为2，其他同理可得，所以得到如图的连线。

在这里插入图片描述
我们把上图用代码表示出来，我们使用链式存储结构，让上图可视化：

在这里插入图片描述
由五个域组成
lichild:用来存储左孩子所在的链结点存储地址。
lTag:当ITag为0表示左孩子结点不空;为1表示空。

rchild:用来存储右孩子所在的链结点存储地址。
rTag:当rTag为1表示右孩子结点不空;为1表示空。

data:用来存储数据。

和我们中序遍历的递归非常类似，顺序为：
左子树->根结点->右子树

代码：

void _inThread(BTNode<T> *&p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    //左子树 _inThread(p->lchild,pre); //当遇到左结点为NULL时，把左孩子结点指向前驱结点；把lTag设为1，表示左孩子结点为空 if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } //当遇到结点不为空且右孩子结点为NULL时，把右孩子结点指向后继结点；把rTag设为1，表示右孩子结点为空 if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } //根结点 pre=p; //右子树 _inThread(p->rchild,pre); } }

虽然我们实现了中序线索二叉树 ，但是要使用它来遍历打印出数据。

图中：
蓝色箭头+红色箭头为路径，其中红色箭头的起点为打印结点。
在这里插入图片描述

看代码可能更轻易看懂：

void inThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root1=_root; _inThread(root1,p); while(root1!=NULL&&root1->lTag==0) { 
    root1=root1->lchild; } while(root1!=NULL) { 
    cout<<root1->data<<" "; if(root1->rTag==1){ 
    root1=root1->rchild; }else{ 
    root1=root1->rchild; while(root1!=NULL&&root1->lTag==0) { 
    root1=root1->lchild; } } } cout<<endl; }

整体代码：

#include<iostream> using namespace std; #define maxSize 10 template<class T> struct BTNode { 
    T data; T lTag; T rTag; BTNode<T>* lchild; BTNode<T>* rchild; BTNode(const T& x) :data(x) ,lTag(0) ,rTag(0) , lchild(NULL) , rchild(NULL) { 
   } }; template<class T> class binary_tree { 
    typedef BTNode<T> node; public: binary_tree(T* a, size_t n, const T&invalid) { 
    size_t index = 0; _root = _create_tree(a, n, invalid, index); } //创建一棵二叉树 BTNode<T>* _create_tree(T*a, size_t n, const T& invalid, size_t& index) { 
    BTNode<T>* root = NULL; if (a[index] != invalid) { 
    root = new BTNode<T>(a[index]); root->lchild = _create_tree(a, n, invalid, ++index); root->rchild = _create_tree(a, n, invalid, ++index); } return root; } //线索二叉树中序遍历 void inThread() { 
    BTNode<T> *p=NULL; BTNode<T> *root1=_root; _inThread(root1,p); while(root1!=NULL&&root1->lTag==0) { 
    root1=root1->lchild; } while(root1!=NULL) { 
    cout<<root1->data<<" "; if(root1->rTag==1){ 
    root1=root1->rchild; }else{ 
    root1=root1->rchild; while(root1!=NULL&&root1->lTag==0) { 
    root1=root1->lchild; } } } cout<<endl; } void _inThread(BTNode<T> *&p,BTNode<T> *&pre) { 
    if(p!=NULL) { 
    _inThread(p->lchild,pre); if(p->lchild==NULL) { 
    p->lchild=pre; p->lTag=1; } if(pre!=NULL&&pre->rchild==NULL) { 
    pre->rchild=p; pre->rTag=1; } pre=p; _inThread(p->rchild,pre); } } protected: node *_root; }; //测试部分 void test_binary_tree() { 
    int array[] = { 
    1, 2, 4, '^', '^' , 5, '^', '^', 3, 6, 8, '^', '^', '^',7,'^','^'}; binary_tree<int> t1(array, sizeof(array) / sizeof(int), '^'); t1.inThread(); } int main(void) { 
    test_binary_tree(); system("pause"); }

4.代码打印结果：

在这里插入图片描述

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/148498.html

赞 (0)
老牧童老牧童
0
上一篇 2025-03-30 18:00
下一篇 2025-03-30 18:10

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信