用二叉链表实现的二叉树类 More...

#include <binaryTree.hh>

Collaboration diagram for Tree::binaryTree< T, Comparator >:

Classes
struct	BinNode
	二叉链表的结点类 More...

Public Types
typedef T	value_type
	类型别名定义 More...

typedef value_type &	reference
	数据的引用 More...

typedef size_t	size_type
	计数器类型 More...

Public Member Functions
	binaryTree ()
	Construct a new binary Tree object. More...

	binaryTree (const value_type &x)
	Construct a new binary Tree object. More...

	binaryTree (const binaryTree &rhs)
	Construct a new binary Tree object 拷贝构造函数 More...

binaryTree &	operator= (const binaryTree &rhs)
	赋值运算符重载 More...

	binaryTree (binaryTree &&rhs)
	Construct a new binary Tree object 移动构造函数 More...

binaryTree &	operator= (binaryTree &&rhs)
	移动赋值运算符 More...

	~binaryTree ()
	Destroy the binary Tree object. More...

void	clear ()
	清空二叉树函数返回后，对象的成员root_将被置nullptr More...

bool	empty () const
	判断二叉树是否为空树 More...

value_type	root (const value_type &flag) const
	返回根结点的数据 More...

value_type	lchild (const value_type &x, const value_type &flag) const
	获得数据为x的结点的左child More...

value_type	rchild (const value_type &x, const value_type &flag) const
	获得数据为x的结点的右child More...

void	delLeft (const value_type &x)
	删除左subtree More...

void	delRight (const value_type &x)
	删除右subtree More...

void	preOrder (std::ostream &out=std::cout) const
	前序遍历(递归版本) More...

void	preOrder_loop (std::ostream &out=std::cout) const
	前序遍历(非递归版本) More...

void	inOrder (std::ostream &out=std::cout) const
	中序遍历(递归版本) More...

void	inOrder_loop (std::ostream &out=std::cout) const
	中序遍历(非递归版本) More...

void	postOrder (std::ostream &out=std::cout) const
	后序遍历(递归版本) More...

void	postOrder_loop (std::ostream &out=std::cout) const
	后序遍历(非递归版本) More...

void	levelOrder (std::ostream &out=std::cout) const
	层次遍历 More...

void	createTree (const value_type &flag=value_type{}, std::istream &in=std::cin)
	Create a Tree object. More...

value_type	parent (value_type x, const value_type &flag) const
	返回数据为x的结点的parent结点 More...

size_type	height () const
	返回二叉树的高度(递归版本) More...

size_type	height_loop () const
	返回二叉树的高度(非递归版本) More...

size_type	size () const
	返回二叉树的结点数(递归版本) More...

size_type	size_loop () const
	返回二叉树的结点数(非递归版本) More...

void	swaplr ()
	交换左右子树 More...

size_type	CountDegreeTwo () const
	统计树中度为2的结点的个数 More...

bool	isCompleteTree () const
	返回是否完全二叉树 More...

bool	isFullBinaryTree () const
	是否满二叉树 More...

Static Public Member Functions
static bool	is_symmetrical_tree (const binaryTree &lhs, const binaryTree &rhs)
	判断两棵二叉树是否互为镜像两棵二叉树#1和#2互为镜像，如果二者皆为空树；或二者根结点的值相同，且#1的左、右子树与#2的右、左子树互为镜像 More...

Public Attributes
const typedef value_type &	const_reference
	数据的常量引用 More...

Private Member Functions
BinNode *	find (const value_type &x, BinNode *root) const
	在以root为根的树中(前序)查找数据为x的结点，返回指向该结点的指针 More...

void	clear (BinNode *&root)
	清空以root为根结点的树，包括清除根结点 More...

BinNode *	clone (BinNode *_root) const
	Internal method to clone subtree. More...

void	preOrder (BinNode *root, std::ostream &out=std::cout) const
	前序遍历以root为根结点的树(递归版本) More...

