liststruct.cpp

实现二叉树以及排序二叉树等功能

//define the functions about List
#include "StdAfx.h"
#include "GlobalDefining.h"

#include "ListStruct.h"
#include <iostream.h>
#include <stdlib.h>

STATUS InitBiTree(BiTree &B)
{
	B=NULL;
	return OK;
}


STATUS InitQueue(SqQueue &Q)
{
	//构造一个空队列
	Q.base=(BiTNode **)malloc(MAXQSIZE * sizeof(BiTNode));
	if(!Q.base) exit(OVERFLOW);
	Q.front=Q.rear=0;
	return OK;
}

STATUS EnQueue(SqQueue &Q,BiTNode *e)
{

	//插入元素B为Q的新的队尾元素
	if((Q.rear+1)% MAXQSIZE==Q.front) return ERROR;//队列满
	Q.base[Q.rear]=e;
 	Q.rear=(Q.rear+1)%MAXQSIZE;
	return OK;
}
STATUS DeQueue(SqQueue &Q,BiTNode *&e)
{
	//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
	if(Q.front==Q.rear) return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	return OK;
}



void Insert_SortTree (BiTree &B, int x)
{
   if(B==NULL) 
   {
        B=(BiTNode*)malloc(sizeof(BiTNode)); 
		B->data = x;
        B->lchild = B->rchild = NULL;  
		return;  
   }
    BiTNode *q, *p = B;
    while(p != NULL)
    {
        if (x == p->data)  return;
        else if (x < p->data)
		{
            q = p;
            p = p->lchild;
        }
        else 
		{	 
            q = p;
            p = p->rchild;
        }
    } 
   BiTNode *newNode=(BiTNode*)malloc(sizeof(BiTNode));
    newNode->data = x;
    newNode->lchild = newNode->rchild = NULL;
    if (x < q->data)
        q->lchild = newNode;
    else q->rchild = newNode;
	
}




STATUS LevelOrderTraverse(BiTree B)
{
	SqQueue Q;
    InitQueue(Q);
	
    if(B!=NULL)    EnQueue(Q,B);
	BiTNode *p;
    while (Q.rear!=Q.front)
    {
        DeQueue(Q,p);
        cout<<p->data<<endl;
        if(p->lchild!= NULL) 
	      EnQueue(Q,p->lchild);  //左儿子入队
        if(p->rchild!= NULL)
	      EnQueue(Q,p->rchild);  //右儿子入队
    }
return OK;
}


STATUS InOrderTraverse(BiTree B)
{
	if(B!=NULL)
	{ 
		InOrderTraverse(B->lchild);
	    cout<<B->data<<endl;
        InOrderTraverse(B->rchild);
	}
	return OK;
}