04071505tree.h

数据结构的部分算法程序。相对来说是通用算法中效率比较高的程序

#include<iostream.h>
#include<malloc.h>
const MAX_TREE_SIZE=100;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

/*typedef struct BiTNode
{
	TElemType data;
	BiTNode *lchild,*rchild,*parent;
}*BiTree;
*/
typedef struct BiTNode
{
  TElemType data;
  union {  BiTNode *lchild,*FirstChild;  };
  union {  BiTNode *rchild,*NextSibling; };
} *BiTree,TNode,*tree,*forest;


//先序遍历
void preorder(BiTree T,void visit(TElemType))
{
	if(T)
	{
		visit(T->data);
		preorder(T->lchild,visit);
		preorder(T->rchild,visit);
	}
}
//中序遍历
void inorder(BiTree T,void visit(TElemType))
{
	if(!T) return;
	inorder(T->lchild,visit);
	visit(T->data);
	inorder(T->rchild,visit);
}
//后序遍历
void postorder(BiTree T,void visit(TElemType))
{
	if(!T) return;
	postorder(T->lchild,visit);
	postorder(T->rchild,visit);
	visit(T->data);
}
//广义表形式
void preorderlists(BiTree T,void visit(TElemType))
{
	if(T)
	{
		visit(T->data);
		if(T->lchild||T->rchild)
		{
			cout<<"(";preorderlists(T->lchild,visit);
			cout<<",";preorderlists(T->rchild,visit);
			cout<<")";
		}
	}
	else cout<<"^";
}
//创建二叉树
void CreateBiTree(BiTree &T,char s[],int &i)
{
	i++;
	if(s[i]=='#') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=s[i];
		CreateBiTree(T->lchild,s,i);
		CreateBiTree(T->rchild,s,i);
	}
}
void CreateBiTree(BiTree &T,char s[])//包装
{	int i=-1;	CreateBiTree(T,s,i);}

int Depth(BiTree T) //求树的深度
{ 
	int dl,dr;
    if (!T) return 0;
    dl=Depth(T->lchild);   
	dr=Depth(T->rchild);
    return dl>dr?dl+1:dr+1;
}
/////////////////////////////////////////////
//树的有关操作(用二叉树的基本操作)
//只写了部分操作

void visit(TElemType e) {cout<<e;}
//先序遍历，类似二叉树的先序遍历
void preorderT(tree T,void visit(TElemType)) 
{
  if (T)
  {
	  visit(T->data);
      preorderT(T->FirstChild,visit); 
      preorderT(T->NextSibling,visit);
  }
}

//树的后序遍历，相当于二叉树的中序遍历
void postorderT(tree T,void visit(TElemType))
 { 
  if (!T) return;
  postorderT(T->FirstChild,visit); 
  visit(T->data);
  postorderT(T->NextSibling,visit); 
}

//广义表形式
void PreorderListsT(tree T,void visit(TElemType)) 
{
  if (!T) return;
  visit(T->data); 
  if (T->FirstChild) cout<<'(';
  PreorderListsT(T->FirstChild,visit); 
  if (T->FirstChild) cout<<')';
  if (T->NextSibling) cout<<',';
  PreorderListsT(T->NextSibling,visit); 
}

//创建树
void CreateTree(tree &T,char s[],int &i)
{
	i++;
	if(s[i]=='#') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=s[i];
		CreateTree(T->lchild,s,i);
		CreateTree(T->rchild,s,i);
	}
}
void CreateTree(tree &T,char s[])//包装
{	int i=-1;	CreateTree(T,s,i);}