二叉树的遍历及线索化

先序线索化转圈问题先序线索化转圈问题是一种经典的数学问题，它可以帮助我们探索数学中的先序遍历、线索化和环的概念。

让我们来了解一下先序遍历和线索化的含义。

我们将研究如何将这些概念应用到转圈问题上，并通过一些具体的例子来进一步理解。

1. 先序遍历在二叉树中，先序遍历是指先访问根节点，然后遍历左子树，最后遍历右子树。

这个遍历顺序可以用一个节点序列来表示，我们可以把先序遍历的结果存储在一个数组中。

在这个数组中，根节点的位置总是在左子树和右子树之前。

2. 线索化线索化是将二叉树中的空指针调整为指向前驱节点或后继节点的方式。

通过线索化，我们可以用指针在树中前进而不需要使用递归或栈。

对于一个二叉树的节点，如果它没有左子树，我们可以把它的左指针指向它的前驱节点；如果它没有右子树，我们可以把它的右指针指向它的后继节点。

3. 先序线索化转圈问题现在让我们来考虑一个有趣的问题：如何将一棵已经线索化的二叉树转化为一个环形链表呢？我们需要把每一个节点的右指针指向它的后继节点，并使得最后一个节点的后继节点指向第一个节点。

为了解决这个问题，我们可以使用先序遍历的思想。

我们可以从根节点开始，依次遍历每个节点，并将它的右指针指向它的后继节点。

我们还需要记录前一个访问的节点，以便将它的后继节点指向当前节点。

具体的步骤如下：- 如果当前节点为根节点，将它的右指针指向它的后继节点，并记录当前节点为前一个节点。

- 如果当前节点有左子树，递归处理左子树。

- 如果当前节点有右子树，继续遍历它的右子树。

通过这种方式，我们可以将一个已经线索化的二叉树转化为一个环形链表。

这个环形链表可以让我们在任意节点中，通过右指针循环遍历所有节点。

在实际应用中，先序线索化转圈问题可以用于优化二叉树的遍历算法。

由于线索化的特性，我们可以避免使用递归或栈，从而提高遍历的效率。

通过对先序线索化转圈问题的深入研究，我们可以更好地理解先序遍历、线索化和环的概念。

这个问题不仅提供了一个数学的挑战，还具有一定的实际应用价值。

数据结构树的知识点总结一、树的基本概念。

1. 树的定义。

- 树是n（n ≥ 0）个结点的有限集。

当n = 0时，称为空树。

在任意一棵非空树中：- 有且仅有一个特定的称为根（root）的结点。

- 当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、…、Tm，其中每个集合本身又是一棵树，并且称为根的子树（sub - tree）。

2. 结点的度、树的度。

- 结点的度：结点拥有的子树个数称为结点的度。

- 树的度：树内各结点的度的最大值称为树的度。

3. 叶子结点（终端结点）和分支结点（非终端结点）- 叶子结点：度为0的结点称为叶子结点或终端结点。

- 分支结点：度不为0的结点称为分支结点或非终端结点。

- 除根结点之外，分支结点也称为内部结点。

4. 树的深度（高度）- 树的层次从根开始定义起，根为第1层，根的子结点为第2层，以此类推。

树中结点的最大层次称为树的深度（或高度）。

二、二叉树。

1. 二叉树的定义。

- 二叉树是n（n ≥ 0）个结点的有限集合：- 或者为空二叉树，即n = 0。

- 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

2. 二叉树的特点。

- 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。

- 二叉树的子树有左右之分，次序不能颠倒。

3. 特殊的二叉树。

- 满二叉树。

- 一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树。

满二叉树的特点是每一层上的结点数都是最大结点数。

- 完全二叉树。

- 深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。

完全二叉树的叶子结点只可能在层次最大的两层上出现；对于最大层次中的叶子结点，都依次排列在该层最左边的位置上；如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子。

三、二叉树的存储结构。

1. 顺序存储结构。

- 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

6.4 线索化二叉树从前面的讨论可知，遍历二叉树就是将非线性结构的二叉树线性化，即按一定规则将二叉树中的结点排列成一个线性序列依次访问。

