STL学习笔记七----二叉查找树

本次实验写了一个简单的二叉查找树,并探寻了二叉查找树节点数量和树高之间的关系.

实验任务

Task 1

请基于所给代码实现BST类，至少应实现如下方法：

BinSearchTree(); // 默认构造函数

int size() const; // 获取存储元素的数目

int height() const; // 获取树高

void printTree(); // 打印BST的树形结构

Iterator insert(const T& item); // 元素的插入

~BinSearchTree(); // 析构函数

其中的部分方法建议用递归算法实现

Task2

生成一系列随机数，通过其从空树开始通过逐个插入的方式构造一个BST，计算该BST的树高；变换随机数序列的数值范围和数目，多次重复实验，获取n个节点BST平均树高的统计量；对所得结果进行数据拟合等分析，获取BST平均树高和节点数目之间的数学关系。

实验分析与代码

什么是二叉树

二叉查找树（Binary Search Tree），简写BST，是满足某些条件的特殊二叉树。

任何一个节点的左子树上的点，都必须小于当前节点。任何一个节点的右子树上的点，都必须大于当前节点。即满足,左小右大的原则。

右子节点的左子节点也必须大于当前节点,左子节点的右子节点也同理.

任何一棵子树，也都满足上面两个条件。另外二叉查找树中，是不存在重复节点的。

实验要求函数的逻辑

size()函数,在二叉树类型中声明一个变量count,初始时为0,构造器中自增,每次插入的时候自增,该函数负责返回变量count.
height(Node* root),该函数内部有三个int类型的局部变量,h为返回值,hl,hr为递归中下一次调用递归函数的返回值,hl和hr分别为递归调用的返回值,而参数为当前节点root的左子叶和右子叶.

函数的运行逻辑为,先判断当前节点为空,若空则返回0.

然后递归调用赋值hr和hl,然后判断hr和hl那个更大,则将其自增赋值给h,返回h.

递归调用的逻辑展开以后,从最末端的节点开始返回,该节点不唯一,当时不存在level比该节点更低的节点.
void printTree(),该函数负责打印二叉树
它需要三个参数,分别是常引用字符串prefix,Node的常指针node,布尔值isLeft

在定义或声明函数时，我们可以将函数的形参指定为引用的形式，这样在调用函数时就会将实参和形参绑定在一起，让它们都指代同一份数据。如此一来，如果在函数体中修改了形参的数据，那么实参的数据也会被修改，从而拥有“在函数内部影响函数外部数据”的效果。

函数的逻辑是,首先判断node是否为空指针,空则结束函数.

若不空,则输出prefix.

然后判断isLeft的的真假值,如果是左子叶,则输出制表符”├──”,否则输出”└──” 紧接着输出当前节点的值.

然后递归调用该函数两次,一次的node为当前节点的左子叶,一个为右子叶,一个的isLeft是true,一个是false.
Iterator insert(const T& item);

这个函数有递归和非递归两种,这里介绍递归的方法,递归需要一个额外的函数来辅助.

这个函数的声明是insert(const T& item, Node*& next, Node* parent),也就是要插入的值,node指针的引用,指向当前节点的父母节点的指针.

它的操作是,首先,如果当前节点为空,则直接申请内存空间,然后创建一个新的节点,把值赋进去.

然后不为空,则判断待插入值与目标节点的值的大小,大则将目标节点的右子叶(根据二叉树定义,大的值向右走)作为下一次递归调用的目标节点,否则为左子叶.

这样就能找到待插入值在二叉树中的应该查找的位置.

代码

点击查看源码

#ifndef BST_H
#define BST_H

#include <iostream>
#include <string>
#include <iomanip>

#define NULL 0
using namespace std;
template<typename T>
class BinSearchTree
{
	class Iterator; //very important!!!
	//typedef typename BinSearchTree<T>::Iterator BST_ITERATOR;

private:

	struct Node
	{
		T item;
		Node* parent;
		Node* left;
		Node* right;
	}; // Node

	Node* root;

	int count;

public:

	// Postcondition: this BinSearchTree is empty.
	BinSearchTree(); //  default constructor

   // Postcondition: the number of items in this BinSearchTree
   //                has been returned.
	int size() const;



	// Postcondition: the height of this BinSearchTree
	//                has been returned.
	int height() const;
	int height(Node* root) const;

	// Postcondition: item has been inserted into this BinSearchTree. An iterator 
	//                positioned at the inserted item has been returned. The
	//                averageTime(n) is O(log n) and worstTime(n) is O(n).
	Iterator insert(const T& item);
	Iterator insert(const T& item, Node*& next, Node* parent);
	

