bitree.cpp

二叉树的实现代码 前序遍历 中序遍历 后序遍历

#include<iostream.h>
#include"head.h"


Status InitBiTree(BiTree &pTree)
{	
  pTree=(BiTNode*)malloc(sizeof(BiTNode));
  if(!pTree) exit(OVERFLOW);
  pTree->lChild=pTree->rChild=NULL;
	return OK;
}

Status DestroyBiTree(BiTree &pTree)
{
	if(!pTree) return ERROR;
	else{
		if(pTree->lChild)
			DestroyBiTree(pTree->lChild);
		else if(pTree->rChild)
			DestroyBiTree(pTree->rChild);
		free(pTree);
		pTree=NULL;
	}

	return OK;
}


Status CreateTree(BiTree &pTree) /*Input Example: abd##e##cf##g##*/
{
    char ch;
    cin>>ch;
    if(ch=='#')
    {
        pTree=NULL;
    }
    else
    {
        if(!(pTree=(BiTNode*)malloc(sizeof(BiTNode))))
        {
            exit(OVERFLOW);
        }
        pTree->Data=ch;
        CreateTree(pTree->lChild);
        CreateTree(pTree->rChild);
    }
return OK;
}

Status ClearBiTree(BiTree &pTree)
{
    if(pTree)
    {
        if(ClearBiTree(pTree->lChild))
        {
            if(ClearBiTree(pTree->rChild))
            {
                cout<<"Deleting :"<<pTree->Data;
                free((void*)pTree);
                return OK;
            }
        }
        return ERROR;
    }
    else
    {
        return OK;
    }
}  

Status Visit(char Data)
{
    cout<<Data;
    return OK;
}

void PreOrderTraval(BiTree &pTree)
{
    if(pTree)
    {
		Visit(pTree->Data);
        PreOrderTraval(pTree->lChild);
		PreOrderTraval(pTree->rChild);
    }
    
}





void InOrderTraval(BiTree &pTree)
{
   if(pTree)
   {
		InOrderTraval(pTree->lChild);
		Visit(pTree->Data);
		(InOrderTraval(pTree->rChild));
		
   }
}



void PostOrderTraval(BiTree &pTree)
{
    if(pTree)
    {
        PostOrderTraval(pTree->lChild);
		PostOrderTraval(pTree->rChild);
		Visit(pTree->Data);
    }
}

int BiLeafCount(BiTree pTree)
{
	if(pTree==NULL)
		return(0);
	else if(pTree->lChild==NULL && pTree->rChild==NULL)
		return(1);
	else
		return (BiLeafCount(pTree->lChild)+BiLeafCount(pTree->rChild));

}//

int BiTreeDepth(BiTree pTree)
{
    int ldepth = 0;
    int rdepth = 0;

    if(pTree==NULL)
		return 0;
    ldepth=BiTreeDepth(pTree->lChild);
    rdepth=BiTreeDepth(pTree->rChild);
    return 1+(ldepth>rdepth?ldepth:rdepth);
}




Status InOrderTraverse(BiTree pTree,Status (*Visit)(char Data))
{
    
	SqStack S;
    InitStack(S);
    BiTree p;
	
	p=pTree;
while(p||!StackEmpty(S)){
		if(p){
			Push(S,p);
			p=p->lChild;
		}
		else{
			Pop(S,p);
			if(!Visit(p->Data)) return ERROR;
			p=p->rChild;
			}
		}
	return OK;
	
return OK;
}

   
void AllPath(BiTree pTree,SqStack &S2) {

// 输出所有从根到叶的路径

	if (pTree) {

Push(S2,pTree);

if (!pTree->lChild && !pTree->rChild )
{ 
StackTraverse(S2,vist);
cout<<",";
}

else {

AllPath( pTree->lChild,S2);

AllPath( pTree->rChild,S2);

}

Pop(S2,pTree);

}

} // AllPath