如图6.20(a)所示的二叉树，经中序遍历得到线性序列：BADEC，经前序遍历得到线性序列：ABCDE，经后序遍历得到线性序列：BEDCA。

在这些线性序列中，二叉树中的每个结点（除第一个和最后一个外）有且仅有唯一的一个前趋和唯一的一个后继，很容易找到各个结点的直接前驱和直接后继。

但当以二叉链表作为二叉树的存储结构时，只能找到结点的左、右孩子，而不能直接找到前驱和后继，只有在遍历的动态过程中得到这些信息。

如果将这些信息在第一次遍历时保存起来，在需要再次对二叉树进行“遍历”时就可以将二叉树视为线性结构进行访问，从而简化遍历操作。

那么，如何存储遍历中得到的结点前驱和后继的信息呢？一个简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指向存储遍历中得到的结点前驱和后继。

fwd L child data R child bkwd这是采用多重链表来表示二叉树。

这种方法虽简单易行，但这种结构的存储密度将大大降低，浪费存储空间。

另一种方法，是利用原有链域L child 和R child的空链域。

在n个结点的二叉链表中有2n个孩子链域，其中仅有n-1个链域是用来指示结点的左右孩子，而另外n+1个链域是空链域。

现在把这些空链域利用起来，使其指向结点的前驱或后继；对那些原来就不为空的链域，则仍然指向左或右孩子。

如果把指向前驱和后继的指针称为线索（Thread），那么，如何区分指向左、右孩子的指针和指向前驱、后继的线索呢？在原结点结构上增加标志域定义为：0 Lchild为左指针，指向左孩子0 Rchild为右指针，指向右孩子ltag＝rtag＝1 Lchild为左线索，指向前驱 1 Rchild为右线索，指向后继以这种结点构成的二叉链表作为二叉树的存储结构，叫做线索链表，其C语言类型说明如下：Typedef struct ThreadTNode{enum{0，1} ltag, rtag;Elem Type data;Struct ThreadTNode *Lchild, *Rchild;}ThreadTNode, *ThreadTree;为了节省内存空间，我们用C语言的位段方法将结点中的左标志域和右标志域与数据域合并在一个存储单元中（即各用一位表示左标志和右标志，其余各位表示结点值）。

⼆叉树遍历（前中后序遍历，三种⽅式）⽬录刷题中碰到⼆叉树的遍历，就查找了⼆叉树遍历的⼏种思路，在此做个总结。

对应的LeetCode题⽬如下：，，，接下来以前序遍历来说明三种解法的思想，后⾯中序和后续直接给出代码。

⾸先定义⼆叉树的数据结构如下：//Definition for a binary tree node.struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};前序遍历，顺序是“根-左-右”。

使⽤递归实现：递归的思想很简单就是我们每次访问根节点后就递归访问其左节点，左节点访问结束后再递归的访问右节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;helper(root,res);return res;}void helper(TreeNode *root, vector<int> &res){res.push_back(root->val);if(root->left) helper(root->left, res);if(root->right) helper(root->right, res);}};使⽤辅助栈迭代实现：算法为：先把根节点push到辅助栈中，然后循环检测栈是否为空，若不空，则取出栈顶元素，保存值到vector中，之后由于需要想访问左⼦节点，所以我们在将根节点的⼦节点⼊栈时要先经右节点⼊栈，再将左节点⼊栈，这样出栈时就会先判断左⼦节点。

