bitree.cpp

创建一棵二叉排序树

//定义二叉树的函数
#include "stdafx.h"
#include "BiTree.h"
#include "Queue.h"
#include "GlobalDefining.h"
#include <iostream.h>
//二叉排序树的插入操作
void Insert_SortTree (BiTree &ST, int x)
{ 		   
	BiTNode *s,*t; 
	BiTNode* p = new BiTNode;
    p->data = x;
	p->lchild = NULL;
	p->rchild = NULL;
	if(ST == NULL)
		ST = p;
	s = ST; 
	while(s != NULL)
	{  
		 t = s;               //t用来记录s的双亲结点
		 if(s->data > x)
		 s = s->lchild;
		 else if(s->data < x)
		 s = s->rchild;
		 else
            return;

	}
    if(t->data > x)             //比较x与t的data的大小确定插入的位置
		t->lchild = p;
	else
	    t->rchild = p;
}
		
//二叉树的中序遍历算法
void InOrderTraverse (BiTree  ST)
{
        if (ST)
        {   
        	InOrderTraverse (ST->lchild);   //利用递归算法实现遍历
	        cout<<ST->data<<",";
        	InOrderTraverse (ST->rchild);
        }

}


//定义队列的操作
STATUS InitQueue (SqQueue &Q)
{
    if (Q.base == NULL) 
		return OVERFLOW;  
    Q.queuesize = MAXQSIZE;
    Q.front = 0;
    Q.rear = 0;
    return OK;
}// 构造一个最大存储空间为 maxsize 的空循环队列 Q


STATUS EnQueue (SqQueue &Q, BiTNode *e)
{  
    if ((Q.rear+1) % Q.queuesize == Q.front) 
        return ERROR;                        //队列满则返回ERROR
    Q.rear = (Q.rear+1) % Q.queuesize;
    Q.base[Q.rear] = e;
    return OK;
}// 插入元素e为Q的新的队尾元素

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

//二叉树的层次遍历函数
void LevelTraverse (BiTree T)
{
	SqQueue Q;
    InitQueue(Q);               //定义一循环队列并初始化
    if(T != NULL)  
	   EnQueue(Q, T);
    BiTNode *p = T;
    while (Q.rear != Q.front)
    {
        DeQueue(Q, p);
        cout<<p->data<<",";

        if(p->lchild != NULL) 
	    EnQueue(Q, p->lchild);  //左儿子入队

        if(p->rchild != NULL)
	    EnQueue(Q, p->rchild); //右儿子入队
    }
}