void	inOrder (BinNode *root, std::ostream &out=std::cout) const
	中序遍历以root为根结点的树(递归版本) More...

void	postOrder (BinNode *root, std::ostream &out=std::cout) const
	后序遍历以root为根结点的树(递归版本) More...

size_type	size (BinNode *_root) const
	返回以指定结点为根结点的二叉树的规模(递归版本) More...

size_type	size_loop (BinNode *_root) const
	返回以指定结点为根结点的二叉树的规模(非递归版本) More...

size_type	height (BinNode *_root) const
	返回以指定结点为根结点的二叉树的高度(递归版本) More...

size_type	height_loop (BinNode *_root) const
	返回以指定结点为根结点的二叉树的高度(非递归版本) More...

size_type	CountDegreeTwo (BinNode *_root) const
	统计树中度为2的结点的个数 More...

void	swaplr (BinNode *_root)
	交换左右子树 More...

Static Private Member Functions
static bool	is_symmetrical_subtree (BinNode root1, BinNode root2)
	Internal method to 判断两棵二叉树是否相互对称 More...

static bool	value_type_less (const value_type &lhs, const value_type &rhs)
	比较value_type类型对象的大小。 More...

static bool	value_type_equal (const value_type &lhs, const value_type &rhs)
	比较value_type类型对象的大小。 More...

static bool	value_type_less_equal (const value_type &lhs, const value_type &rhs)
	比较value_type类型对象的大小。 More...

static bool	is_equal_subtree (BinNode _root1, BinNode _root2)
	判断两棵二叉树是否相同 "相同"是指：两棵树的形状及对应结点的值相等 More...

Private Attributes
BinNode *	root_
	二叉树的根结点 More...

Static Private Attributes
static Comparator	is_less_than_ = Comparator{}
	比较器(function object) More...

Friends
bool	operator== (const binaryTree &lhs, const binaryTree &rhs)
	比较两棵二叉树是否相同 "相同"是指： More...

void	printBinaryTree (const binaryTree &bin_tree, const typename binaryTree ::value_type &flag, std::ostream &out)

Detailed Description

template<typename T, typename Comparator>
class Tree::binaryTree< T, Comparator >

用二叉链表实现的二叉树类

Template Parameters

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

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

要求对T重载了operator<< 和 operator>>。建议每个对象的输出在一行以内

Warning: 若树中存储了data相同的结点，则私有find方法调用该方法的公有方法可能出现异常！

Definition at line 53 of file binaryTree.hh.

Member Typedef Documentation

◆ reference

template<typename T , typename Comparator >

typedef value_type& Tree::binaryTree< T, Comparator >::reference

数据的引用

Definition at line 109 of file binaryTree.hh.

◆ size_type

template<typename T , typename Comparator >

typedef size_t Tree::binaryTree< T, Comparator >::size_type

计数器类型

Definition at line 111 of file binaryTree.hh.

◆ value_type

template<typename T , typename Comparator >

typedef T Tree::binaryTree< T, Comparator >::value_type

类型别名定义

数据类型

Definition at line 108 of file binaryTree.hh.

Constructor & Destructor Documentation

◆ binaryTree() [1/4]

template<typename T , typename Comparator >

Tree::binaryTree< T, Comparator >::binaryTree ( )

inline

Construct a new binary Tree object.

创建一棵空树

Definition at line 160 of file binaryTree.hh.

◆ binaryTree() [2/4]

template<typename T , typename Comparator >

Tree::binaryTree< T, Comparator >::binaryTree ( const value_type & x )

inlineexplicit

Construct a new binary Tree object.

创建一棵带有根节点的树

Parameters

x 根结点的数据

Definition at line 169 of file binaryTree.hh.

◆ binaryTree() [3/4]

template<typename T , typename Comparator >

Tree::binaryTree< T, Comparator >::binaryTree ( const binaryTree< T, Comparator > & rhs )

inline

Construct a new binary Tree object 拷贝构造函数

Parameters

rhs 源对象

Note: 参考C++设计模式——原型模式

