线索二叉树
1.什么是线索二叉树？
线索二叉树是一种特殊的二叉树，它在传统二叉树的基础上，利用节点中原本为空的指针域存储指向节点前驱或后继的信息，从而在遍历时不需要递归或栈辅助，能够高效地找到前驱或后继节点。
前序遍历：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先序后继节点的查找
后继节点和孩子有关
这里我们需要谈论的只有非叶子节点的情况，因为叶子节点一定会有前驱和后继节点直接返回即可
前序遍历：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节点的前驱为父节点左子树的最右子节点
如若想实现前驱代码如下
//前序线索二叉树 前驱节点的查找
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层次线索二叉树
看到这了自己动手实现一下吧