数据结构——线索化二叉树和哈夫曼树[通俗易懂]

数据结构——线索化二叉树和哈夫曼树[通俗易懂]线索化二叉树和哈夫曼树基础知识介绍与代码分析一、基础知识介绍二、代码分析:线索二叉树(采用中序遍历)#include “pch.h”#include <iostream>using namespace std;//定义线索二叉树typedef struct Tree{ int data, LTag, RTag; //定义数据域与标记域 Tre…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

线索化二叉树和哈夫曼树基础知识介绍与代码分析

一、基础知识介绍

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、代码分析:

线索二叉树(采用中序遍历)

#include "pch.h"
#include <iostream>
using namespace std;

//定义线索二叉树
typedef struct Tree
{ 
   
	int data, LTag, RTag;	//定义数据域与标记域
	Tree *lchild, *rchild;

}Tree,*Trees;

Trees pre = NULL;	//设置前驱线索

//初始化二叉树
void InitBitTree(Trees*boot)
{ 
   
	*boot = (Trees)malloc(sizeof(Tree));
	(*boot)->lchild = (*boot)->rchild = NULL;
	(*boot)->LTag = (*boot)->RTag = 0;
}
//创建二叉树
void CreateBtTree(Trees &boot)
{ 
   
	int num;
	cout << "请输入数据:";
	cin >> num;
	if (num==0)
	{ 
   
		boot = NULL;
	}
	else
	{ 
   
		boot =(Trees) malloc(sizeof(Tree));
		boot->data = num;
		boot->lchild = boot->rchild = 0;
		boot->LTag = boot->RTag = 0;
		CreateBtTree(boot->lchild);
		CreateBtTree(boot->rchild);
	}
}
//添加线索
void InssertLineTree(Trees &boot)
{ 
   
	if (boot!=NULL)
	{ 
   
		InssertLineTree(boot->lchild);//线索化左子树
		if (boot->lchild==NULL)
		{ 
   
			boot->LTag = 1;
			boot->lchild = pre;//设置前驱线索
		}
		if (pre!=NULL&&pre->rchild==NULL)
		{ 
   
			pre->rchild = boot ;
			pre->RTag = 1;
		}
		//当前访问节点为下一个节点的前驱/
		pre = boot;
		//线索化右子树
		InssertLineTree(boot->rchild);
	}
}
//创建头结点
Trees InOrderThread(Trees &rt)
{ 
   
	Trees throot;
	if (!(throot = (Trees)malloc(sizeof(Tree))))
	{ 
   
		cout << "头结点创建失败!" << endl;
		exit(0);
	}
	throot->LTag = 0;//左标记为0 指向左子树
	throot->RTag = 1;//右标记为1 指向遍历的前驱
	throot->rchild = throot;//右子树指向头结点本身
	if (!throot)
	{ 
   
		//二叉树如果为空,左指针指向头结点本身
		throot->lchild = throot;
	}
	else
	{ 
   
		throot->lchild = rt;
		pre = throot;
		//插入线索
		InssertLineTree(rt);
		pre->rchild = throot;
		pre->RTag = 1;
		throot->rchild = pre;
	}

	return throot;
}

//中序遍历查找前驱
void InPre(Trees boot)
{ 
   
	Trees q = NULL;
	if (boot->LTag==1)
	{ 
   
		pre = boot->lchild;
	}
	else
	{ 
   
		for (q=boot->lchild; q->RTag==0;q=q->rchild )
		{ 
   
			pre=q;
		}
	}
	if (pre)
	{ 
   
		cout << "用中序遍历找到的前驱为:" << pre->data << endl;
	}
	else
	{ 
   
		cout << "用中序遍历无前驱:" << endl;
	}
}

//中序遍历后序节点
void InNext(Trees boot)
{ 
   
	Trees q = NULL;
	if (boot->RTag == 1)
	{ 
   
		pre = boot->rchild;
	}
	else
	{ 
   
		for (q = boot->rchild; q->LTag == 0; q = q->lchild)
		{ 
   
			pre = q;
		}
	}
	if (pre)
	{ 
   
		cout << "用中序遍历找到的后继为:" << pre->data << endl;
	}
	else
	{ 
   
		cout << "用中序遍历无后继:" << endl;
	}
}

//中序遍历查找线索二叉树第一个节点
Trees InFirst(Trees boot)
{ 
   
	Trees p = boot;
	if (!p)
	{ 
   
		return 0;
	}
	while (p->LTag==0)
	{ 
   
		p = p->lchild;
	}
	return p;
	//中序遍历左 根 右 二叉树左左端节
	//二叉树的最左端的节点

}

//中序遍历线索二叉树
void TinOrder(Trees &throot)
{ 
   
	Trees p;
	p = throot->lchild;
	while (p!=throot)
	{ 
   
		while (p->LTag==0)//有左子树
		{ 
   
			p = p->lchild;
		}
		cout<<p->data<<endl;
		while (p->RTag==1&&p->rchild!=throot)
		{ 
   
			p = p->rchild;
			cout << p->data << endl;
		}
		p = p->rchild;
	}
	cout << endl;
}
int main()
{ 
   
	Trees boot = NULL;
	cout << "创建线索二叉树,如果输入0结束:" << endl;
	CreateBtTree(boot);
	Trees throot;	//头结点

	throot=InOrderThread(boot);
	//进行遍历
	TinOrder(throot);

	InPre(boot);
	InNext(boot);

	Trees bt=InFirst(boot);
	cout << "中序遍历线索二叉树的第一个节点为:" << bt->data << endl;

	return 0;
}

结果为:

居中

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170981.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号