Definition at line 177 of file binaryTree.hh.

◆ binaryTree() [4/4]

template<typename T , typename Comparator >

Tree::binaryTree< T, Comparator >::binaryTree ( binaryTree< T, Comparator > && rhs )

inline

Construct a new binary Tree object 移动构造函数

Parameters

rhs 源对象，右值

Definition at line 198 of file binaryTree.hh.

◆ ~binaryTree()

template<class T , typename Comparator >

Tree::binaryTree< T, Comparator >::~binaryTree

Destroy the binary Tree object.

Definition at line 654 of file binaryTree.hh.

Member Function Documentation

◆ clear() [1/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::clear

清空二叉树函数返回后，对象的成员root_将被置nullptr

Definition at line 648 of file binaryTree.hh.

References Tree::binaryTree< T, Comparator >::BinNode::data, Tree::binaryTree< T, Comparator >::BinNode::left, and Tree::binaryTree< T, Comparator >::BinNode::right.

◆ clear() [2/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::clear ( BinNode *& root )

private

清空以root为根结点的树，包括清除根结点

Parameters

root	指向目标树的根结点的指针

Note: 类的工具函数

函数执行完毕后，root将被置为nullptr

Definition at line 636 of file binaryTree.hh.

◆ clone()

template<class T , typename Comparator >

binaryTree< T, Comparator >::BinNode * Tree::binaryTree< T, Comparator >::clone ( BinNode * _root ) const

private

Internal method to clone subtree.

Parameters

_root 指向源二叉树的根结点的指针

Returns: BinNode* 指向新二叉树的根结点的指针

Definition at line 660 of file binaryTree.hh.

◆ CountDegreeTwo() [1/2]

template<typename T , typename Comparator >

size_type Tree::binaryTree< T, Comparator >::CountDegreeTwo ( ) const

inline

统计树中度为2的结点的个数

Definition at line 409 of file binaryTree.hh.

Referenced by print_test_result().

Here is the caller graph for this function:

◆ CountDegreeTwo() [2/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::CountDegreeTwo ( BinNode * _root ) const

private

统计树中度为2的结点的个数

Parameters

_root 指向树的根结点的指针

Note: 类的工具函数

Definition at line 1082 of file binaryTree.hh.

◆ createTree()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::createTree	(	const value_type &	flag = `value_type{}`,
		std::istream &	in = `std::cin`
	)

Create a Tree object.

Parameters

flag	"空结点"的特殊标记
in	输入流对象，可以是cin, 或者ifstream类的对象等

@ details 该方法首先调用clear()清空二叉树。然后要从输入流(标准/文件流)按层次顺序输入在建二叉树各结点的值，依此建立一棵二叉树
输入flag表示"空结点"

Warning: 本方法可能调用ifstream类从istream类继承的的sync()方法，which可能导致未定义行为。

Note: 要求对value_type类型重载了operator>>和operator<<

Definition at line 1324 of file binaryTree.hh.

Referenced by main().

Here is the caller graph for this function:

◆ delLeft()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::delLeft ( const value_type & x )

删除左subtree

Parameters

x	目标结点。以该结点的左child为根的树将被删除

Warning: 树中有data相同的结点时，该方法只能访问到前序序列中首次出现该数据的那个结点！

Definition at line 1031 of file binaryTree.hh.

Referenced by main().

Here is the caller graph for this function:

◆ delRight()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::delRight ( const value_type & x )

删除右subtree

Parameters

x	目标结点。以该节点的右child为根的树将被删除

Warning: 树中有data相同的结点时，该方法只能访问到前序序列中首次出现该数据的那个结点！

Definition at line 1041 of file binaryTree.hh.

Referenced by main().

Here is the caller graph for this function:

◆ empty()

template<class T , typename Comparator >

bool Tree::binaryTree< T, Comparator >::empty

判断二叉树是否为空树

Returns: true 是空树; false 非空树

Definition at line 621 of file binaryTree.hh.

◆ find()

template<class T , typename Comparator >

binaryTree< T, Comparator >::BinNode * Tree::binaryTree< T, Comparator >::find	(	const value_type &	x,
		BinNode *	root
	)		const

private

在以root为根的树中(前序)查找数据为x的结点，返回指向该结点的指针

Parameters

x	目标数据
root	目标二叉树的根结点的地址

Returns: BinNode* 指向查找到的数据为x的结点的指针。返回nullptr表示找不到。

Note: 类的工具函数

Warning: 树中有data相同的结点时，该方法只能找到前序序列中首次出现该数据的那个结点！

Definition at line 1015 of file binaryTree.hh.

◆ height() [1/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::height

返回二叉树的高度(递归版本)

The height of n_i is the length of the longest path from n_i to a leaf. Thus all leaves are at height 0.
The height of a tree is equal to the height of the root.

Returns: size_type 二叉树的高度

Definition at line 1195 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ height() [2/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::height ( BinNode * _root ) const

private

返回以指定结点为根结点的二叉树的高度(递归版本)

Parameters

_root 指向根结点的指针

Returns: value_type 以指定结点为根结点的二叉树的高度

Note: 类的工具函数

Definition at line 1093 of file binaryTree.hh.

◆ height_loop() [1/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::height_loop

返回二叉树的高度(非递归版本)

The height of n_i is the length of the longest path from n_i to a leaf. Thus all leaves are at height 0.
The height of a tree is equal to the height of the root.

Returns: size_type 二叉树的高度

Note: Reference https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

Definition at line 1201 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ height_loop() [2/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::height_loop ( BinNode * _root ) const

private

返回以指定结点为根结点的二叉树的高度(非递归版本)

Parameters

_root 指向根结点的指针

Returns: value_type 以指定结点为根结点的二叉树的高度

Note: 类的工具函数; Reference https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

Definition at line 1104 of file binaryTree.hh.

◆ inOrder() [1/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::inOrder	(	BinNode *	root,
		std::ostream &	out = `std::cout`
	)		const

private

中序遍历以root为根结点的树(递归版本)

Parameters

root	指向目标树的根结点的指针
out	输出流对象，可以是标准输出流或文件流等

Note: 类的工具函数

Definition at line 837 of file binaryTree.hh.

◆ inOrder() [2/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::inOrder ( std::ostream & out = std::cout ) const

中序遍历(递归版本)

中序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

Definition at line 906 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ inOrder_loop()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::inOrder_loop ( std::ostream & out = std::cout ) const

中序遍历(非递归版本)

中序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

Definition at line 848 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ is_equal_subtree()

template<class T , class U >

bool Tree::binaryTree< T, U >::is_equal_subtree	(	BinNode *	_root1,
		BinNode *	_root2
	)

staticprivate

判断两棵二叉树是否相同 "相同"是指：两棵树的形状及对应结点的值相等

Parameters

_root1	指向二叉树#1的根结点的指针
_root2	指向二叉树#2的根结点的指针

Returns: true 两棵树相同; false 两棵树不相同

Definition at line 684 of file binaryTree.hh.

◆ is_symmetrical_subtree()

template<class T , class U >

bool Tree::binaryTree< T, U >::is_symmetrical_subtree	(	BinNode *	root1,
		BinNode *	root2
	)

staticprivate

Internal method to 判断两棵二叉树是否相互对称

Parameters

root1	指向二叉树#1的根结点的指针
root2	指向二叉树#2的根结点的指针

Returns: true #1和#2相互对称; false otherwise

Definition at line 668 of file binaryTree.hh.

◆ is_symmetrical_tree()

template<typename T , typename Comparator >

static bool Tree::binaryTree< T, Comparator >::is_symmetrical_tree	(	const binaryTree< T, Comparator > &	lhs,
		const binaryTree< T, Comparator > &	rhs
	)

inlinestatic

判断两棵二叉树是否互为镜像两棵二叉树#1和#2互为镜像，如果二者皆为空树；或二者根结点的值相同，且#1的左、右子树与#2的右、左子树互为镜像

Parameters

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

Returns: true #1 symmetrical to #2; false otherwise

Definition at line 437 of file binaryTree.hh.

◆ isCompleteTree()

template<class T , typename Comparator >

bool Tree::binaryTree< T, Comparator >::isCompleteTree

返回是否完全二叉树

Returns: true 是完全二叉树; false 不是完全二叉树

至此，当前结点处理完毕。若当前结点有空孩子，则它是层序上的首个度非2结点。从而是完全二叉树iff.其后(不含)的结点全为叶子结点。

函数只可能在此if中返回

Definition at line 711 of file binaryTree.hh.

References Tree::binaryTree< T, Comparator >::BinNode::left, and Tree::binaryTree< T, Comparator >::BinNode::right.

Referenced by print_test_result().

Here is the caller graph for this function:

◆ isFullBinaryTree()

template<typename T , typename U >

bool Tree::binaryTree< T, U >::isFullBinaryTree

是否满二叉树

Note: 定义满二叉树：任意一层的结点数都达到了最大值。

Returns: true 是满二叉树; false 非满二叉树

Definition at line 699 of file binaryTree.hh.

References Queue::seqQueue< T >::push().

Referenced by print_test_result().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ lchild()

template<class T , typename Comparator >

binaryTree< T, Comparator >::value_type Tree::binaryTree< T, Comparator >::lchild	(	const value_type &	x,
		const value_type &	flag
	)		const

获得数据为x的结点的左child

Parameters

x	目标结点的数据
flag	无左child时返回的标记

Returns: value_type 左child的数据

Warning: 树中有data相同的结点时，该方法只能访问到前序序列中首次出现该数据的那个结点！

Definition at line 1051 of file binaryTree.hh.

◆ levelOrder()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::levelOrder ( std::ostream & out = std::cout ) const

层次遍历

层次打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

Definition at line 990 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ operator=() [1/2]

template<typename T , typename Comparator >

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

inline

移动赋值运算符

Parameters

rhs 源对象，右值

Returns: binaryTree& 目的对象的引用

Definition at line 206 of file binaryTree.hh.

◆ operator=() [2/2]

template<typename T , typename Comparator >

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

inline

赋值运算符重载

Parameters

rhs 源对象

Returns: binaryTree& 目的对象的引用

Definition at line 185 of file binaryTree.hh.

◆ parent()

template<typename T , typename Comparator >

value_type Tree::binaryTree< T, Comparator >::parent	(	value_type	x,
		const value_type &	flag
	)		const

inline

返回数据为x的结点的parent结点

Parameters

x	目标结点的数据
flag	parent不存在时返回的特殊标记

Returns: value_type parent结点的数据

Bug:: 二叉链表不允许访问结点的parent，本函数恒返回flag

Definition at line 358 of file binaryTree.hh.

◆ postOrder() [1/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::postOrder	(	BinNode *	root,
		std::ostream &	out = `std::cout`
	)		const

private

后序遍历以root为根结点的树(递归版本)

Parameters

root	指向目标树的根结点的指针
out	输出流对象，可以是标准输出流或文件流等

Note: 类的工具函数

Definition at line 912 of file binaryTree.hh.

◆ postOrder() [2/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::postOrder ( std::ostream & out = std::cout ) const

后序遍历(递归版本)

后序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

Definition at line 984 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ postOrder_loop()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::postOrder_loop ( std::ostream & out = std::cout ) const

后序遍历(非递归版本)

后序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

连续递归调用，归入一个stage，直接反序进栈即可

Definition at line 923 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ preOrder() [1/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::preOrder	(	BinNode *	root,
		std::ostream &	out = `std::cout`
	)		const

private

前序遍历以root为根结点的树(递归版本)

Parameters

root	指向目标树的根结点的指针
out	输出流对象，可以是标准输出流或文件流等

Note: 类的工具函数

Definition at line 758 of file binaryTree.hh.

◆ preOrder() [2/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::preOrder ( std::ostream & out = std::cout ) const

前序遍历(递归版本)

前序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

Definition at line 831 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ preOrder_loop()

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::preOrder_loop ( std::ostream & out = std::cout ) const

前序遍历(非递归版本)

前序打印二叉树各结点的数据到标准输出设备

Parameters

out	输出流对象，可以是标准输出流或文件流等

引用类型的形参不需要记录。只需记录BinNode* _root。首次调用时，实参就是对象的根结点root_；该细节应被封装，故提供给用户的函数形参表不设_root。递归版本是有限次tail recursion，不必记录stage。

首次调用时，实参就是对象的根结点root_；该细节应被封装，故提供给用户的函数形参表不设_root。

函数体内的递归调用返回后，唯一的行为是新的递归调用，故不必保存断点(分stage)，直接将所有tail recursions按反序进栈即可。注意到若某次递归调用的实参为0将导致空操作，所以若为空则不必进栈 (导致两次访问，可选)。

Definition at line 769 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ rchild()

template<class T , typename Comparator >

binaryTree< T, Comparator >::value_type Tree::binaryTree< T, Comparator >::rchild	(	const value_type &	x,
		const value_type &	flag
	)		const

获得数据为x的结点的右child

Parameters

x	目标结点的数据
flag	无右child时返回的标记

Returns: value_type 右child的数据

Warning: 树中有data相同的结点时，该方法只能访问到前序序列中首次出现该数据的那个结点！

Definition at line 1061 of file binaryTree.hh.

Referenced by Tree::printBinaryTree().

Here is the caller graph for this function:

◆ root()

template<class T , typename Comparator >

binaryTree< T, Comparator >::value_type Tree::binaryTree< T, Comparator >::root ( const value_type & flag ) const

返回根结点的数据

Parameters

flag	为空树时返回的特殊标记

Returns: value_type 根结点的数据

Definition at line 627 of file binaryTree.hh.

◆ size() [1/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::size

返回二叉树的结点数(递归版本)

Returns: size_type 二叉树的结点数

Definition at line 1312 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ size() [2/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::size ( BinNode * _root ) const

private

返回以指定结点为根结点的二叉树的规模(递归版本)

Parameters

_root 指向根结点的指针

Returns: value_type 以指定结点为根结点的二叉树的规模

Note: 类的工具函数

Definition at line 1207 of file binaryTree.hh.

◆ size_loop() [1/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::size_loop

返回二叉树的结点数(非递归版本)

Returns: size_type 二叉树的结点数

Note: Reference https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

Definition at line 1318 of file binaryTree.hh.

Referenced by print_test_result(), and Tree::print_test_result().

Here is the caller graph for this function:

◆ size_loop() [2/2]

template<class T , typename Comparator >

binaryTree< T, Comparator >::size_type Tree::binaryTree< T, Comparator >::size_loop ( BinNode * _root ) const

private

返回以指定结点为根结点的二叉树的规模(非递归版本)

Parameters

_root 指向根结点的指针

Returns: value_type 以指定结点为根结点的二叉树的规模

Note: 类的工具函数

Reference

https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

Definition at line 1220 of file binaryTree.hh.

◆ swaplr() [1/2]

template<typename T , typename Comparator >

void Tree::binaryTree< T, Comparator >::swaplr ( )

inline

交换左右子树

Parameters

_root 指向树的根结点的指针

Warning: 不允许用户指定参数

Definition at line 404 of file binaryTree.hh.

Referenced by main().

Here is the caller graph for this function:

◆ swaplr() [2/2]

template<class T , typename Comparator >

void Tree::binaryTree< T, Comparator >::swaplr ( BinNode * _root )

private

交换左右子树

Parameters

_root 指向树的根结点的指针

Note: 类的工具函数

Definition at line 1071 of file binaryTree.hh.

◆ value_type_equal()

template<typename T , typename Comparator >

static bool Tree::binaryTree< T, Comparator >::value_type_equal	(	const value_type &	lhs,
		const value_type &	rhs
	)

inlinestaticprivate

比较value_type类型对象的大小。

Parameters

lhs	左运算数
rhs	右运算数

Returns: true lhs == rhs; false lhs != rhs

Definition at line 538 of file binaryTree.hh.

◆ value_type_less()

template<typename T , typename Comparator >

static bool Tree::binaryTree< T, Comparator >::value_type_less	(	const value_type &	lhs,
		const value_type &	rhs
	)

inlinestaticprivate

比较value_type类型对象的大小。

Parameters

lhs	左运算数
rhs	右运算数

Returns: true lhs < rhs; false lhs >= rhs

Definition at line 528 of file binaryTree.hh.

◆ value_type_less_equal()

template<typename T , typename Comparator >

static bool Tree::binaryTree< T, Comparator >::value_type_less_equal	(	const value_type &	lhs,
		const value_type &	rhs
	)

inlinestaticprivate

比较value_type类型对象的大小。

Parameters

lhs	左运算数
rhs	右运算数

Returns: true lhs <= rhs; false lhs > rhs

Definition at line 548 of file binaryTree.hh.

Friends And Related Function Documentation

◆ operator==

template<typename T , typename Comparator >

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

friend

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

不能在此声明下述友元(invalid use of incomplete type)，原因：类的内部类型value_type未声明。只需把友元声明置于typedef后即可

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.

◆ printBinaryTree

template<typename T , typename Comparator >

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

friend

Member Data Documentation

◆ const_reference

template<typename T , typename Comparator >

const typedef value_type& Tree::binaryTree< T, Comparator >::const_reference

数据的常量引用

Definition at line 110 of file binaryTree.hh.

◆ is_less_than_

template<class T , typename Comparator >

Comparator Tree::binaryTree< T, Comparator >::is_less_than_ = Comparator{}

staticprivate

比较器(function object)

Definition at line 518 of file binaryTree.hh.

◆ root_

template<typename T , typename Comparator >

BinNode* Tree::binaryTree< T, Comparator >::root_

private

二叉树的根结点

Definition at line 151 of file binaryTree.hh.

The documentation for this class was generated from the following file:

include/binaryTree.hh

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

template<typename T, typename Comparator> class Tree::binaryTree< T, Comparator >

Member Typedef Documentation

◆ reference

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ binaryTree() [1/4]

◆ binaryTree() [2/4]

◆ binaryTree() [3/4]

◆ binaryTree() [4/4]

◆ ~binaryTree()

Member Function Documentation

◆ clear() [1/2]

◆ clear() [2/2]

◆ clone()

◆ CountDegreeTwo() [1/2]

◆ CountDegreeTwo() [2/2]

◆ createTree()

◆ delLeft()

◆ delRight()

◆ empty()

◆ find()

◆ height() [1/2]

◆ height() [2/2]

◆ height_loop() [1/2]

◆ height_loop() [2/2]

◆ inOrder() [1/2]

◆ inOrder() [2/2]

◆ inOrder_loop()

◆ is_equal_subtree()

◆ is_symmetrical_subtree()

◆ is_symmetrical_tree()

◆ isCompleteTree()

◆ isFullBinaryTree()

◆ lchild()

◆ levelOrder()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ postOrder() [1/2]

◆ postOrder() [2/2]

◆ postOrder_loop()

◆ preOrder() [1/2]

◆ preOrder() [2/2]

◆ preOrder_loop()

◆ rchild()

◆ root()

◆ size() [1/2]

◆ size() [2/2]

◆ size_loop() [1/2]

◆ size_loop() [2/2]

Reference

◆ swaplr() [1/2]

◆ swaplr() [2/2]

◆ value_type_equal()

◆ value_type_less()

◆ value_type_less_equal()

Friends And Related Function Documentation

◆ operator==

◆ printBinaryTree

Member Data Documentation

◆ const_reference

◆ is_less_than_

◆ root_

template<typename T, typename Comparator>
class Tree::binaryTree< T, Comparator >