线索二叉树

server/2024/11/28 15:02:20/

1.什么是线索二叉树?

线索二叉树是一种特殊的二叉树,它在传统二叉树的基础上,利用节点中原本为空的指针域存储指向节点前驱或后继的信息,从而在遍历时不需要递归或栈辅助,能够高效地找到前驱或后继节点。

cdab55c7bef24171af72d172e56116b0.png

前序遍历:ABDECFG                   
中序遍历:DBEAFCG
后序遍历:DEBFGCA

2.线索二叉树节点的定义

struct Treenode
{int val;Treenode* left;Treenode* right;Treenode* parent;bool ltag;        //默认无前驱和后继节点  0bool rtag;Treenode():val(0),left(nullptr),right(nullptr),parent(nullptr),tag(0),rtag(0){}
};

3.线索二叉树的分类

  • 前序线索二叉树
  • 中序线索二叉树
  • 后序线索二叉树
  • 层次线索二叉树

我这里实现不同线索二叉树,线索的创建,后继节点的查找,使用后继节点遍历 

3.1先序线索二叉树

3.1.1先序线索的创建

创建先序线索需要我们先对整个二叉树先序遍历,然后记录先前访问节点,然后链接先前节点和当前节点,所以我们需要一个pre指针

为什么要使用静态的pre指针,不能使用函数传参吗?

函数传参只能保证在同一级的递归pre改动,它无法返回改动的pre指针给上一级递归
static成员保证了递归结束后,生命周期并未结束,不同级的递归共享同一个pre指针,同时pre只能初始化一次


//前序线索二叉树  线索的创建
void preclue_create(Treenode *root) 
{static Treenode *pre=nullptr;if (root == nullptr)  return; if (root->left == nullptr)        //没有左孩子则建立前驱节点为pre{root->ltag = 1;    //前驱标记root->left = pre;}if (pre != nullptr && pre->right == nullptr) //pre非空且没有右孩子 则建立后继节点为root{pre->rtag = 1;     //后继标记pre->right = root;}pre = root;            //更新pre节点preclue_create(root->left);preclue_create(root->right);
}

 3.1.2先序后继节点的查找

后继节点和孩子有关
这里我们需要谈论的只有非叶子节点的情况,因为叶子节点一定会有前驱和后继节点直接返回即可
cdab55c7bef24171af72d172e56116b0.png

前序遍历:ABDECFG 
因为是根左右,所以我们优先考虑左子树,然后右子树   
处理叶子节点:后继结点有标记   直接返回后继节点 
处理非叶子节点后继的三种情况:1.有左孩子   2.只有右孩子   3.无左右孩子(最后一个节点)

//前序线索二叉树  后继节点的查找
Treenode* pre_next(Treenode* root)
{if(root==nullptr) return nullptr;//有后继节点标记if(root->rtag==1) return root->right;//无后继节点的三种情况 //1.该节点有左孩子 返回左孩子  //2.只有右孩子 返回右孩子 //3.返回空  if(root->ltag==0) return root->left;else if(root->rtag==0) return root->right;else return nullptr;
}

3.1.3前驱节点的查找 

 前驱节点和父亲有关
 如果没有父亲,前驱为nullptr
 如果root节点是其父亲的左节点或者其父亲无左孩子,那么root节点的前驱为父节点
 剩下的就是root节点是其父亲的右节点,那么root节点的前驱为父节点左子树的最右子节点
这里我并没有给出parent定义,如若想实现前驱代码如下

//前序线索二叉树  前驱节点的查找
Treenode* pre_next(Treenode* root)
{if(root==nullptr) return nullptr;//有前驱节点标记if(root->ltag==1) return root->left;//无前驱节点标记的三种情况 //无父节点if(root->parent==nullptr) return nullptr;//root是其父亲左孩子或者其父亲无左孩子if(root->parent->left==root||root->parent->left==nullptr) return root->parent;//返回父节点左子树最右子节点auto node=root->parent->left;while(node->rtag==0) node=node->right;return node;
}

3.1.4使用后继节点先序遍历

首先我们得找到起始节点  然后通过pre_next去遍历
不难看出先序遍历得起始节点为 根节点

//前序线索二叉树  先序遍历
void pre_display(Treenode* root)
{if(root==nullptr) return;//root就是起始节点while(root){visit(root);root=pre_next(root);}
}

相信在前序的讲解下,后面我就不再过多解释

 

3.2中序线索二叉树

3.2.1中序线索的创建

//中序线索二叉树  线索的创建
void midclue_create(Treenode *root) 
{static Treenode *pre = nullptr;    //static 每个递归共享同一个pre 且只初始化一次if (root == nullptr)return;midclue_create(root->left);if (root->left == nullptr)   //处理左空节点线索{   root->ltag = 1;root->left = pre;}if (pre != nullptr && pre->right == nullptr)  //处理非空前节点右空线索{  pre->right = root;pre->rtag = 1;}pre = root;midclue_create(root->right);
}

3.2.2中序后继节点的查找

//中序线索二叉树 后驱节点的获取
Treenode* mid_next(Treenode* root)
{	           //有后驱节点  直接returnif(root->rtag==1){return root->right;}//否则返回该root节点右子树的最左子节点else                                   {root=root->right;while(root&&root->ltag==0)      //1表示前驱节点,0表示有左孩子,{root=root->left;}return root;              //return 右子树的最左子节点}
}

