数据结构-线索二叉树（后序线索二叉树及遍历）

2024-03-08 13:08
文章标签 二叉树 遍历 数据结构 线索 后序

本文主要是介绍数据结构-线索二叉树（后序线索二叉树及遍历），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 后序线索二叉树

  • 线索化的概念及相关图解

在上一篇中详细介绍了中序线索二叉树，线索化图解及相关概念都放在那篇博客啦，放个传送门

线索二叉树详细解析（含图解）：传送门

包括还有先序线索二叉树：传送门

 

  • 后序线索二叉树

（1）后序线索二叉树的构造

             ①思路：在这里说下构造的原因，与先序中序线索二叉树不同，在遍历时后序时先把孩子全部遍历了再回到父母节点，  而回寻父母节点的方法只能在定义的节点结构中添加一指针，指向该节点的父母节点。

template<class T>
struct BT_Thread_Node
{T Data;BT_Thread_Node* Left_Child;BT_Thread_Node* Right_Child;BT_Thread_Node* Parent;	       //指向该节点的父母节点int Ltag;int Rtag;
};

             ②先序递归构造二叉树

                 就一点不同：传参多了一个父母节点，构建完当前节点后，该节点得指向父母节点，并且该节点作为其左右孩子的                                           父母节点作为参数传至下一构造函数。

