线索二叉树

#include<iostream>
#include<cstdlib>

using namespace std;

typedef int ElemType;

struct Node {
	ElemType data;
	Node *left, *right;
	bool rTag, lTag;
};

void initThread(Node* &bt) {
	bt=NULL;
}

void insertThread(Node* &bt,const ElemType& item) {
	Node *child=bt,*parent=NULL;
	while(child!=NULL) {
		parent=child;
		if(item<child->data)
		if(child->lTag==false)
		child=child->left;
		else
		child=NULL;
		else if(item>child->data)
		if(child->rTag==false)
		child=child->right;
		else
		child=NULL;
		else
		return;
	}
	Node* temp=new Node;
	temp->data=item;
	temp->lTag=temp->rTag=true;

	if(parent==NULL) {
		temp->left=temp->right=NULL;
		bt=temp;
	}
	else if(item>parent->data) {
		temp->right=parent->right;
		parent->rTag=false;
		parent->right=temp;
		temp->left=parent;
	}
	else {
		temp->left=parent->left;
		parent->lTag=false;
		parent->left=temp;
		temp->right=parent;
	}

}

void printTree(Node* bt) {
	if (bt != NULL) {
		cout << bt->data << ' ';
		if (bt->lTag == false || bt->rTag == false) {
			cout << '(';
			if (bt->lTag == false)
				printTree(bt->left);
			if (bt->rTag == false) {
				cout << ',';
				printTree(bt->right);
			}
			cout << ')';
		}
	}
}

Node* inorderNext(Node* bt) {
	if (bt->rTag == true)
		return bt->right;
	else {
		bt = bt->right;
		while (bt->lTag == false)
			bt = bt->left;
		return bt;
	}
}

void inorderThread(Node* bt) {
	if (bt != NULL) {
		while (bt->lTag == false)
			bt = bt->left;
		do {
			cout << bt->data << ' ';
			bt = inorderNext(bt);
		} while (bt != NULL);
	}
}

void display(Node* bt) {
	cout << "Tree: ";
	printTree(bt);
	cout << endl;
	cout << "inorder thread: ";
	inorderThread(bt);
	cout << endl;
}

bool deleteThread(Node* &bt,const ElemType& item) {
	if(bt==NULL)
	return false;
	else {
		if(item>bt->data)
		if(bt->rTag==false)
		return deleteThread(bt->right,item);
		else
		return false;
		else if(item<bt->data)
		if(bt->lTag==false)
		return deleteThread(bt->left,item);
		else
		return false;
		else {
			if(bt->lTag==true&&bt->rTag==true) {
				Node* temp=bt;
				if((bt->left!=NULL)&&(bt->left->right==temp)) {
					bt->left->rTag=true;
					bt->left->right=bt->right;
				}
				else if((bt->right!=NULL)&&(bt->right->left=temp)) {
					bt->right->lTag=true;
					bt->right->left=bt->left;
				}
				else {
					bt=NULL;
				}
				delete temp;
				return true;
			}
			else if(bt->lTag==true&&bt->rTag==false) {
				Node* temp=bt->right;
				while(temp->lTag!=true) {
					temp=temp->left;
				}
				bt->data=temp->data;
				return deleteThread(bt->right,temp->data);
			}
			else if(bt->lTag=false&&bt->rTag==true) {
				Node *temp=bt->left;
				while(temp->rTag!=true) {
					temp=temp->right;
				}
				bt->data=temp->data;
				return deleteThread(bt->left,temp->data);
			}
			else {
				if(bt->left->rTag==true) {
					bt->data=bt->left->data;
					return deleteThread(bt->left,bt->left->data);
				}
				else {
					Node *parent=bt,*child=bt->left;
					while(child->rTag!=true) {
						parent=child;
						child=child->right;
					}
					bt->data=child->data;
					return deleteThread(parent->right,child->data);
				}
			}
		}

	}
}

void clearThread(Node* &bt) {
	if(bt!=NULL) {
		if(bt->lTag==false)
		clearThread(bt->left);
		if(bt->rTag==false)
		clearThread(bt->right);

		delete bt;
		bt=NULL;
	}
}
int main() {
	ElemType array[] = { 36, 12, 75, 83, 54, 67, 60, 40, 92, 72 };
	Node* bt;
	initThread(bt);
	for (int i = 0; i < 10; i++)
		insertThread(bt, array[i]);
	display(bt);

	for (int i = 0; i < 10; i++) {
		cout << "***************** " << array[i] << " ***************" << endl;
		deleteThread(bt, array[i]);
		display(bt);
	}

	clearThread(bt);
}