【原】数据结构——线索化二叉树和哈夫曼树

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

一、基础知识介绍

二、代码分析：

线索二叉树（采用中序遍历）

#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;
}

结果为：