目录
1. 二叉线索树的节点结构体
2.按先序遍历的顺序创建二叉树
3. 二叉树的线索化（使用中序遍历线索化）
4. 创建中序线索二叉树
5. 中序遍历打印线索二叉树
6. 完整代码
7. 运行结果及截图
1. 二叉线索树的节点结构体
typedef struct ClueBiTreeNode {//定义二叉线索树的节点结构体
char data;//数据域
ClueBiTreeNode* LeftChild;//左孩子
int LTag;
ClueBiTreeNode* RightChild;//右孩子
int RTag;
// LTag=0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索
}*BiTreeClue;// BiTreeClue --》二叉线索树的结构体指针
2.按先序遍历的顺序创建二叉树
void CreateBiTree(BiTreeClue& T) {
char c;
cin >> c;//输入字符
if (c == '*') {
T = NULL;
}//孩子为空时，其值为‘*’
else {
T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点
T->data = c;//为新节点填充数据
T->LTag = 0;//新节点初始化，存在左孩子
T->RTag = 0;//新节点初始化，存在右孩子
CreateBiTree(T->LeftChild);//递归处理左孩子
CreateBiTree(T->RightChild);//递归处理右孩子
}
}
3. 二叉树的线索化（使用中序遍历线索化）
void ClueBiTree(BiTreeClue& T) {
if (!T) return;//T是空树
if (T) {//T不是空树
//中序遍历：左、根、右
ClueBiTree(T->LeftChild);//先处理左子树
if (!(T->LeftChild)) {//左子树为空时
T->LTag = 1;//表明该节点无左子树，此时指向前驱节点
T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点
}
if (!(pre->RightChild)) {//右子树为空时
pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点
pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点
}
pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针
ClueBiTree(T->RightChild);//处理右子树
}
}
4. 创建中序线索二叉树
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
5. 中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;//一直向右移动
cout << Q->data << " ";//打印出该点的值
}
Q = Q->RightChild;//指回了头指针
}
}
6. 完整代码
#include
using namespace std;
typedef struct ClueBiTreeNode {//定义二叉线索树的节点结构体
char data;//数据域
ClueBiTreeNode* LeftChild;//左孩子
int LTag;
ClueBiTreeNode* RightChild;//右孩子
int RTag;
// LTag=0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索
}*BiTreeClue;// BiTreeClue --》二叉线索树的结构体指针
ClueBiTreeNode* pre;//定义了一个全局叉线索树的结构体指针变量pre
//按先序遍历的顺序创建二叉树
void CreateBiTree(BiTreeClue& T) {
char c;
cin >> c;//输入字符
if (c == '*') {
T = NULL;
}//孩子为空时，其值为‘*’
else {
T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点
T->data = c;//为新节点填充数据
T->LTag = 0;//新节点初始化，存在左孩子
T->RTag = 0;//新节点初始化，存在右孩子
CreateBiTree(T->LeftChild);//递归处理左孩子
CreateBiTree(T->RightChild);//递归处理右孩子
}
}
//构造二叉树的线索，使用的是中序遍历线索化的方式。
void ClueBiTree(BiTreeClue& T) {
if (!T) return;//T是空树
if (T) {//T不是空树
//中序遍历：左、根、右
ClueBiTree(T->LeftChild);//先处理左子树
if (!(T->LeftChild)) {//左子树为空时
T->LTag = 1;//表明该节点无左子树，此时指向前驱节点
T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点
}
if (!(pre->RightChild)) {//右子树为空时
pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点
pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点
}
pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针
ClueBiTree(T->RightChild);//处理右子树
}
}
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
//中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;
cout << Q->data << " ";
}
Q = Q->RightChild;//指回了头指针
}
}
int main() {
BiTreeClue T;
BiTreeClue Head;
cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABD**E**CF**G**）" << endl;
CreateBiTree(T);
CreateClueBiTree(Head, T);
cout << endl;
cout << "中序遍历的中序线索二叉树为：";
InorderPrint(Head);
cout << endl;
system("pause");
}
7. 运行结果及截图
void CreateBiTree(BiTreeClue& T) {
char c;
cin >> c;//输入字符
if (c == '*') {
T = NULL;
}//孩子为空时，其值为‘*’
else {
T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点
T->data = c;//为新节点填充数据
T->LTag = 0;//新节点初始化，存在左孩子
T->RTag = 0;//新节点初始化，存在右孩子
CreateBiTree(T->LeftChild);//递归处理左孩子
CreateBiTree(T->RightChild);//递归处理右孩子
}
}
3. 二叉树的线索化（使用中序遍历线索化）
void ClueBiTree(BiTreeClue& T) {
if (!T) return;//T是空树
if (T) {//T不是空树
//中序遍历：左、根、右
ClueBiTree(T->LeftChild);//先处理左子树
if (!(T->LeftChild)) {//左子树为空时
T->LTag = 1;//表明该节点无左子树，此时指向前驱节点
T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点
}
if (!(pre->RightChild)) {//右子树为空时
pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点
pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点
}
pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针
ClueBiTree(T->RightChild);//处理右子树
}
}
4. 创建中序线索二叉树
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
5. 中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;//一直向右移动
cout << Q->data << " ";//打印出该点的值
}
Q = Q->RightChild;//指回了头指针
}
}
6. 完整代码
#include
using namespace std;
typedef struct ClueBiTreeNode {//定义二叉线索树的节点结构体
char data;//数据域
ClueBiTreeNode* LeftChild;//左孩子
int LTag;
ClueBiTreeNode* RightChild;//右孩子
int RTag;
// LTag=0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索
}*BiTreeClue;// BiTreeClue --》二叉线索树的结构体指针
ClueBiTreeNode* pre;//定义了一个全局叉线索树的结构体指针变量pre
//按先序遍历的顺序创建二叉树
void CreateBiTree(BiTreeClue& T) {
char c;
cin >> c;//输入字符
if (c == '*') {
T = NULL;
}//孩子为空时，其值为‘*’
else {
T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点
T->data = c;//为新节点填充数据
T->LTag = 0;//新节点初始化，存在左孩子
T->RTag = 0;//新节点初始化，存在右孩子
CreateBiTree(T->LeftChild);//递归处理左孩子
CreateBiTree(T->RightChild);//递归处理右孩子
}
}
//构造二叉树的线索，使用的是中序遍历线索化的方式。
void ClueBiTree(BiTreeClue& T) {
if (!T) return;//T是空树
if (T) {//T不是空树
//中序遍历：左、根、右
ClueBiTree(T->LeftChild);//先处理左子树
if (!(T->LeftChild)) {//左子树为空时
T->LTag = 1;//表明该节点无左子树，此时指向前驱节点
T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点
}
if (!(pre->RightChild)) {//右子树为空时
pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点
pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点
}
pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针
ClueBiTree(T->RightChild);//处理右子树
}
}
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
//中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;
cout << Q->data << " ";
}
Q = Q->RightChild;//指回了头指针
}
}
int main() {
BiTreeClue T;
BiTreeClue Head;
cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABD**E**CF**G**）" << endl;
CreateBiTree(T);
CreateClueBiTree(Head, T);
cout << endl;
cout << "中序遍历的中序线索二叉树为：";
InorderPrint(Head);
cout << endl;
system("pause");
}
7. 运行结果及截图
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
5. 中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;//一直向右移动
cout << Q->data << " ";//打印出该点的值
}
Q = Q->RightChild;//指回了头指针
}
}
6. 完整代码
#include
using namespace std;
typedef struct ClueBiTreeNode {//定义二叉线索树的节点结构体
char data;//数据域
ClueBiTreeNode* LeftChild;//左孩子
int LTag;
ClueBiTreeNode* RightChild;//右孩子
int RTag;
// LTag=0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索
}*BiTreeClue;// BiTreeClue --》二叉线索树的结构体指针
ClueBiTreeNode* pre;//定义了一个全局叉线索树的结构体指针变量pre
//按先序遍历的顺序创建二叉树
void CreateBiTree(BiTreeClue& T) {
char c;
cin >> c;//输入字符
if (c == '*') {
T = NULL;
}//孩子为空时，其值为‘*’
else {
T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点
T->data = c;//为新节点填充数据
T->LTag = 0;//新节点初始化，存在左孩子
T->RTag = 0;//新节点初始化，存在右孩子
CreateBiTree(T->LeftChild);//递归处理左孩子
CreateBiTree(T->RightChild);//递归处理右孩子
}
}
//构造二叉树的线索，使用的是中序遍历线索化的方式。
void ClueBiTree(BiTreeClue& T) {
if (!T) return;//T是空树
if (T) {//T不是空树
//中序遍历：左、根、右
ClueBiTree(T->LeftChild);//先处理左子树
if (!(T->LeftChild)) {//左子树为空时
T->LTag = 1;//表明该节点无左子树，此时指向前驱节点
T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点
}
if (!(pre->RightChild)) {//右子树为空时
pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点
pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点
}
pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针
ClueBiTree(T->RightChild);//处理右子树
}
}
void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) {
head = new(ClueBiTreeNode);//头节点
head->data = NULL;//头节点无数据
head->LTag = 0;//头节点无前驱
head->RTag = 1;//头节点有后继
//如果传进来的树是一个空树，那么head节点的左子节点指向自己
if (!T) {
head->LeftChild = head;
}
else {//不是空树
head->LeftChild = T;//头指针指向根节点
pre = head;//根节点的前驱节点是头节点
ClueBiTree(T);//将该树给线索化
//线索化后此时pre指向最右的节点
pre->RTag = 1;//此时最右的节点无右子树
pre->RightChild = head;//最右的节点的后继指向头指针
head->RightChild = pre;//头指针的右子树指针指向最后一个节点
}
}
//中序遍历打印线索二叉树
void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树
ClueBiTreeNode* Q;
Q = T->LeftChild;//Q是根节点的左孩子
//如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束
while (Q != T) {
while (Q->LTag == 0) {//该节点有左子树
Q = Q->LeftChild;//一直向左找到最左的节点
}
cout << Q->data << " ";//输出最左的节点数据
while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点
Q = Q->RightChild;
cout << Q->data << " ";
}
Q = Q->RightChild;//指回了头指针
}
}
int main() {
BiTreeClue T;
BiTreeClue Head;
cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABD**E**CF**G**）" << endl;
CreateBiTree(T);
CreateClueBiTree(Head, T);
cout << endl;
cout << "中序遍历的中序线索二叉树为：";
InorderPrint(Head);
cout << endl;
system("pause");
}
7. 运行结果及截图
#includeusing namespace std; typedef struct ClueBiTreeNode {//定义二叉线索树的节点结构体 char data;//数据域 ClueBiTreeNode* LeftChild;//左孩子 int LTag; ClueBiTreeNode* RightChild;//右孩子 int RTag; // LTag=0表示当前节点左指针域保存的是左孩子地址 1保存是当前节点的前驱节点线索 }*BiTreeClue;// BiTreeClue --》二叉线索树的结构体指针 ClueBiTreeNode* pre;//定义了一个全局叉线索树的结构体指针变量pre //按先序遍历的顺序创建二叉树 void CreateBiTree(BiTreeClue& T) { char c; cin >> c;//输入字符 if (c == '*') { T = NULL; }//孩子为空时，其值为‘*’ else { T = new ClueBiTreeNode;//申请新节点，用来保存孩子节点 T->data = c;//为新节点填充数据 T->LTag = 0;//新节点初始化，存在左孩子 T->RTag = 0;//新节点初始化，存在右孩子 CreateBiTree(T->LeftChild);//递归处理左孩子 CreateBiTree(T->RightChild);//递归处理右孩子 } } //构造二叉树的线索，使用的是中序遍历线索化的方式。 void ClueBiTree(BiTreeClue& T) { if (!T) return;//T是空树 if (T) {//T不是空树 //中序遍历：左、根、右 ClueBiTree(T->LeftChild);//先处理左子树 if (!(T->LeftChild)) {//左子树为空时 T->LTag = 1;//表明该节点无左子树，此时指向前驱节点 T->LeftChild = pre;//表明该节点无左子树，此时指向前驱节点 } if (!(pre->RightChild)) {//右子树为空时 pre->RTag = 1; //表明该节点无右子树，此时指向前驱节点 pre->RightChild = T;//表明该节点无左子树，此时指向前驱节点 } pre = T;//pre指向当前的T，作为T将要指向的下一个节点的前驱节点提示指针 ClueBiTree(T->RightChild);//处理右子树 } } void CreateClueBiTree(BiTreeClue& head, BiTreeClue& T) { head = new(ClueBiTreeNode);//头节点 head->data = NULL;//头节点无数据 head->LTag = 0;//头节点无前驱 head->RTag = 1;//头节点有后继 //如果传进来的树是一个空树，那么head节点的左子节点指向自己 if (!T) { head->LeftChild = head; } else {//不是空树 head->LeftChild = T;//头指针指向根节点 pre = head;//根节点的前驱节点是头节点 ClueBiTree(T);//将该树给线索化 //线索化后此时pre指向最右的节点 pre->RTag = 1;//此时最右的节点无右子树 pre->RightChild = head;//最右的节点的后继指向头指针 head->RightChild = pre;//头指针的右子树指针指向最后一个节点 } } //中序遍历打印线索二叉树 void InorderPrint(const BiTreeClue T) {//遍历不改变树，加const保护该树 ClueBiTreeNode* Q; Q = T->LeftChild;//Q是根节点的左孩子 //如果指向左孩子的指针，和指向根节点的指针相同时，表示这个树要么是空树或者遍历结束 while (Q != T) { while (Q->LTag == 0) {//该节点有左子树 Q = Q->LeftChild;//一直向左找到最左的节点 } cout << Q->data << " ";//输出最左的节点数据 while (Q->RTag == 1 && Q->RightChild != T) {//该节点无右子树并且不是遍历结束时树中最右的节点 Q = Q->RightChild; cout << Q->data << " "; } Q = Q->RightChild;//指回了头指针 } } int main() { BiTreeClue T; BiTreeClue Head; cout << "请按先序遍历的顺序创建二叉树，若其节点的左孩子或右孩子不存在则使用*代替！如：（ABD**E**CF**G**）" << endl; CreateBiTree(T); CreateClueBiTree(Head, T); cout << endl; cout << "中序遍历的中序线索二叉树为："; InorderPrint(Head); cout << endl; system("pause"); }
7. 运行结果及截图
下图为测试用例： (ABD**E**CF**G**)
前序遍历：A B D E C F G
中序遍历：D B E A F C G
后序遍历：D E B F G C A