template<class T>
int Thread_Binary_tree<T>::Create_Thread_BTree(BT_Thread_Node<T>* &Tree,BT_Thread_Node<T>* Parent_Node)
{int Data;cin >> Data;if (Data == -1)Tree = NULL;else{Tree = new BT_Thread_Node<T>;Tree->Parent = Parent_Node;        //指向父母节点Tree->Data = Data;Tree->Ltag = Link;Tree->Rtag = Link;Create_Thread_BTree(Tree->Left_Child,Tree);  //Tree是孩子的父母节点Create_Thread_BTree(Tree->Right_Child,Tree);}return 1;
}

 

（2）后序线索化

             ①思路：

                        a.先线索化左右孩子节点

                        b.根节点：若左孩子节点空，左孩子节点指向前驱节点（前一次访问的节点Pre_Node），标记该孩子为                                                       线索模式（Thread）

                                         若前一次访问的节点不为空并且它的右孩子为空，则该右孩子指向当前节点（后继节点），                                                         标记该孩子为线索模式（Thread）

                        c.保存当前节点，作为下一次的Pre_Node (记录历史的意思）

             ②实现代码：

#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）
template<class T>
void Thread_Binary_tree<T>::PostOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
{if (Tree == NULL)return;PostOrder_Thread_Op(Tree->Left_Child);		//左PostOrder_Thread_Op(Tree->Right_Child);		//右if (Tree->Left_Child == NULL)		//根{Tree->Left_Child = Pre_Node;Tree->Ltag = Thread;}if (Pre_Node != NULL && Pre_Node->Right_Child == NULL){Pre_Node->Right_Child = Tree;Pre_Node->Rtag = Thread;}Pre_Node = Tree;
}

注意！！！！！Pre_Node 是作为类内私有数据，相当于全局变量，对每个节点的线索都会使它改变！

 

（3）中序线索遍历

             ①思路：

                        a.靠左访问：找到最左边的节点，也就是后序遍历顺序中最先访问的那个节点

                        b.按后继线索访问：当前节点的右孩子节点指向的是后继，则访问该节点并指向下一右孩子直到该孩子不为后继节点。记得保存每次访问的节点哦，便于后面判断袖珍树（子树）是否访问完成。

                        c.回到根部：后面会放出一个例子，在ab两部分操作后，会出现两种情况

                                  1：该节点为根节点，访问最后这一节点后，整个后序遍历完成啦，跳出。                                                                                   2：是节点是子树的根节点，访问这一节点后完成的是子树的后序遍历，这时肯定是回到该子树根节         点的父母节点，然后指向该父母节点的右孩子进行下一次的遍历。

             ②实现代码：

template<class T>
void Thread_Binary_tree<T>::_PostOrder_Op(BT_Thread_Node<T>* &Tree)
{if (Tree == NULL)return;BT_Thread_Node<T> *Cur_Node = Tree;Pre_Node = NULL;while (Cur_Node != NULL){//个人觉得，Cur_Node->Ltag == Link会影响找到最左节点，但就测试数据来看，两个都ok//while (Cur_Node->Left_Child != Pre_Node && Cur_Node->Ltag == Link)while (Cur_Node->Left_Child != Pre_Node)//change,找到起始节点（在左树的最左边）{Cur_Node = Cur_Node->Left_Child;}while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新Cur_Node = Cur_Node->Right_Child;}if (Cur_Node == Tree)		//如果当前节点为根节点，说明遍历完成{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";return;}while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该袖珍树只差根就遍历完成{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";Pre_Node = Cur_Node;Cur_Node = Cur_Node->Parent;		//访问袖珍树后回到上一层}if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子{Cur_Node = Cur_Node->Right_Child;}}
}

把要访问的节点全部入栈？？？答：为了方便析构。

             ③图解举栗

                     a.靠左访问：最左边的节点是D（先找，不访问）

                     b.按后继访问：看箭头！ D -> G -> E-> B（B的右子树不是线索啦，跳出，此时B还没有访问）

                     c.回到根部：显然回到的根部是B，并且是上面说的第二种情况！ 子树的根节点

                                          怎么判断？还记得我说的要保存上一访问节点吗？ 上一访问节点是E，B的右子树指向E

                                 判定的语句对于程序中的：while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)

                                         访问B后完成以B为根节点的子树（BDEG）的后序遍历，然后回到B的父母节点A

                                          回到A（不访问A），直接指向它的右孩子C    

 

                      大家注意！！对于a操作，不仅可以在链模式（左孩子存在的情况下）找，也可以寻找该节点的前驱！！

                      我的锅这个图其实C的左孩子是指向F，为了易懂我还没画出来。

                      回到遍历：到了C之后，又是重复abc操作啦，靠左孩子访问到了F（C的左孩子节点指向它的前驱节点F），再后继访问到C，最后回到根部A，遍历完成。

 

（4）析构线索树

              在写中序线索树的时候我是比较傻，又写了一遍线索遍历，这次干脆在遍历的时候就把节点入栈，便于删除。

             ①实现代码：

template<class T>
Thread_Binary_tree<T>::~Thread_Binary_tree()
{while (Top != -1){delete BT_Node_Stack[Top];Top--;}
}

 

到这再bb两句，重要的！ 和先序还有中序线索不同的是

一 节点的定义：多了个指向父母节点的指针

二 保存上一访问节点：为了判断子树是否遍历完成，需记录

 

到这基础就讲完啦，看看类实现代码吧~

  • 后序线索二叉树类实现

（1）类定义包括常量定义

                         老思路，实现与接口分开~实现函数全部私有化

#include<iostream>
using namespace std;
#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）
#define MAXSIZE  100template<class T>
struct BT_Thread_Node
{T Data;BT_Thread_Node* Left_Child;BT_Thread_Node* Right_Child;BT_Thread_Node* Parent;	       //指向该节点的父母节点int Ltag;int Rtag;
};template<class T>
class Thread_Binary_tree
{
private:BT_Thread_Node<T>* Tree;BT_Thread_Node<T>* Pre_Node;BT_Thread_Node<T>* BT_Node_Stack[MAXSIZE];int Top;int Create_Thread_BTree(BT_Thread_Node<T>* &Tree,BT_Thread_Node<T>* Parent);void PostOrder_Thread_Op(BT_Thread_Node<T>* &Tree);void _PostOrder_Op(BT_Thread_Node<T>* &Tree);
public:Thread_Binary_tree();~Thread_Binary_tree();void PostOrder_Thread();void _PostOrder();
};

（2）完整代码

#include<iostream>
using namespace std;
#define Link	0	//表示该节点有非空孩子节点
#define Thread	1	//表示该节点有后续节点（对于右子树来说）
#define MAXSIZE  100template<class T>
struct BT_Thread_Node
{T Data;BT_Thread_Node* Left_Child;BT_Thread_Node* Right_Child;BT_Thread_Node* Parent;	       //指向该节点的父母节点int Ltag;int Rtag;
};template<class T>
class Thread_Binary_tree
{
private:BT_Thread_Node<T>* Tree;BT_Thread_Node<T>* Pre_Node;BT_Thread_Node<T>* BT_Node_Stack[MAXSIZE];int Top;int Create_Thread_BTree(BT_Thread_Node<T>* &Tree,BT_Thread_Node<T>* Parent);void PostOrder_Thread_Op(BT_Thread_Node<T>* &Tree);void _PostOrder_Op(BT_Thread_Node<T>* &Tree);
public:Thread_Binary_tree();~Thread_Binary_tree();void PostOrder_Thread();void _PostOrder();
};template<class T>
int Thread_Binary_tree<T>::Create_Thread_BTree(BT_Thread_Node<T>* &Tree,BT_Thread_Node<T>* Parent_Node)
{int Data;cin >> Data;if (Data == -1)Tree = NULL;else{Tree = new BT_Thread_Node<T>;Tree->Parent = Parent_Node;        //指向父母节点Tree->Data = Data;Tree->Ltag = Link;Tree->Rtag = Link;Create_Thread_BTree(Tree->Left_Child,Tree);  //Tree是孩子的父母节点Create_Thread_BTree(Tree->Right_Child,Tree);}return 1;
}template<class T>
void Thread_Binary_tree<T>::PostOrder_Thread_Op(BT_Thread_Node<T>* &Tree)
{if (Tree == NULL)return;PostOrder_Thread_Op(Tree->Left_Child);		//左PostOrder_Thread_Op(Tree->Right_Child);		//右if (Tree->Left_Child == NULL)		//根{Tree->Left_Child = Pre_Node;Tree->Ltag = Thread;}if (Pre_Node != NULL && Pre_Node->Right_Child == NULL){Pre_Node->Right_Child = Tree;Pre_Node->Rtag = Thread;}Pre_Node = Tree;
}template<class T>
void Thread_Binary_tree<T>::_PostOrder_Op(BT_Thread_Node<T>* &Tree)
{if (Tree == NULL)return;BT_Thread_Node<T> *Cur_Node = Tree;Pre_Node = NULL;while (Cur_Node != NULL){//个人觉得，Cur_Node->Ltag == Link会影响找到最左节点，但就测试数据来看，两个都ok//while (Cur_Node->Left_Child != Pre_Node && Cur_Node->Ltag == Link)while (Cur_Node->Left_Child != Pre_Node)//change,找到起始节点（在左树的最左边）{Cur_Node = Cur_Node->Left_Child;}while (Cur_Node != NULL && Cur_Node->Rtag == Thread)//按线索找到次树节点{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";Pre_Node = Cur_Node;			//每次访问节点后，PreNode更新Cur_Node = Cur_Node->Right_Child;}if (Cur_Node == Tree)		//如果当前节点为根节点，说明遍历完成{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";return;}while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node)//当前节点的右孩子节点刚好上次遍历，说明该袖珍树只差根就遍历完成{BT_Node_Stack[++Top] = Cur_Node;cout << Cur_Node->Data << " ";Pre_Node = Cur_Node;Cur_Node = Cur_Node->Parent;		//访问袖珍树后回到上一层}if (Cur_Node != NULL && Cur_Node->Rtag == Link)		//回到上一层后，先访问右孩子{Cur_Node = Cur_Node->Right_Child;}}
}template<class T>
Thread_Binary_tree<T>::Thread_Binary_tree():Pre_Node(NULL),Top(-1)
{Create_Thread_BTree(Tree, NULL);
}template<class T>
Thread_Binary_tree<T>::~Thread_Binary_tree()
{while (Top != -1){delete BT_Node_Stack[Top];Top--;}
}template<class T>
void Thread_Binary_tree<T>::PostOrder_Thread()
{PostOrder_Thread_Op(Tree);
}template<class T>
void Thread_Binary_tree<T>::_PostOrder()
{_PostOrder_Op(Tree);
}int main()
{Thread_Binary_tree<int> MyTree;MyTree.PostOrder_Thread();MyTree._PostOrder();return 0;
}

这篇关于数据结构-线索二叉树（后序线索二叉树及遍历）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/787183。

相关文章

C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
C++中使用vector存储并遍历数据的基本步骤

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库（STL）提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,：本文主要介绍C... 目录（1）容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌（基于哈希表）：‌容器适配器‌：（
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2