Tree Namespace Reference

自定义的树类都在Tree名字空间内 More...

Classes
class	binaryTree
	用二叉链表实现的二叉树类 More...
class	binTree
class	Tree
class	TreeException

Functions
template<class T , typename Comparator >
void	printBinaryTree (const binaryTree< T, Comparator > &bin_tree, const typename binaryTree< T, Comparator >::value_type &flag, std::ostream &out=std::cout)
	输出一棵二叉树 More...
template<class T , typename Comparator >
bool	operator== (const binaryTree< T, Comparator > &lhs, const binaryTree< T, Comparator > &rhs)
	比较两棵二叉树是否相同 "相同"是指： More...
static bool	GenTreeData (const char *_file_path="./test0.txt", const char *empty_flag="@")
	生成一个文件，内容是一棵二叉树的层次遍历 More...
template<typename T , typename Comparator >
static void	print_test_result (const binaryTree< T, Comparator > &binary_tree, const typename binaryTree< T, Comparator >::value_type &flag, std::ostream &out=std::cout)
	(测试用)将一棵二叉树的遍历结果插到输出流 More...

Detailed Description

自定义的树类都在Tree名字空间内

Function Documentation

GenTreeData()

static bool Tree::GenTreeData ( const char *  _file_path = "./test0.txt", const char *  empty_flag = "@"  )

static

生成一个文件，内容是一棵二叉树的层次遍历

Parameters

_file_path	文件路径
empty_flag	空结点标记

首先询问是否删除同名文件（若有）。 然后判断文件是否存在且可读，若是，则不做任何操作； 若否，则尝试新建文件。 函数返回true，只保证文件file_path存在，不保证其可读。

Returns

true 文件已存在，或生成成功

false 文件生成失败

Definition at line 39 of file test0.hh.

Referenced by main().

Here is the caller graph for this function:

operator==()

template<class T , typename Comparator >

bool Tree::operator==	(	const binaryTree< T, Comparator > &	lhs,
		const binaryTree< T, Comparator > &	rhs
	)

比较两棵二叉树是否相同 "相同"是指：

Template Parameters

T	数据类型
Comparator	数据类型的比较器类，默认为std::less<T>

Note

此函数模板的模板实参由函数实参表推断，用户无需指定

若类型T重载了operator<，则Comparator的默认类型std::less<T>将调用operator<，故实例化时不必指定tparam2；
否则，要求指定模板参数Comparator，which is a function object, 重载了bool operator(T t1, T t2)：当语义上t1 < t2时返回true。

Parameters

lhs	二叉树#1
rhs	二叉树#2

Returns

true #1和#2相同

false #1和#2不同

Definition at line 1462 of file binaryTree.hh.

print_test_result()

template<typename T , typename Comparator >

static void Tree::print_test_result ( const binaryTree< T, Comparator > &  binary_tree, const typename binaryTree< T, Comparator >::value_type &  flag, std::ostream &  out = std::cout  )

static

(测试用)将一棵二叉树的遍历结果插到输出流

Template Parameters

T	二叉树存储的数据的类型
Comparator	函数对象，用于比较T类型的数据：lhs < rhs 要求重载bool operator(const T &lhs, const T &rhs)

Parameters

binary_tree	二叉树类的对象
flag	类T的对象，表示空结点的特殊标记
out	输出流对象，要求是ostream类及其派生类的对象，如std::cout，或ofstream类的对象

Definition at line 108 of file test0.hh.

References Tree::binaryTree< T, Comparator >::height(), Tree::binaryTree< T, Comparator >::height_loop(), Tree::binaryTree< T, Comparator >::inOrder(), Tree::binaryTree< T, Comparator >::inOrder_loop(), Tree::binaryTree< T, Comparator >::levelOrder(), Tree::binaryTree< T, Comparator >::postOrder(), Tree::binaryTree< T, Comparator >::postOrder_loop(), Tree::binaryTree< T, Comparator >::preOrder(), Tree::binaryTree< T, Comparator >::preOrder_loop(), printBinaryTree(), Tree::binaryTree< T, Comparator >::size(), and Tree::binaryTree< T, Comparator >::size_loop().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

printBinaryTree()

template<class T , typename Comparator >

void Tree::printBinaryTree	(	const binaryTree< T, Comparator > &	bin_tree,
		const typename binaryTree< T, Comparator >::value_type &	flag,
		std::ostream &	out = std::cout
	)

输出一棵二叉树

Template Parameters

T

二叉树的数据类型

Parameters

bin_tree	二叉树类的对象
flag	用于表示空结点的特殊标记
out	输出流对象。默认是std::cout，也可以是ostream类及其派生类的对象，包括输出文件流等。

按层次顺序输出每个结点及其children，用于测试二叉树类实现的正确性。 该函数假定树中没有data相同的结点

Note

该函数模板被声明为binaryTree<T>类的友元仅作测试用，实际上不必作友元。
用于测试：

1. 二叉树类实现的正确性，包括lchild，rchild，root等API
2. 模板作同参模板的友元
3. 模板函数的模板实参的推断：tparam2是否能由binaryTree的tparam2的默认值推断？

Deprecated:

该函数仅作测试用，将在正式版本中删除。

Bug:

bin_tree中不允许含有data相同的结点，否则可能导致无限循环！

Definition at line 1426 of file binaryTree.hh.

References Tree::binaryTree< T, Comparator >::rchild().

Referenced by print_test_result(), and print_test_result().

Here is the call graph for this function:

Here is the caller graph for this function: