[C++知识库]中序线索二叉树的创建和遍历（C++）

内容是王道上的，这里是完全可以实现的代码，还需要加深理解。

#include<iostream>
using namespace std;

//树的结构体 
struct tree{
	int data;
	struct tree* lchild;
	struct tree* rchild;
	int ltag;
	int rtag;
};

//插入树节点（模板记忆） 
tree* insert(tree* &T){
	int a;
	cout<<"请输入结点："<<endl;
	cin>>a;
	if(a==00){
		return 0;
	}
	else{
		T=new tree;
		T->data=a;
		T->lchild=insert(T->lchild);
		T->rchild=insert(T->rchild);
	}
	return T;   //这一步不能少，否则只能输出第一个 
} 

//中序遍历对二叉树线索化
void InThread(tree* &P,tree* &Pre){    //Pre相当于全局变量 
	if(P!=NULL){
		InThread(P->lchild,Pre);
		if(P->lchild==NULL){         //左孩子为空就可以线索化，指向pre
			P->lchild=Pre;
			P->ltag=1; 
		}
		if(Pre!=NULL&&Pre->rchild==NULL){   //当前访问结点的pre存在，且pre没有右孩子，那当前结点就是pre的后继 
			Pre->rchild=P;
			Pre->rtag=1;
		}
		Pre=P;                          //后移 
		InThread(P->rchild,Pre); 
	} 
} 

//主过程 （完成收尾工作） 
void creat(tree* &T){
	tree* Pre=NULL;
	if(T!=NULL){
		InThread(T,Pre);
		Pre->rchild=NULL;
		Pre->rtag=1;
	}
}

//返回中序遍历下第一个结点的地址 
tree* first(tree* &T){
	while(T->ltag==0){    //有左孩子，就一直向左寻找 
		T=T->lchild;
	}
	return T;
}

//寻找后继 （相当于++操作） 
tree* next(tree* &T){ 
	if(T->rtag==0){
		return first(T->rchild);
	}
	else{
		return T->rchild;
	}
}

//遍历 
void bianli(tree* &T){
	for(tree *P=first(T);P!=NULL;P=next(P)){
		cout<<P->data<<endl;
	}
}

int main(){
	tree* T;
	insert(T);
	creat(T);
	bianli(T);
	return 0;
}