btree.cpp

二叉树应用

#include "iostream.h"

struct btree{
	char value;//名称
	int id;
	struct btree *lp,*rp;
};

typedef struct btree BTree;

BTree* InputTree();//返回树的指针，判断有无树根
int OutputTree(BTree *root,int level=0);
BTree* SearchNode(BTree *root, int id);
void DeleteTree(BTree *root);

int main()
{
	BTree* root;
	root=InputTree();
	OutputTree(root);
	DeleteTree(root);
	return 0;
}

BTree* InputTree()
{
	cout<<"Please input a tree!\n The format is \"the current node id space the parent node id\". "<<endl;\
	int cid,pid;
	char value;
	BTree *root,*p,*q;
	root=NULL;
	p=NULL;
	do{
		cout<<"\nInput current node id (<0 exit), parent node id, and node value(one char):";//输入树结构，以二叉树保存
		cin>>cid>>pid>>value;
		if(cid<0) break;
		if(root==NULL){
			root=new BTree;
			root->id=cid;
			root->value=value;
			root->lp=NULL;
			root->rp=NULL;
		}
		else{
			p=SearchNode(root,pid);//能否找到当前接点的父接点
			if(p==NULL) cout<<"Error parent id!"<<endl;
			else{
				q=new BTree;
				if(q==NULL){
					cout<<"System Error!!!"<<endl;
					break;
				}
				q->id=cid;
				q->value=value;
				q->lp=NULL;
				q->rp=NULL;
				if(p->lp==NULL) p->lp=q;
				else{
					p=p->lp;
					while(p->rp!=NULL) p=p->rp;//已经有子接点，直到右指针为空
					p->rp=q;
				}
			}
		}
	}while(1);	
	return root;
}

//假设用户输入的current id无重复
BTree* SearchNode(BTree *p, int id)
{
	BTree *p1,*p2;
	p1=p2=NULL;
	if(p->id==id) return p;
	if(p->lp!=NULL) p1=SearchNode(p->lp,id);//找当前接点的父接点，先根序递归调用。
	if(p->rp!=NULL) p2=SearchNode(p->rp,id);
	if(p1!=NULL) return p1;
	if(p2!=NULL) return p2;
	return NULL;
}

void DeleteTree(BTree *root)
{
	if(root==NULL) return;
	if(root->lp!=NULL) DeleteTree(root->lp);//后根遍历
	if(root->rp!=NULL) DeleteTree(root->rp);
	delete root;
}

int OutputTree(BTree *root,int level)
{
	if(root==NULL) return 0;
	for(int i=0;i<level;i++) cout<<' ';//递归函数，先将根接点打出，ROOT子树的根接点
	cout<<root->value<<endl;
	OutputTree(root->lp,level+1);//左，孩子//右，兄弟
	OutputTree(root->rp,level);
	return 1;
}