treestruct.cpp

创建一棵二叉树

//define the functions about Tree

#include "stdafx.h"
#include "GlobalDefining.h"
#include "TreeStruct.h"
#include "QueueStruct.h"
#include <iostream.h>
#include <stdlib.h>


extern STATUS InitQueue (SqQueue &Q);  //构造一个空队列
extern STATUS EnQueue (SqQueue &Q, BiTree e);  //插入元素e为Q的新的队尾元素
extern STATUS DeQueue (SqQueue &Q, BiTree &e); //删除Q的队头元素，用e返回其值


//有关BiTree的基本操作包括：
/*
STATUS InitTree(BiTree &T);
void DestroyTree(BiTree &T);
void Insert_SortTree (BiTree &T, int data);
void InOrderTraverse (BiTree &T);
void LevelTraverse (BiTree &T);
*/


STATUS InitTree(BiTree &T)    //初始化二叉树T
{
    T = NULL;
	return OK;
}

void DestroyTree(BiTree &T)   //逐个销毁二叉树T中的每个结点
{	
	if (T == NULL) 
		return; 
	else
	{ 
		DestroyTree(T->lchild); 
		DestroyTree(T->rchild); 
		free(T); 
	}	
}



void Insert_SortTree (BiTree &T, int data)  //二叉排序树的建立
{
	BiTree newT, p, q;
	newT = (BiTree)malloc(sizeof(BiTNode));
	newT->data = data;
	newT->lchild = NULL;
	newT->rchild = NULL;
	if( T == NULL )
		T = newT;
	q = T;                    //q指向树根
	while ( q != NULL )
	{
		p = q;   
		if ( q->data == data )
			return;
		if ( q->data > data )  //p用来记录q的双亲结点
			q = q->lchild;
		else 
			q = q->rchild;
	}
	if ( p->data < data )            //确定newT插入的位置
		p->rchild = newT;
	else 
		p->lchild = newT;
}


void InOrderTraverse (BiTree &T)      //利用递归算法实现中序遍历
{
        if ( T != NULL )
        {   
        	InOrderTraverse (T->lchild);
			cout<<T->data<<" ";
        	InOrderTraverse (T->rchild);
        }
}


void LevelTraverse(BiTree &T)    //实现层次遍历
{
	SqQueue Q;
    InitQueue(Q);
    if(T != NULL)              //将根放入队列
		EnQueue(Q, T);
    BiTree p;
    while ( Q.front != Q.rear )            //当队列非空时
    {
        DeQueue(Q, p);
        cout<<p->data<<" ";         // 从队列取出一个元素并访问
        if(p->lchild != NULL)
			EnQueue(Q, p->lchild);  // 如果该元素有右子树就将它放入队列
        if(p->rchild != NULL)
			EnQueue(Q, p->rchild);  // 如果该元素有左子树就将它放入队列
    }
}