数据结构：使用C++实现二叉树的遍历和线索化

#include <iostream>
#include <time.h>
using namespace std;

typedef struct Node{
	int key;
	int ltag,rtag;//1:thread 0:edge
	Node *lchild, *rchild;
}Node;

Node *GetNewNode(int key)
{
	Node *p=new Node;
	p->key=key;
	p->ltag=p->rtag=0;
	p->lchild=p->rchild=NULL;
	return p;
}

Node *insert(Node *root,int key)
{
	if(root==NULL)	return GetNewNode(key);
	if(rand()%2)	root->lchild=insert(root->lchild,key);
	else			root->rchild=insert(root->rchild,key);
	return root;
}

void clear(Node *root)
{
	if(root==NULL)	return;
	if(root->ltag==0)	clear(root->lchild);
	if(root->rtag==0)	clear(root->rchild);
	delete root;
	return;
}

void PRE_order(Node *root)
{
	if(root==NULL)	return;
	cout<<root->key<<' ';
	if(root->ltag==0)	PRE_order(root->lchild);
	if(root->rtag==0)	PRE_order(root->rchild);
	return;
}

void IN_order(Node *root)
{
	if(root==NULL)	return;
	if(root->ltag==0)	IN_order(root->lchild);
	cout<<root->key<<' ';
	if(root->rtag==0)	IN_order(root->rchild);
}

void POST_order(Node *root)
{
	if(root==NULL)	return;
	if(root->ltag==0)	PRE_order(root->lchild);
	if(root->rtag==0)	PRE_order(root->rchild);
	cout<<root->key<<' ';
}

Node *pre_node=NULL,*inorder_root = NULL;
void __build_inorder_thread(Node *root) {
    if (root == NULL) return ;
    if (root->ltag == 0) __build_inorder_thread(root->lchild);
    if (inorder_root == NULL) inorder_root = root;
    if (root->lchild == NULL) {
        root->lchild = pre_node;
        root->ltag = 1;
    }
    if (pre_node && pre_node->rchild == NULL) {
        pre_node->rchild = root;
        pre_node->rtag = 1;
    }
    pre_node = root;
    if (root->rtag == 0) __build_inorder_thread(root->rchild);
    return ;
}

void build_inorder_thread(Node *root)
{
	__build_inorder_thread(root);
	pre_node->rchild=NULL;
	pre_node->rtag=1;
	return;
}

Node *GetNextNode(Node *root)
{
	if(root->rtag==1)	return root->rchild;
	root=root->rchild;
	while(root->ltag==0&&root->lchild)	root=root->lchild;
	return root;
}

int main()
{
	srand(time(0));
	Node *root=NULL;
	#define MAX_NODE 10
	for(int i=0;i<MAX_NODE;++i)
	{
		root=insert(root,rand()%100);
	}
	pre_node = inorder_root = NULL;
	build_inorder_thread(root);
	
	PRE_order(root);cout<<endl;
	IN_order(root);cout<<endl;
	POST_order(root);cout<<endl;
	//Like Linklist
	Node *node=inorder_root;
	while(node){
		cout<<node->key<<' ';
		node=GetNextNode(node);
	}
	cout<<endl;
	clear(root);
	return 0;
}