bitree.cpp

设计一个应用程序能将一组整数数据按由小到大的顺序存 放在一个连续的整数表（顺序表）中

// bitree.cpp: implementation of the bitree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include <iostream.h>
#include "sequen.h"
#include "bitree.h"

// 参数：binode - 欲加入树中的结点
//		 tree - 要插入结点的子树
// 返回值：插入了新结点的子树
node* bitree::insertnode(node* binode, node* tree)
{										// 将结点binode插入到tree子树中
	if(tree == 0)
		return binode;
	if(binode->item < tree->item)
		tree->left = insertnode(binode, tree->left);	// 插入左子树
	else if(binode->item > tree->item)
		tree->right = insertnode(binode, tree->right);	// 插入右子树
	else
		delete binode;
	return tree;						// 返回新子树
}

// 参数：val - 欲插入树的结点值
// 返回值：标志插入操作是否成功的布尔标志
bool bitree::insert(int val)			// 将整数val插入到树中
{
	node* binode = new node;			// 分配一个结点
	bool ok = false;
	if(binode != 0)
	{
		binode->item = val;				// 为结点赋值
		binode->left = binode->right = 0;
		root = insertnode(binode, root);// 将结点插入到以root为根的树中
		ok = true;
	}
	return ok;
}

// 参数：binode - 被显示输出的子树
void bitree::printnode(node* binode)	// 输出以binode结点为根的子树
{
	if(binode != 0)
	{
		printnode(binode->left);		// 首先输出左子树的各结点
		cout << binode->item << " ";
		printnode(binode->right);		// 最后输出右子树的各结点
	}
}

void bitree::print()
{
	printnode(root);
	cout << "\n";
}

// 参数：seq - 欲转换为树的有序序列
//		 low - 序列低端元素的序数
//		 high - 序列高端元素的序数
// 返回值：由序列构造产生的二叉树
node* maketree(sequen* seq, int low, int high)
{										// 递归将一个有序列构造成一棵树
	int mid = (low + high) / 2;
	node* binode = new node;
	if(binode != 0)
	{
		binode->item = seq->items[mid];
		binode->left = (mid <= low ? 0 : maketree(seq, low, mid - 1));
		binode->right = (mid >= high ? 0 : maketree(seq, mid + 1, high));
	}
	return binode;
}

// 参数：seq - 欲转换为树的有序序列
//		 low - 序列低端元素的序数
//		 high - 序列高端元素的序数
void bitree::seqtotree(sequen* seq, int low, int high)
{						// 将一个有序列对象通过maketree()函数转换成一个二叉树对象
	if(low == 0 && high == 0)
		high = seq->used;
	root = (low < 0 || high < 0 || low > seq->used || high > seq->used)
		? 0 : maketree(seq, low, high);
}