	// Postcondition: if there is an item in this BinSearchTree that equals item,
	//                the value returned is an iterator pointing to that item.
	//                Otherwise, the value returned is an iterator with the same
	//                value as the iterator returned by the end( ) method.  The
	//                averageTime(n) is O(log n) and worstTime(n) is O(n).
	Iterator find(const T& item) const;

	// Precondition: itr is positioned at an item in this BinSearchTree.
	// Postcondition: the item that itr is positioned at has been deleted from
	//                this BinSearchTree.  The averageTime(n) is O(log n)
	//                and worstTime(n) is O(n).
	void erase(Iterator itr);

	// Postcondition: The space allocated for this BinSearchTree has been
	//                deallocated.  The worstTime(n) is O(n).
	~BinSearchTree();

	void destory(Node* t);

	// Postcondition: The tree-shape of this BinSearchTree has been printed
	void printTree();

	void printhelp(const string& prefix, const Node* node, bool isLeft) const;

	class Iterator
	{
		friend class BinSearchTree<T>;

	private:

		Node* curr;
		Iterator(Node* currNode);

	public:

		Iterator();

		Iterator& operator++ ();

		Iterator& operator-- ();

		T& operator* () const;

		bool operator== (const Iterator& otherIterator)const;

	}; // Iterator

	// Postcondition: if this BinSearchTree is non-empty, an iterator positioned
	//                at the smallest item in the tree has been returned.
	//                Otherwise, the iterator returned has the same value as the
	//                iterator returned by the end( ) method.
	Iterator begin();


	// Postcondition: the value returned is an iterator that can be used in a 
	//                comparison for ending the traversal of this BinSearchTree.
	//                If this BinSearchTree is non-empty, the largest item is in the
	//                position just before the position of the iterator returned.
	Iterator end();

}; // BinSearchTree



//************************the following is the implmentation of the bst class interfaces***********************************
template<typename T>
BinSearchTree<T>::BinSearchTree()
{
	//默认构造器
	root = NULL;
	count = 0;
}

template<typename T>
int BinSearchTree<T>::size() const
{
	return count;
}

template<typename T>
int BinSearchTree<T>::height() const
{
	return height(root);
}
template<typename T>
int BinSearchTree<T>::height(Node* root) const
{
	//根节点为空的时候,返回高度为0
	if (root == NULL)
	{
		return 0;
	}

	int hl = height(root->left);//递归遍历左子树
	int hr = height(root->right);//递归遍历右子树

	int h = 0;
	h = ((hr > hl) ? hr : hl) + 1;
	//如果hr大于hl,那么取hr的值,并把hr+1赋给h
	//如果hr不大于hl,那么取hl的值,并把hl+1赋给h
	return h;


}

template<typename T>
typename BinSearchTree<T>::Iterator BinSearchTree<T>::insert(const T& item)
{
	//当根节点为空,创建新节点,值为item并以此为根节点
	if (root == NULL)
	{
		root = new Node;
		root->parent = NULL;
		root->left = NULL;
		root->right = NULL;
		root->item = item;
		count++;
		return begin();
	}
	//根节点不为空,且待插入值大于根节点值
	else if (item > root->item)
	{
		//在根节点的右子叶插入值
		return insert(item, root->right, root);
	}
	else
	{
		//在根节点的左子叶插入值
		return insert(item, root->left, root);
	}
}
template<typename T>
typename BinSearchTree<T>::Iterator BinSearchTree<T>::insert(const T& item, Node*& next, Node* parent)
{
	//当目标节点为空时,直接将待插入值放入新节点,并令目标节点为新节点
	if (next == NULL)
	{
		next = new Node;
		next->parent = parent;
		next->left = NULL;
		next->right = NULL;
		next->item = item;
		count++;
		return Iterator(next);
	}
	//否则,根据二叉搜索树的定义进行递归,直到寻找的空的目标节点为止
	else if (item > next->item)
	{
		return insert(item, next->right, next);
	}
	else
	{
		return insert(item, next->left, next);
	}

}

template<typename T>
void BinSearchTree<T>::printTree()
{
	printhelp("", root, false);
}

template<typename T>
void BinSearchTree<T>::printhelp(const string &prefix,const Node* node,bool isLeft) const
{
	if (node != nullptr)
	{
		cout << prefix;

		cout << (isLeft ? "├── " : "└── ");

		cout << node->item << endl;

		printhelp(prefix + (isLeft ? "│   " : "    "), node->left, true);
		printhelp(prefix + (isLeft ? "│   " : "    "), node->right, false);
	}
}

