C++ 用土办法找到二叉树中序遍历序列前驱和后继

╰半橙微兮° 2022-12-23 13:28 23阅读 0赞

> # **问题思考：如果不用三叉树，而用指针怎么找到中序遍历序列的前驱和后继呢？** #
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

> **思路：从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问结点，指针pre记录上一个被访问的结点。**
> 
> **①如何找到指定结点p在 q 中序遍历序列中的前驱？**
> 
> **②如何找到p的中序后继？**

①如何找到指定结点 p

中序遍历序列中的前驱？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

> **（1）寻找中序前驱**

//中序遍历寻找前驱 
    void BiTree::BInorder(BiNode *bt){
    	if(bt!=nullptr){
    		BInorder(bt->lchild);//递归遍历左子树
    		Bvisit(bt);//访问根结点
    		BInorder(bt->rchild);//递归遍历右子树 
    	}
    } 
    //访问，可以得到中序前驱 
    void BiTree::Bvisit(BiNode *q){
    	if( q->data == p->data)//当前访问结点刚好是结点p 
    		final1= pre;//找到p的前驱
    	else
    		pre = q;//pre指向当前访问的结点 
    }

> **（2）寻找中序后继**

//中序遍历寻找后继
    void BiTree::AInorder(BiNode *bt){
    	if(bt!=nullptr){
    		AInorder(bt->lchild);//递归遍历左子树
    		Avisit(bt);//访问根结点
    		AInorder(bt->rchild);//递归遍历右子树 
    	}
    }
    //访问，可以得到中序后继
    void BiTree::Avisit(BiNode *q){
    	if(flag == 1 && pre!=nullptr && pre->data == p->data){//当前访问结点刚好是结点p 
    		final2= q;//找到p的后继
    		flag = 0;
    	}
    	else
    		pre = q;//pre指向当前访问的结点 
    }

> **C++完整代码：**

//用土办法找到中序前驱
    #include<iostream>
    using namespace std;
    typedef char DataType;
    struct BiNode
    {
    	DataType data;
    	BiNode *lchild,*rchild;
    };
    BiNode *p=new BiNode; //记录目标节点
    BiNode *pre = nullptr;//指向当前访问结点的前驱
    BiNode *final1= nullptr;//用于记录最终结果 
    BiNode *final2= nullptr;//用于记录最终结果 
    class BiTree
    {
    	public:
    		BiTree(){root=Create(root);}//构造函数，建立一颗二叉树
    		~BiTree(){Release(root);}//析构函数，释放各个节点的存储空间
    		void Inorder(){Inorder(root);}//中序遍历二叉树
    		void BInorder(){BInorder(root);}//中序遍历寻找前驱二叉树
    		void AInorder(){AInorder(root);}//中序遍历寻找后继二叉树
    		void Bvisit(BiNode *q);//访问，可以得到中序前驱 
    		void Avisit(BiNode *q);//访问，可以得到中序后继
    	private:
    		BiNode *root;//指向根节点的头指针
    		BiNode *Create(BiNode *bt);//构造函数调用
    		int flag=1;
    		void Release(BiNode *bt);
    		void Inorder(BiNode *bt);//中序遍历函数调用
    		void BInorder(BiNode *bt);//中序遍历寻找前驱函数调用
    		void AInorder(BiNode *bt); //中序遍历寻找后继函数调用
    };
    //创建二叉树 
    BiNode *BiTree::Create(BiNode *bt)
    {
    	static int i=0;
    	char ch;
    	string str="AB#D##C##";
    	ch=str[i++];
    	if(ch=='#')bt=nullptr;//建立一棵空树 
    	else {
    		bt=new BiNode;bt->data=ch;//生成一个结点，数据域为ch
    		bt->lchild=Create(bt->lchild);//递归建立左子树
    		bt->rchild=Create(bt->rchild);//递归建立右子树
    	}
    	return bt;
    }
    //销毁二叉树 
    void BiTree::Release(BiNode *bt)
    {
    	if(bt!=nullptr){
    		Release(bt->lchild);
    		Release(bt->rchild);
    		delete bt;
    	}
    }
    //中序遍历
    void BiTree::Inorder(BiNode *bt)
    {
    	if(bt==nullptr)return;//递归调用的结束条件
    	else{
    		Inorder(bt->lchild);//中序递归遍历bt的左子树
    		cout<<bt->data<<" ";//访问根节点的数据域
    		Inorder(bt->rchild);//中序递归遍历bt的右子树
    	}
    }
    //中序遍历寻找前驱 
    void BiTree::BInorder(BiNode *bt){
    	if(bt!=nullptr){
    		BInorder(bt->lchild);//递归遍历左子树
    		Bvisit(bt);//访问根结点
    		BInorder(bt->rchild);//递归遍历右子树 
    	}
    } 
    //中序遍历寻找后继
    void BiTree::AInorder(BiNode *bt){
    	if(bt!=nullptr){
    		AInorder(bt->lchild);//递归遍历左子树
    		Avisit(bt);//访问根结点
    		AInorder(bt->rchild);//递归遍历右子树 
    	}
    }
    //访问，可以得到中序前驱 
    void BiTree::Bvisit(BiNode *q){
    	if( q->data == p->data)//当前访问结点刚好是结点p 
    		final1= pre;//找到p的前驱
    	else
    		pre = q;//pre指向当前访问的结点 
    } 
    //访问，可以得到中序后继
    void BiTree::Avisit(BiNode *q){
    	if(flag == 1 && pre!=nullptr && pre->data == p->data){//当前访问结点刚好是结点p 
    		final2= q;//找到p的后继
    		flag = 0;
    	}
    	else
    		pre = q;//pre指向当前访问的结点 
    }
    int main(){
    	p->data ='D';//p指向目标结点
    	cout<<"创建一棵二叉树"<<endl;
    	BiTree T{};//创建一颗二叉树
    	cout<<"---中序遍历---"<<endl;//B D A C
    	T.Inorder();
    	cout<<endl;
    	T.BInorder();
    	if (final1 != nullptr)
            cout<<"结点"<<p->data<<"中序前驱"<<"  "<<final1->data<<endl;
        else
            cout<<"结点"<<p->data<<"无前驱"<<endl;
    	T.AInorder();
    	if (final2 != nullptr)
            cout<<"结点"<<p->data<<"中序后继"<<"  "<<final2->data<<endl;
        else
            cout<<"结点"<<p->data<<"无后继"<<endl;
    	return 0;
    }

> **实验结果图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5][]

> ### 我是热爱学习的呵呵哒~如果你觉得文章很棒，对你有帮助的话，可以点赞+收藏+加关注喔~ ###
> 
> **如果文章有不正确的地方，欢迎交流指正，我将虚心请教~o(>ω<)o**
> 
> **我会定期更新文章，继续为您提供优质文章~o(>ω<)o**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221120/5d4bd42c3d85498196f05e94402e05bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201125122613767.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201125122629938.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201125122654295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201125123907194.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201125123916564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70