线索化二叉树和哈夫曼树基础知识介绍与代码分析
一、基础知识介绍
二、代码分析：
线索二叉树（采用中序遍历）
#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; }
结果为：