template<typename T>
typename BinSearchTree<T>::Iterator BinSearchTree<T>::find(const T& item) const
{
	Node* i = root;
	while (i != NULL)
	{
		if (i->item == item)
		{
			return Iterator(i);
		}
		else if (item > i->item)
		{
			i = i->right;
		}
		else
		{
			i = i->left;
		}

	}
	return end();
}


template<typename T>
void BinSearchTree<T>::erase(Iterator itr)
{
	Node* curr = itr.curr;
	if (curr->left == NULL && curr->right == NULL)
	{
		curr->parent = NULL;
		delete curr;
	}
	else if (curr->left == NULL)
	{
		if (curr->parent->item > curr->item)
		{
			curr->parent->left = curr->right;
		}
		else
		{
			curr->parent->right = curr->right;
		}
		delete curr;
	}
	else if (curr->right == NULL)
	{
		if (curr->parent->item > curr->item)
		{
			curr->parent->left = curr->left;
		}
		else
		{
			curr->parent->right = curr->left;
		}
		delete curr;
	}
	else
	{
		Node* s = curr->left;
		while (s != NULL)
		{
			s = s->right;
		}
		curr->item = s->item;
		itr.curr = s;
		erase(itr);
	}
}

template<typename T>
BinSearchTree<T>::~BinSearchTree()
{
	destory(root);
}
template<typename T>
void BinSearchTree<T>::destory(Node* t)
{
	if (t != NULL)
	{
		destory(t->left);
		destory(t->right);
		delete(t);
	}
}

template<typename T>
typename BinSearchTree<T>::Iterator BinSearchTree<T>::begin()
{
	//not finished
	return Iterator(root);
}

template<typename T>
typename BinSearchTree<T>::Iterator BinSearchTree<T>::end()
{
	return Iterator();
}

//************************the following is the implmentation of the iterator inner class***********************************
template<typename T>
BinSearchTree<T>::Iterator::Iterator(Node* currNode)
{
	curr = currNode;
}

template<typename T>
BinSearchTree<T>::Iterator::Iterator()
{
}

template<typename T>
typename BinSearchTree<T>::Iterator& BinSearchTree<T>::Iterator::operator++()
{
	Node* t;
	if (curr->right != NULL)
	{
		curr = curr->right;
		while (curr->left != NULL)
		{
			curr = curr->left;
		}
	}
	else
	{
		t = curr->parent;
		while (curr == t->right)
		{
			curr = t;
			t = t->parent;
			if (t == NULL)
			{
				return end();
			}
		}
		curr = t;
	}
	return *this;
}

template<typename T>
typename BinSearchTree<T>::Iterator& BinSearchTree<T>::Iterator::operator--()
{
	Node* t;
	if (curr->right != NULL)
	{
		curr = curr->right;
		while (curr->left != NULL)
		{
			curr = curr->left;
		}
	}
	else
	{
		t = curr->parent;
		while (curr == t->right)
		{
			curr = t;
			t = t->parent;
			if (t == NULL)
			{
				return end();
			}
		}
		curr = t;
	}
	return *this;
}

template<typename T>
T& BinSearchTree<T>::Iterator::operator* () const
{
	return curr->item;
}

template<typename T>
bool  BinSearchTree<T>::Iterator::operator==(const Iterator& otherIterator) const
{
	return curr == otherIterator.curr;
}


#endif

Task2验证的思路

在主程序中测试时,需要几个变量,首先是随即生成节点的值的最大值MAX,然后是生成的二叉树的最大节点数nodeNum,最后是每个有着不同节点数量的二叉树要重复生成并计算多少次num.
双循环,外循环是增加当前重复计算平均树高的二叉树的节点数量.
内循环是对节点数量相同的二叉树进行nodeNum次模拟,并计算平均树高.
外循环每结束一次,对外输出一次”但有n个节点的时候,二叉树的平均数高为:”+平均树高.
之后利用得到的数据,初步判断其回归方程的类型,利用excel进行回归分析.

实验验证结果

点击查看原始数据

当有1个节点的时候,平均树高为1

当有2个节点的时候,平均树高为2

当有3个节点的时候,平均树高为2.645

当有5个节点的时候,平均树高为3.78

当有6个节点的时候,平均树高为4.24

当有7个节点的时候,平均树高为4.72

