1.结构
#include<stdio.h>
#include<stdlib.h>
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
int data;
struct BTnode *lchild,*rchild;
int ltag,rtag;
}*BTree,BTnode;1.1初始化tag
#include<stdio.h>
#include<stdlib.h>
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
int data;
struct BTnode *lchild,*rchild;
int ltag,rtag;
}*BTree,BTnode;2.基本操作
2.1 先序创建二叉树
int j=0; //创建二叉树的全局变量
//先序创建二叉树
int CreateBTree(BTree &T){
int str[]={1,2,3,NULL,4,NULL,NULL,NULL,5,6,NULL,7,NULL,NULL,8,NULL,NULL};
if(str[j]=='#') return false;
if(str[j]==NULL){
T=NULL;
j++;
}else{
T=(BTnode *)malloc(sizeof(BTnode));
T->data=str[j];
j++;
CreateBTree(T->lchild);
CreateBTree(T->rchild);
}
} 输出函数：
inline bool visit(int e){ //此处使用内敛函数，提高运行效率
printf("%d",e);
return true;
}2.2.先序线索化
//先序线索化.
void prehread(BTree &root){
if(root!=NULL){
if(root->lchild==NULL){
root->ltag=1;
root->lchild=pre;
}else{
root->ltag=0;
}
if(pre){
if(pre->rchild==NULL){
pre->rtag=1;
pre->rchild=root;
}else{
pre->rtag=0;
}
}
pre=root;
if(root->ltag==0){
prehread(root->lchild);
}
if(root->rtag==0){
prehread(root->rchild);
}
}
} 2.2.1.先序遍历
//寻找先序后继
BTree preNext(BTree T){
if(T->rtag==1){
return T->rchild;
}else{
if(T->ltag==0){
return T->lchild;
}else{
return T->rchild;
}
}
}
//先序线索二叉树的遍历
void prebianli(BTree T){
BTree p;
p=T;
while(p){
visit(p->data);
p=preNext(p);
}
} 
2.3.中序线索化
//中序线索化
BTree pre=NULL ; //中序线索化的全局变量
void Inthread(BTree &root){
if(root!=NULL){
Inthread(root->lchild);
if(root->lchild==NULL){
root->ltag=1;
root->lchild=pre;
}else{
root->ltag=0;
}
if(pre){
if(pre->rchild==NULL){
pre->rtag=1;
pre->rchild=root;
}else{
pre->rtag=0;
}
}
pre=root;
Inthread(root->rchild);
}
}2.3.1 中序遍历
//求中序首结点
BTree InFirst(BTree T){
BTree p=T;
if(p==NULL) return NULL;
while(p->ltag==0){
p=p->lchild;
}
return p;
}
//求中序后继
BTree InNext(BTree T) {
BTree next=NULL;
if(T->rtag==1){
next=T->rchild;
}else {
T = T->rchild;
while (T->ltag==0 ) {
T = T->lchild;
}
next=T;
}
return next;
}
//中序线索二叉树的遍历
void Inbianli(BTree T){
BTree p;
p=InFirst(T);
while(p){
visit(p->data);
p=InNext(p);
}
} 
2.4.后序线索化
//后续线索化
void Postthread(BTree &root){
BTree pre=NULL;
if(root){
Postthread(root->lchild);
Postthread(root->rchild);
if(root->lchild==NULL){
root->ltag=1;
root->lchild=pre;
}
if(pre&&pre->rchild==NULL){
pre->rtag=1;
pre->rchild=root;
}
pre=root;
}
}2.4.1 后序遍历
//求后序前驱
BTree postnext(BTree T){
if(T->ltag==0){
if(T->rtag==0){
return T->rchild;
}else{
return T->lchild;
}
}else {
return T->lchild;
}
}
//后序遍历
void postbianli(BTree T){
BTree p;
p=T;
while(p){
p=postnext(p);
visit(p->data);
}
} 
总结
tag最好另起函数进行初始化，并且在遍历中，牢抓前中后的遍历次序进行分析。
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注编程网的更多内容!