代码如下：class Solution {public:vector<int> preorderTraversal(TreeNode* root) {if(root == NULL) return {};vector<int> res;stack<TreeNode*> st;st.push(root);while(!st.empty()){//将根节点出栈放⼊结果集中TreeNode *t = st.top();st.pop();res.push_back(t->val);//先⼊栈右节点，后左节点if(t->right) st.push(t->right);if(t->left) st.push(t->left);}return res;}};Morris Traversal⽅法具体的详细解释可以参考如下链接：这种解法可以实现O(N)的时间复杂度和O(1)的空间复杂度。

实验九线索二叉树的创建及遍历实验目的：掌握二叉树的线索链表存储结构，能够实现二叉树的线索链表的创建、遍历等基本操作实验要求：1、认真阅读和掌握教材上和本实验相关的内容及算法2、上机将线索二叉树的线索链表存储表示的创建和遍历算法实现。

3、进行简单的输入输出验证。

实验内容：编程实现二叉树的线索链表存储表示的基本操作，这些基本操作包括：线索二叉树的创建、线索二叉树的中序遍历算法的实现。

要求对程序中的一些关键语句要有注释，并能够进行简单的输入输出验证。

参考代码#include <stdlib.h>#include <stdio.h>#define OVERFLOW 0//线索二叉树的二叉链表存储定义typedef enum PointerTag {LINK=0,THREAD=1};struct BiThrNode{char data;struct BiThrNode * lchild, * rchild;PointerTag LTag, RTag;};typedef struct BiThrNode BiThrNode;typedef BiThrNode * BiThrTree;/*****************************************************************\** 按先序次序输入二叉树中的结点的值（一个字符）构造二叉链表表示的二叉树，* 字符'#'表示空树。

** 例如，一棵二叉树的三种遍历次序为：* 先序：-+a*b-cd/ef 中序：a+b*c-d-e/f 后序：abcd-*+ef/* 程序中应该输入：-+a##*b##-c##d##/e##f##** 又如，一棵二叉树的三种遍历次序为：* 先序：ABDFGCEH 中序：BFDGACHE 后序：FGDBHECA* 程序中应该输入：AB#DF##G##C#EH###*\******************************************************************/ void CreateBiTree(BiThrTree &T){char ch;ch = getchar();if (ch=='#') T=NULL;else{if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);T->data = ch;T->LTag = LINK;T->RTag = LINK;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return;}//CreateBiTreevoid PrintBiTree(BiThrTree T){//按中序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。

莫里斯算法莫里斯算法（Morris Traversal）是一种二叉树遍历的算法，通过只使用一个指针和利用线索二叉树的思想，实现对二叉树的中序遍历，时间复杂度为O(n)，空间复杂度为O(1)。

1. 线索二叉树线索二叉树是指将一颗二叉树中所有的空指针域指向该节点的直接前驱节点或直接后继节点的二叉树。

线索化后，原本空闲的指针域存储前驱或后继的指针，可以方便地实现对二叉树的遍历。

在递归遍历的过程中，需要记录每个节点是否已经被遍历。

线索二叉树分为前序线索二叉树、中序线索二叉树、后序线索二叉树。

其中，利用中序线索二叉树可以实现对二叉树的中序遍历。

2. Morris遍历算法Morris遍历算法是一种利用线索二叉树对二叉树进行中序遍历的算法，它的核心思想是在遍历节点的过程中，利用空闲的指针域存储前驱或后继的指针，从而实现对二叉树的遍历。

Morris遍历算法对于空间的要求比较严格，它只需要使用一个指针来实现对二叉树的遍历，因此空间复杂度为O(1)，非常适合解决空间限制的问题。

在时间复杂度方面，Morris遍历算法需要在遍历每个节点和寻找其前驱节点时，都需要遍历部分节点，因此时间复杂度为O(n)。

具体而言，Morris遍历算法利用线索化指针判断节点是否被访问过，从而实现对二叉树的遍历。

Morris遍历算法的具体流程如下：1）初始化当前节点为根节点2）重复以下操作，直到当前节点为空a. 如果当前节点没有左孩子节点，则输出当前节点，将其右孩子节点作为下一次要访问的节点，更新当前节点为右孩子节点b. 如果当前节点存在左孩子节点，则寻找当前节点的左子树中的最右侧节点，该节点为当前节点的直接前驱节点i. 如果该节点的右孩子指向当前节点，则说明当前节点是第二次访问该节点，将其右孩子设为null，输出该节点，更新当前节点为右孩子节点ii. 如果该节点的右孩子指向null，则说明当前节点为第一次访问该节点，将其右孩子设为当前节点，更新当前节点为左孩子节点Morris遍历算法的特点是利用空闲的指针域存储前驱或后继的指针，实现对二叉树的遍历。