C言語_.データ構造_二叉樹(再帰)

#include 
#include 
#include 
#include 
using namespace std;
typedef int  Status;
typedef int BiTreeElemType;
typedef struct BiTreeNode{
	BiTreeElemType data;
	struct  BiTreeNode *lChild, *rChild;
}BiTreeNode,*BiTree;

Status CreateBiTree(BiTree &T) {
	BiTreeElemType n;
	cin >> n;
	if (n < 0) 	T = NULL;
	else {
		T = (BiTree)new BiTreeNode;
		if (T == NULL) {
			cout << "CreateBiTree      
";
			return 0;
		}
		T->data = n;
		CreateBiTree(T->lChild);
		CreateBiTree(T->rChild);

	}
	return 1;
}
//         
Status CreatBiTree(BiTreeElemType a[], int nFrom, int nTo, BiTree &T) {
	int nECount = nTo - nFrom + 1;	//        
	BiTree upper = NULL;//   
	BiTree current = NULL;//  
	BiTree below = NULL;//  
	int n = 1;
	while (n > 0) {
		while (n < nECount&&a[n + nFrom - 1]>0) {
			current = (BiTree)new BiTreeNode;
			if (current == NULL) {
				cout << "CreatBiTree          
";
				return 0;
			}
			current->data = a[n + nFrom - 1];
			current->rChild = current;
			current->lChild = upper;
			upper = current;
			n *= 2;
		}
		n /= 2;
		below = NULL;
		while (current != NULL && current->rChild != current) {
			upper = current->rChild;
			current->rChild = below;
			below = current;
			current = upper;
			n /= 2;
		}
		if (current == NULL) break;
		current->rChild = current->lChild;
		current->lChild = below;
		n = n * 2 + 1;
	}
	T = below;
	return 1;
}
Status VisitBiTreeElement(BiTreeElemType &e) {
	cout << e << ' ';
	return 1;
 }
//      
Status PreOrderBiTreeRec(BiTree &T) {
	if (T == NULL)	return 0;
	VisitBiTreeElement(T->data);
	PreOrderBiTreeRec(T->lChild);
	PreOrderBiTreeRec(T->rChild);
	return 1;
}
//      
Status InOrderBiTreeRec(BiTree &T) {
	if (T == NULL)	return 0;
	InOrderBiTreeRec(T->lChild);
	VisitBiTreeElement(T->data);
	InOrderBiTreeRec(T->rChild);
	return 1;
}
//      
Status PostOrderBiTreeRec(BiTree &T) {
	if (T == NULL)	return 0;
	PostOrderBiTreeRec(T->lChild);
	PostOrderBiTreeRec(T->rChild);
	VisitBiTreeElement(T->data);
	return 1;
}
//         
Status DestroyBiTreePostOrder(BiTree &T) {
	if (T == NULL) return 1;
	DestroyBiTreePostOrder(T->lChild);
	DestroyBiTreePostOrder(T->rChild);
	delete T;
	return 1;
}
//     
Status PreOrderBiTreeUnRec(BiTree T) {
	stack st;
	BiTree p;
	p = T;
	if (p == NULL) {
		printf("  ！
");
		return 0;
	}
	while (p||(!st.empty())){
		if(p)	{
			cout << ' ' << p->data;//       
			st.push(p);
			p = p->lChild;
		}
		else{
			p = st.top();
			st.pop();
			p = p->rChild;
		}
	}
	return 1;
}
//     
Status InOrderBiTreeUnRec(BiTree T) {
	stack st;
	BiTree p;
	p = T;
	if (p == NULL) {
		printf("  ！
");
		return 0;
	}
	while (p || (!st.empty())) {
		if (p) {
			st.push(p);
			p = p->lChild;
		}
		else {
			p = st.top();
			st.pop();
			cout << ' ' << p->data;//                    （         ）
			p = p->rChild;
		}
	}
	return 1;
}
//     
Status PostOrderBiTreeUnRec(BiTree T) {
	stack st;
	BiTree p;
	BiTree pre=NULL;//         
	p = T;
	if (p == NULL) {
		printf("  ！
");
		return 0;
	}
	while (p || (!st.empty())) {
		if (p) {
			st.push(p);
			p = p->lChild;
		}
		else {
			p = st.top();			
			if (p->rChild != NULL && pre != p->rChild){//          
			
				p = p->rChild;
				st.push(p);
				p = p->lChild;
			}
			else {
				p = st.top();
				st.pop();
				cout << ' ' << p->data;
				pre = p;//      
				p = NULL;
			}
		}
	}
	return 1;
}
//    
Status BFS(BiTree T) {
	queue qu;
	BiTree p;
	p = T;
	qu.push(p);
	while (!qu.empty()){
		p = qu.front();
		cout << p->data << ' ';
		if (p->lChild) qu.push(p->lChild);
		if (p->rChild) qu.push(p->rChild);
		qu.pop();
	}
	return 1;
}
int main() {
	BiTreeNode *Troot;
	int a[] = { 1,2,3,4,5,6,7,8,9,10};
	CreateBiTree(Troot);
	
	PreOrderBiTreeRec(Troot);
	cout << endl;
	PreOrderBiTreeUnRec(Troot);
	cout << endl;
	InOrderBiTreeRec(Troot);
	cout << endl;
	InOrderBiTreeUnRec(Troot);
	cout << endl;
	PostOrderBiTreeRec(Troot);
	cout << endl;
	PostOrderBiTreeUnRec(Troot);
	cout << endl;
	BFS(Troot);
	DestroyBiTreePostOrder(Troot);
	return 1;
}

テストサンプル:
//1 2 3-1 4-1-4-1-6 7-1-1 8-1 9-1/*                1              /   \             2       6          /   \     / \          3   5  7    8               \             \                 4             9*/