当有8个节点的时候,平均树高为5.08

当有9个节点的时候,平均树高为5.285

当有10个节点的时候,平均树高为5.755

当有11个节点的时候,平均树高为5.845

当有12个节点的时候,平均树高为6.15

当有13个节点的时候,平均树高为6.435

当有14个节点的时候,平均树高为6.775

当有15个节点的时候,平均树高为6.79

当有16个节点的时候,平均树高为7.07

当有17个节点的时候,平均树高为7.18

当有18个节点的时候,平均树高为7.46

当有19个节点的时候,平均树高为7.58

当有20个节点的时候,平均树高为7.765

当有21个节点的时候,平均树高为7.83

当有22个节点的时候,平均树高为8.025

当有23个节点的时候,平均树高为8.26

当有24个节点的时候,平均树高为8.215

当有25个节点的时候,平均树高为8.325

当有26个节点的时候,平均树高为8.47

当有27个节点的时候,平均树高为8.75

当有28个节点的时候,平均树高为8.84

当有29个节点的时候,平均树高为8.975

当有30个节点的时候,平均树高为8.975

当有31个节点的时候,平均树高为9.16

当有32个节点的时候,平均树高为9.18

当有33个节点的时候,平均树高为9.465

当有34个节点的时候,平均树高为9.375

当有35个节点的时候,平均树高为9.59

当有36个节点的时候,平均树高为9.77

当有37个节点的时候,平均树高为9.795

当有38个节点的时候,平均树高为9.77

当有39个节点的时候,平均树高为9.985

当有40个节点的时候,平均树高为9.93

当有41个节点的时候,平均树高为10.17

当有42个节点的时候,平均树高为10.355

当有43个节点的时候,平均树高为10.375

当有44个节点的时候,平均树高为10.345

当有45个节点的时候,平均树高为10.49

当有46个节点的时候,平均树高为10.545

当有47个节点的时候,平均树高为10.815

当有48个节点的时候,平均树高为10.7

当有49个节点的时候,平均树高为10.825

当有50个节点的时候,平均树高为10.82

当有51个节点的时候,平均树高为10.94

有52个节点的时候,平均树高为10.975

当有53个节点的时候,平均树高为11.045

当有54个节点的时候,平均树高为11.055

当有55个节点的时候,平均树高为11.16

当有56个节点的时候,平均树高为11.305

当有57个节点的时候,平均树高为11.22

当有58个节点的时候,平均树高为11.355

当有59个节点的时候,平均树高为11.475

当有60个节点的时候,平均树高为11.415

当有61个节点的时候,平均树高为11.635

当有62个节点的时候,平均树高为11.385

当有63个节点的时候,平均树高为11.735

当有64个节点的时候,平均树高为11.73

当有65个节点的时候,平均树高为11.835

当有66个节点的时候,平均树高为11.625

当有67个节点的时候,平均树高为11.68

当有68个节点的时候,平均树高为11.91

当有69个节点的时候,平均树高为12.04

当有70个节点的时候,平均树高为11.89

当有71个节点的时候,平均树高为11.88

当有72个节点的时候,平均树高为12.055

当有73个节点的时候,平均树高为12.205

当有74个节点的时候,平均树高为12.39

当有75个节点的时候,平均树高为12.175

当有76个节点的时候,平均树高为12.16

当有77个节点的时候,平均树高为12.43

当有78个节点的时候,平均树高为12.465

当有79个节点的时候,平均树高为12.495

当有80个节点的时候,平均树高为12.33

当有81个节点的时候,平均树高为12.45

当有82个节点的时候,平均树高为12.455

当有83个节点的时候,平均树高为12.67

当有84个节点的时候,平均树高为12.725

当有85个节点的时候,平均树高为12.775

当有86个节点的时候,平均树高为12.87

当有87个节点的时候,平均树高为12.7

当有88个节点的时候,平均树高为12.7

当有89个节点的时候,平均树高为12.89

当有90个节点的时候,平均树高为12.93

当有91个节点的时候,平均树高为13.08

当有92个节点的时候,平均树高为13.06

当有93个节点的时候,平均树高为13.235

当有94个节点的时候,平均树高为13.065

当有95个节点的时候,平均树高为13.055

当有96个节点的时候,平均树高为13.2

当有97个节点的时候,平均树高为13.28

当有98个节点的时候,平均树高为13.095

当有99个节点的时候,平均树高为13.24

当有100个节点的时候,平均树高为13.5

由上图可见,二者之间为对数关系