3.2.3中序前驱节点的查找

如果root节点是其父节点的左孩子或者没有父亲  前驱为 root节点左子树的最右子节点
否则 前驱为其父节点

Treenode* mid_pre(Treenode* root)
{if(root==nullptr) return nullptr;if(root->parent==nullptr||root->parent->left==root){auto node=root->left;while(node!=nullptr&&node->rtag==0) node=node->right;return node;}else return root->parent;
}

3.2.4使用后继节点实现中序遍历

//中序线索二叉树的 中序遍历
void mid_display(Treenode* root)
{if(root==nullptr) return;while(root->ltag==0)            //遍历到二叉树的最左子节点  也就是中序遍历的开始节点{root=root->left;}while(root)           //我们通过后驱节点访问下一个节点{visit(root);root=mid_next(root);}
}

3.3后序线索二叉树

3.3.1后序线索的创建


//后序线程二叉树  线索的创建
void lastclue_create(Treenode *root) {static Treenode *pre=nullptr;if (root == nullptr) return;lastclue_create(root->left);lastclue_create(root->right);if(root->left==nullptr){root->ltag=1;root->left=pre;}if(pre!=nullptr&&pre->right!=nullptr){pre->rtag=1;pre->right=root;}pre=root;
}

3.3.2后序后继节点的查找

//后序线索二叉树  后继节点的查找
Treenode* last_next(Treenode* root)
{if(root==nullptr) return nullptr;//有后继节点标记if(root->rtag==1) return root->right;if(root->parent==nullptr) return root->right;else if(root->parent->left==root){auto node=root->parent;while(node->rtag==0&&node->right!=nullptr){node=node->right;}return node;}else return root->parent;
}

3.3.3后序前驱节点的查找

//后序线索二叉树  前驱节点的查找
Treenode* last_pre(Treenode* root)
{if(root==nullptr) return nullptr;//有前驱节点标记if(root->ltag==1) return root->left;//无前驱节点 //三种情况//1.有右孩子//2.只有左孩子//3.无左右孩子 if(root->rtag==0) return root->right;else if(root->ltag==0) return root->left;else return nullptr;
}

 

3.3.4使用后继节点实现后序遍历

//后序线索二叉树  后序遍历
void last_display(Treenode* root)
{if(root==nullptr) return;//起始节点为左子树的最左叶子节点while (root->ltag == 0 || root->rtag == 0)   //判断是否是叶子节点{if (root->ltag == 0) root = root->left;  // 优先进入左子树  else root = root->right;                 // 否则进入右子树}while(root){visit(root);root=root->last_next(root);}
}

3.4层次线索二叉树
看到这了自己动手实现一下吧
 


 

  

 


http://www.ppmy.cn/server/145652.html

相关文章

代码随想录打卡DAY20

算法记录第20天 [二叉树] 1.LeetCode 501. 二叉搜索树中的众数 题目描述: 给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。如果树…

深入解析经典排序算法:原理、实现与优化

文章目录 6. 堆排序(Heap Sort)原理Java 实现 7. 希尔排序(Shell Sort)原理Java 实现 8. 计数排序(Counting Sort)原理Java 实现 9. 基数排序(Radix Sort)原理Java 实现 深入浅出&am…

(STM32)ADC驱动配置

1.ADC驱动(STM32) ADC模块中,**常规模式(Regular Mode)和注入模式(Injected Mode)**是两种不同的ADC工作模式 常规模式:用于普通的ADC转换,是默认的ADC工作模式。 注入…

【ROS2】ROS2 与 ROS1 编码方式对比(C++实现)

目录 一、初始化和关闭节点二、发布者和订阅者三、服务和客户端四、参数管理五、日志记录六、生命周期管理 ROS1 主要使用roscpp和rospy作为客户端库,分别用于C和Python语言。 ROS2 引入了新的客户端库rclcpp(C)和rclpy(Python&a…

iOS开发之修改已有项目的项目名和类名前缀

一、修改项目名称 1、Xcode打开项目修改项目名称 直接选中项目,点击enter,直接修改项目名称 把buydodo改成xiedodo,点击enter Rename完了点继续,只有框框内的部分变了 2、退出Xcode关闭项目,修改剩下的项目名称 找…

论文笔记(五十七)Diffusion Model Predictive Control

Diffusion Model Predictive Control 文章概括摘要1. Introduction2. Related work3. 方法3.1 模型预测控制3.2. 模型学习3.3. 规划(Planning)3.4. 适应 4. 实验(Experiments)4.1. 对于固定奖励,D-MPC 可与其他离线 RL…

element-plus弹窗二次封装踩坑

1 基于element-plus的二次封装弹窗很常见。代码如下&#xff1a; 父组件&#xff1a; import Dialog from ./components/Dialogs/testDailog.vueconst showref(false) const openDialog()>{show.valuetrue}<button click"openDialog" >打开dialoag</bu…

git merge 排除文件

方法一&#xff1a; 在Git中&#xff0c;如果你想在合并时排除特定文件&#xff0c;你可以使用.gitattributes文件来指定合并策略。你可以设置一个自定义合并策略来忽略特定文件的合并。 首先&#xff0c;在仓库的根目录下创建或编辑.gitattributes文件&#xff0c;并添加以…