二叉树(二)——二叉搜索树及C++实现

什么是二叉搜索树

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

二叉树节点类

本类是构成二叉树的节点类。包括三个指针,分别指向双亲节点、左孩子节点和右孩子节点,还有一个变量存储数据。如果二叉树插入和删除操作很少,可以存储高度变量,因为插入操作和删除操作需要更新一系列节点的高度值。红黑颜色是在红黑树中使用的。本类同时重载了比较、赋值和输出运算符。

typedef enum {
	RB_RED,
	RB_BLACK
}RBColor;

template <typename T>
class BinNode {
	// 知识点一:
	// <<和>>操作符重载,不能以成员函数的形式重载,必须以独立函数的形式重载,并声明为类的友元。
	// 知识点二:
	// 如果形参中含有模板类,需要在声明与定义的地方加上对应模板参数的声明,比如
	// template<typename T> 或 template<T>.
	template<typename T>
	friend std::ostream& operator<<(std::ostream& os, BinNode<T> const& bn); // 声明为类的友元
	public:
		// data
		BinNode<T>* parent;
		BinNode<T>* left;
		BinNode<T>* right;
		T data;
		unsigned int height;
		RBColor color; // red-black tree

		// constructor
		BinNode():parent(nullptr), left(nullptr), right (nullptr), height(0), data(0), color(RB_RED) {}
		BinNode(const T d, BinNode<T>* p = nullptr, BinNode<T>* l = nullptr, BinNode<T>* r = nullptr, unsigned int h = 0, RBColor c = RB_RED) : data(d), parent(p), left(l), right(r), height(h), color(c) {}
		BinNode(const BinNode<T>& bn) : parent(bn.parent), left(bn.left), right(bn.right), data(bn.data), height(bn.height) {};

		// operator
		bool operator<(BinNode<T> const& bn) { return data < bn.data; }
		bool operator==(BinNode<T> const& bn) { return data == bn.data; }
		bool operator>(BinNode<T> const& bn) { return data > bn.data; }
		BinNode<T>& operator=(BinNode<T> const& bn);
};

template <typename T> 
BinNode<T>& BinNode<T>::operator=(BinNode<T> const& bn) {
	this->parent = bn.parent;
	this->left = bn.left;
	this->right = bn.right;
	this->color = bn.color;
	this->data = bn.data;
	return *this;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, BinNode<T> const& bn) {
	os << "parent:\t" << bn.parent << std::endl;
	os << "left child:\t" << bn.left << std::endl;
	os << "right child:\t" << bn.right << std::endl;
	os << "data:\t" << bn.data << std::endl << std::endl;
	return os;
}

二叉树模板

template <typename T>
class BinarySearchTree {
	/*
	 * 转换成双向链表没有实现
	 */
public:
	BinNode<T>* root;

	// constructor
	BinarySearchTree() : root(nullptr) {}     // 默认构造函数
	BinarySearchTree(const std::vector<T>& v);      // 构造函数
	// 根据前序遍历序列和中序遍历序列构建二叉树
	BinarySearchTree(std::vector<T>& inOrder, std::vector<T>& preOrder);
	BinarySearchTree(const BinarySearchTree<T>& t); // 拷贝构造函数

	// destructor
	~BinarySearchTree(); // 析构函数

	// interface
	// nodes number
	std::size_t nodeNumber(const BinNode<T>* node); // recusively
	std::size_t nodeNumber(); // non-recusively
	// leaf number
	std::size_t leafNumber(const BinNode<T>* node); // recusively
	std::size_t leafNumber(); // non-recusively
	// depth
	std::size_t depth(const BinNode<T>* node); // recusively
	std::size_t depth(); // non-recusively
	// transplant 将以v为根的子树替换以u为根的子树。注意,是替换而不是互换。(删除节点时用到)
	// 注意:transplant并没有处理v.left和v.right的更新,这些更新都由transplant的调用者来负责
	void transplant(BinNode<T>* u, BinNode<T>* v);
	// insert & delete
	BinNode<T>* insert(T const& e);
	void remove(BinNode<T>* node);
	// copy
	BinNode<T>* copy(BinNode<T> const* node);
	// recusively tree search 深度优先遍历的三种递归实现方式
	void inOrderTreeSearch(const BinNode<T>* root);
	void preOrderTreeSearch(const BinNode<T>* root);
	void postOrderTreeSearch(const BinNode<T>* root);
	// non-recusively tree search 深度优先遍历的三种非递归实现方式
	void inOrderTreeSearch();
	void preOrderTreeSearch();
	void postOrderTreeSearch();
	// Hierarchical traversal 层次遍历(广度优先遍历)
	void hierarchTraverse();
	// search
	BinNode<T>* search(const BinNode<T>* node, T const& e); // recursively
	BinNode<T>* search(T const& e); // non-recursively
	// 求二叉树第K层的节点个数
	std::size_t getKLevelNum(const BinNode<T>* node, const std::size_t k);
	std::size_t getKLevelNum(const std::size_t k);
	// maximum & minimum
	BinNode<T>* max() { return max(root); }
	BinNode<T>* min() { return min(root); }
	BinNode<T>* max(BinNode<T>* node); // 参数不能写成const的形式
	BinNode<T>* min(BinNode<T>* node); // 参数不能写成const的形式
	// successor & predecessor
	BinNode<T>* successor(const BinNode<T>* node);
	BinNode<T>* predecessor(const BinNode<T>* node);
	// mirror
	void mirror(BinNode<T>* node); // recursively
	void mirror(); // non-recursively
	// 判断两棵二叉树是否结构相同
	bool structureCmp(BinNode<T> const* node1, BinNode<T> const* node2); // recursively
	bool structureCmp(BinarySearchTree<T> const& tree); // non-recursively
	// operator = 
	BinarySearchTree<T>& operator=(BinarySearchTree<T> const& bst);

private:
	BinNode<T>* constructCore(typename std::vector<T>::iterator ib, typename std::vector<T>::iterator ie, typename std::vector<T>::iterator pb, typename std::vector<T>::iterator pe);
};

构造函数

由vector创建二叉搜索树

template <typename T>
BinarySearchTree<T>::BinarySearchTree(const std::vector<T>& v)
{
	for (auto e : v)
	{
		root = insert(e);
	}
}

里面的insert函数会在本博客的后面讲解。

由前序遍历序列和中序遍历序列重建二叉树

下面的关键部分是constructCore函数。在函数constructCore中,我们先根据前序遍历序列的第一个数字创建根节点,接下来在中序遍历序列中找到根节点的位置,这样就能确定左右子树节点的数量。在前序遍历序列和中序遍历序列中划分左右子树节点的值之后,我们就可以递归地调用函数constructCore去分别构建它的左右子树。注意,函数constructCore最后一定要返回节点指针node,否则,最后构建的二叉树将是一棵空树,并且在构建二叉树构成中new出来的节点不能被释放,造成内存泄露。

template <typename T>
BinarySearchTree<T>::BinarySearchTree(std::vector<T>& inOrder, std::vector<T>& preOrder)
{
	root = constructCore(inOrder.begin(), inOrder.end(), preOrder.begin(), preOrder.end());
}

template <typename T>
BinNode<T>* BinarySearchTree<T>::constructCore(typename std::vector<T>::iterator ib, typename std::vector<T>::iterator ie, typename std::vector<T>::iterator pb, typename std::vector<T>::iterator pe)
{
	T rootValue = *pb;
	BinNode<T>* node = new BinNode<T>(rootValue);
	if (pb == pe - 1)
	{
		if (ib == ie - 1 && *pb == *ib)
			return node;
		else
			throw std::exception("Invalid input.");
	}

	// 从中序遍历序列中找到根节点
	typename std::vector<T>::iterator rootInorder = ib;
	while (rootInorder < ie && *rootInorder != rootValue)
	{
		++rootInorder;
	}
	if (rootInorder == ie)
		throw std::exception("Invalid input.");
	std::size_t leftLength = rootInorder - ib;
	typename std::vector<T>::iterator lpe = pb + leftLength + 1;
	if (leftLength > 0)
	{
		// 构建左子树
		node->left = constructCore(ib, rootInorder, pb + 1, lpe);
		node->left->parent = node;
	}
	if (leftLength < pe - pb - 1)
	{
		// 构建右子树
		node->right = constructCore(rootInorder + 1, ie, lpe, pe);
		node->right->parent = node;
	}
	return node; // 最后一定要返回节点指针node,否则,最后构建的二叉树将是一棵空树,并且在构建二叉树构成中new出来的节点不能被释放,造成内存泄露。
}

析构函数

在析构函数中调用了remove函数,该函数将在本博文的后面讲解。

template <typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
	while (root != nullptr)
	{
		remove(root);
	}
}

求二叉树中的节点个数

递归实现

递归实现的思想是:二叉树中节点的个数等于左子树节点的个数加右子树节点的个数,最后再加上根节点的个数(1)。注意,最后一定要加上根节点的个数,否则最后的结果是0.

template <typename T>
std::size_t BinarySearchTree<T>::nodeNumber(const BinNode<T>* node)
{
	if (node == nullptr)
		return 0;
	return nodeNumber(node->left) + nodeNumber(node->right) + 1;
}

非递归实现

非递归实现的方式可以借助栈这种数据结构来实现。当借助栈这种数据结构实现的时候,可以直接将递归实现的代码翻译成非递归实现的代码。其思想为:首先观察递归函数的函数体一共递归调用了几次,假设为N次,再观察最后一次递归调用之后,是否访问过node变量,如果有,则M=N+1,否则M=N。最后,将node变量压入栈的次数为M-1次。在本例中,M=2,故将node 变量压入栈的次数为1次。在下面代码中,3处if语句块中都只将node压入栈一次。其他例子请看本博文后面的前序遍历、中序遍历、后序遍历以及其他例子。

template <typename T>
std::size_t BinarySearchTree<T>::nodeNumber()
{
	std::stack<BinNode<T>*> stk;
	BinNode<T>* temp;
	std::size_t num = 0;
	if (root != nullptr)
		stk.push(root);
	while (!stk.empty())
	{
		temp = stk.top();
		stk.pop();
		num += 1;
		if (temp->left != nullptr)
			stk.push(temp->left);
		if (temp->right != nullptr)
			stk.push(temp->right);
	}
	return num;
}

 

求二叉树中叶子节点的个数

递归求解

当某个节点为空的时候,其叶子节点的个数为0;当某个节点非空,并且没有左右孩子的时候,该节点为叶子节点;否则叶子节点的个数等于左子树中叶子节点的个数加上右子树叶子节点的个数。

template <typename T>
std::size_t BinarySearchTree<T>::leafNumber(const BinNode<T>* node)
{
	if (node == nullptr)
		return 0;
	else if (node->left == nullptr && node->right == nullptr)
		return 1;
	return leafNumber(node->left) + leafNumber(node->right);
}

非递归求解

使用层次遍历思想求解

本例使用了层次遍历(广度优先遍历)的思想求解叶子节点的个数。

// 用层次遍历的思想求解
template <typename T>
std::size_t BinarySearchTree<T>::leafNumber()
{
	std::queue<BinNode<T>*> que;
	BinNode<T>* temp = nullptr;
	std::size_t num = 0;
	if (root != nullptr)
		que.push(root);
	while (!que.empty())
	{
		temp = que.front();
		que.pop();
		if (temp->left == nullptr && temp->right == nullptr)
		{
			num += 1;
		}
		if (temp->left != nullptr)
		{
			que.push(temp->left);
		}
		if (temp->right != nullptr)
		{
			que.push(temp->right);
		}
	}
	return num;
}

使用深度优先遍历思想求解

本例使用了深度优先遍历的思想求解叶子节点的个数。

template <typename T>
std::size_t BinarySearchTree<T>::leafNumber()
{
	std::stack<BinNode<T>*> stk;
	BinNode<T>* temp;
	std::size_t num = 0;
	if (root != nullptr)
	{
		stk.push(root);
	}
	while (!stk.empty())
	{
		temp = stk.top();
		stk.pop();
		if (temp->left == nullptr && temp->right == nullptr)
			num += 1;
		if (temp->left != nullptr)
			stk.push(temp->left);
		if (temp->right != nullptr)
			stk.push(temp->right);
	}
	return num;
}

求一个二叉树的深度

递归求解

如果节点为空节点,那么深度为0;否则,深度等于左子树深度和右子树深度最大者加1。

注意:如果规定根节点的深度为0,那么不需要加1;如果规定根节点的深度为1,那么需要加1。本博文规定根节点的深度为1,故在return的时候加了一个1。

template <typename T>
std::size_t BinarySearchTree<T>::depth(const BinNode<T>* node)
{
	if (node == nullptr)
		return 0;
	return std::max(depth(node->left), depth(node->right)) + 1;
}

非递归求解

本非递归思想求解的过程中使用了双栈,即一个栈用来存储二叉树中的节点,另一个栈用来存储与节点所对应的访问次数。之所以这么实现的原因是因为:

必须在访问某个节点的左子树和右子树的所有节点之后才能从栈中弹出该节点。反应这一思想的代码请看下面代码中的注释。

template <typename T>
std::size_t BinarySearchTree<T>::depth()
{
	std::stack<BinNode<T>*> stk;
	std::stack<std::size_t> stk_num;
	BinNode<T>* temp;
	std::size_t dep = 0;
	if (root != nullptr)
	{
		stk.push(root);
		stk_num.push(2);
	}
	while (!stk.empty())
	{
		if (dep < stk.size())
			dep = stk.size();
		std::size_t s = stk_num.top();
		stk_num.pop();
		temp = stk.top();
		if (s == 1) // 表示此时该访问节点的右子树
		{
			stk_num.push(s - 1);
			if (temp->right != nullptr)
			{
				stk.push(temp->right); 
				stk_num.push(2);
			}
		}
		else if (s == 2) // 表示此时该访问节点的左子树
		{
			stk_num.push(s - 1);
			if (temp->left != nullptr)
			{
				stk.push(temp->left);
				stk_num.push(2);
			}
		}
		else // s == 0 // 表示此时该节点的左右子树都已经访问过了
		{
			stk.pop(); // 在访问某个节点的左子树和右子树的所有节点之后才能从栈中弹出该节点
		}
	}
	return dep;
}

中序遍历

递归实现

template <typename T>
void BinarySearchTree<T>::inOrderTreeSearch(const BinNode<T>* root)
{
	if (root != nullptr)
	{
		inOrderTreeSearch(root->left);
		std::cout << root->data << "\t";
		inOrderTreeSearch(root->right);
	}
}

非递归实现

非递归实现的过程中使用了栈这一数据结构。

template <typename T>
void BinarySearchTree<T>::inOrderTreeSearch()
{
	std::stack<BinNode<T>*> stk;
	BinNode<T>* p = root;
	while (!stk.empty() || p != nullptr)
	{
		if (p != nullptr)
		{
			stk.push(p);
			p = p->left;
		}
		else
		{
			BinNode<T>* tmp = stk.top();
			stk.pop();
			std::cout << tmp->data << "\t";
			p = tmp->right;
		}
	}
}

前序遍历

递归实现

template <typename T>
void BinarySearchTree<T>::preOrderTreeSearch(const BinNode<T>* root)
{
	if (root != nullptr)
	{
		std::cout << root->data << "\t";
		preOrderTreeSearch(root->left);
		preOrderTreeSearch(root->right);
	}
}

非递归实现

template <typename T>
void BinarySearchTree<T>::preOrderTreeSearch()
{
	std::stack<BinNode<T>*> stk;
	BinNode<T>* p = root;
	while (!stk.empty() || p != nullptr)
	{
		if (p != nullptr)
		{
			std::cout << p->data << "\t";
			stk.push(p);
			p = p->left;
		}
		else
		{
			BinNode<T>* tmp = stk.top();
			stk.pop();
			p = tmp->right;
		}
	}
}

后序遍历

递归实现

template <typename T>
void BinarySearchTree<T>::postOrderTreeSearch(const BinNode<T>* root)
{
	if (root != nullptr)
	{
		postOrderTreeSearch(root->left);
		postOrderTreeSearch(root->right);
		std::cout << root->data << "\t";
	}
}

非递归实现

template <typename T>
void BinarySearchTree<T>::postOrderTreeSearch()
{
	std::stack<BinNode<T>*> stk;
	BinNode<T>* p = root;
	while (!stk.empty() || p != nullptr)
	{
		if (p != nullptr)
		{
			stk.push(p);
			stk.push(p);
			p = p->left;
		}
		else
		{
			BinNode<T>* tmp = stk.top();
			stk.pop();
			if (stk.size() == 0 || tmp != stk.top())
			{
				std::cout << tmp->data << "\t";
				p = nullptr;
			}
			else
			{
				p = tmp->right;
			}
		}
	}
}

广度优先遍历/层次遍历

本函数使用了队列这一数据结构。

template <typename T>
void BinarySearchTree<T>::hierarchTraverse()
{
	std::queue<BinNode<T>*> que;
	if (root != nullptr)
	{
		que.push(root);
		while (!que.empty())
		{
			auto tmp = que.front();
			que.pop();
			std::cout << tmp->data << "\t";
			if (tmp->left != nullptr)
			{
				que.push(tmp->left);
			}
			if (tmp->right != nullptr)
			{
				que.push(tmp->right);
			}
		}
	}
}

插入节点

本函数的作用是将数据插入到二叉树中,并维持二叉搜索树的特征。需要注意的是,插入的节点总是以叶子节点的形式插入。明白了这一点,理解这个函数就很容易了。

// 插入总是以叶子节点的形式插入
template <typename T>
BinNode<T>* BinarySearchTree<T>::insert(T const& e)
{
	BinNode<T>* y = nullptr;
	BinNode<T>* x = root;
	while (x != nullptr)
	{
		y = x;
		if (e < x->data)
		{
			x = x->left;
		}
		else
		{
			x = x->right;
		}
	}
	BinNode<T>* z = new BinNode<T>(e, y);
	if (y == nullptr)
	{
		root = z;
	}
	else if (z->data < y->data)
	{
		y->left = z;
	}
	else
	{
		y->right = z;
	}
	return root;
}

子树替代

本函数的作用是将以v为根节点的子树替换以u为根节点的子树。这个函数将在remove函数中被调用。

注意:本函数仅更新了v节点中的父节点指针,没有更新v节点的左右孩子指针。这两个指针需要由调用者负责更新。

template <typename T>
void BinarySearchTree<T>::transplant(BinNode<T>* u, BinNode<T>* v)
{
	if (u->parent == nullptr)
	{
		root = v;
	}
	else if (u == u->parent->left)
	{
		u->parent->left = v;
	}
	else
	{
		u->parent->right = v;
	}
	if (v != nullptr)
	{
		v->parent = u->parent;
	}
}

删除节点

和插入节点相比,删除节点比较复杂,在此,将《算法导论》中相关的内容摘录如下:

template <typename T>
void BinarySearchTree<T>::remove(BinNode<T>* node)
{
	BinNode<T>* y;
	if (node != nullptr) // 因为本成员函数允许传入空指针,因此delete的时候需要判断一下是否是空指针
	{ 
		if (node->left == nullptr)
		{
			transplant(node, node->right);
		}
		else if (node->right == nullptr)
		{
			transplant(node, node->left);
		}
		else // 有两个孩子
		{
			y = min(node->right);
			if (y->parent != node)
			{
				transplant(y, y->right);
				y->right = node->right;
				y->right->parent = y;
			}
			transplant(node, y);
			y->left = node->left;
			y->left->parent = y;
		}
		delete node;
	}
}

复制一个树

该函数的作用是将一个以node为根节点的树创建一棵一模一样的树。该函数可在复制构造函数和赋值运算符重载函数中调用。

template <typename T>
BinNode<T>* BinarySearchTree<T>::copy(BinNode<T> const* node)
{
	if (node == nullptr)
		return nullptr;
	// 切记,不能使用 
	// BinNode<T> newNode(node->data);
	// BinNode<T>* pNewNode = &newNode;
	// 因为递归回来之后,pNewNode在同一个递归内部指向的是同一个地址
	// 也就是说,某个节点的左右孩子是一样的
	BinNode<T>* pNewNode = new BinNode<T>(node->data);
	pNewNode->left = copy(node->left);
	if (pNewNode->left != nullptr)
	{
		pNewNode->left->parent = pNewNode;
	}
	pNewNode->right = copy(node->right);
	if (pNewNode->right != nullptr)
	{
		pNewNode->right->parent = pNewNode;
	}
	return pNewNode;
}

查找

递归实现

template<typename T>
BinNode<T>* BinarySearchTree<T>::search(const BinNode<T>* node, T const& e)
{
	if (node == nullptr || node->data == e)
		return node;
	if (e < node->data)
	{
		search(node->left, e);
	}
	else
	{
		search(node->right, e)
	}
}

非递归实现

template<typename T>
BinNode<T>* BinarySearchTree<T>::search(T const& e)
{
	BinNode<T>* p = root;
	while (p != nullptr && p->data != e)
	{
		if (e < p->data)
		{
			p = p->left;
		}
		else
		{
			p = p->right;
		}
	}
	return p;
}

最大值

template <typename T>
BinNode<T>* BinarySearchTree<T>::max(BinNode<T>* node)
{
	while (node->right != nullptr)
	{
		node = node->right;
	}
	return node;
}

最小值

template <typename T>
BinNode<T>* BinarySearchTree<T>::min(BinNode<T>* node)
{
	while (node->left != nullptr)
	{
		node = node->left;
	}
	return node;
}

后继

// 从该节点往上找,一直找到某个节点,该节点是其父节点的左孩子。
// 如果有后继,返回对应节点的指针,否则返回nullptr
template <typename T>
BinNode<T>* BinarySearchTree<T>::successor(const BinNode<T>* node)
{
	BinNode<T>* p;
	if (node->right != nullptr)
	{
		return min(node->right);
	}
	p = node->parent;
	while (p != nullptr && node == p->right)
	{
		node = p;
		p = p->parent;
	}
	return p;

}

前驱

// 从该节点往上找,一直找到某个节点,该节点是其父节点的右孩子。
template <typename T>
BinNode<T>* BinarySearchTree<T>::predecessor(const BinNode<T>* node)
{
	BinNode<T>* p;
	if (node->left != nullptr)
	{
		return max(node->left);
	}
	p = node->parent;
	while (p != nullptr && node == p->left)
	{
		node = p;
		p = p->parent;
	}
	return p;
}

赋值运算符重载

template <typename T>
BinarySearchTree<T>& BinarySearchTree<T>::operator=(BinarySearchTree<T> const& bst)
{
	if (bst.root != root)
		root = copy(bst.root);
	return *this;
}

镜像

递归实现

template <typename T>
void BinarySearchTree<T>::mirror(BinNode<T>* node)
{
	if (node == nullptr)
		return;
	BinNode<T>* temp = node->left;
	node->left = node->right;
	node->right = temp;
	
	mirror(node->left);
	mirror(node->right);
}

非递归实现

template <typename T>
void BinarySearchTree<T>::mirror()
{
	BinNode<T>* temp;
	BinNode<T>* temp2;
	std::stack < BinNode<T>*> stk;
	if (root != nullptr)
	{
		stk.push(root);
	}
	while (!stk.empty())
	{
		temp = stk.top();
		stk.pop();
		temp2 = temp->left;
		temp->left = temp->right;
		temp->right = temp2;
		if (temp->left != nullptr)
		{
			stk.push(temp->left);
		}
		if (temp->right != nullptr)
		{
			stk.push(temp->right);
		}
	}
}

计算第K层节点的个数

递归实现

template <typename T>
std::size_t BinarySearchTree<T>::getKLevelNum(const BinNode<T>* node, const std::size_t k)
{
	if (node == nullptr)
		return 0;
	if (k == 1)
		return 1;
	return getKLevelNum(node->left, k - 1) + getKLevelNum(node->right, k - 1);
}

非递归实现

template <typename T>
std::size_t BinarySearchTree<T>::getKLevelNum(const std::size_t k)
{
	std::queue<BinNode<T>*> que;
	std::queue<std::size_t> level;
	BinNode<T>* temp;
	std::size_t num = 0;
	std::size_t curLev = 1; // 当前的深度(规定根节点的深度为1)
	if (root != nullptr)
	{
		que.push(root);
		level.push(curLev);
	}
	while (!que.empty())
	{
		temp = que.front();
		que.pop();
		curLev = level.front();
		if (curLev == k)
		{
			num = level.size();
			break;
		}
		level.pop();
		if (temp->left != nullptr)
		{
			que.push(temp->left);
			level.push(curLev + 1);
		}
		if (temp->right != nullptr)
		{
			que.push(temp->right);
			level.push(curLev + 1);
		}
	}
	return num;
}

判断两棵树的结构是否相同

递归实现

// 递归判断两个树的结构是否相同
template <typename T>
bool BinarySearchTree<T>::structureCmp(BinNode<T> const* node1, BinNode<T> const* node2)
{
	if (node1 == nullptr && node2 == nullptr)
		return true;
	if ((node1 != nullptr && node2 == nullptr) || (node1 == nullptr && node2 != nullptr))
		return false;
	bool leftResult = structureCmp(node1->left, node2->left);
	bool rightResult = structureCmp(node1->right, node2->right);
	return leftResult && rightResult;
}

非递归实现

// 非递归判断两个树的结构是否相同
template <typename T>
bool BinarySearchTree<T>::structureCmp(BinarySearchTree<T> const& tree)
{
	std::stack<BinNode<T>*> stk1;
	std::stack<BinNode<T>*> stk2;
	BinNode<T>* temp1;
	BinNode<T>* temp2;
	bool leftResult;
	bool rightResult;
	if (root == tree.root) // 同一棵树比较
		return true;
	if (root != nullptr && tree.root != nullptr)
	{
		stk1.push(root);
		stk2.push(tree.root);
	}
	else if (root == nullptr && tree.root == nullptr)
		return true;
	else
		return false;
	while (!stk1.empty() && !stk2.empty())
	{
		temp1 = stk1.top();
		stk1.pop();
		temp2 = stk2.top();
		stk2.pop();
		if ((temp1->left == nullptr && temp2->left == nullptr) || (temp1->left && temp2->left))
			leftResult = true;
		if ((temp1->right == nullptr && temp2->right == nullptr) || (temp1->right && temp2->right))
			rightResult = true;
		if (!(leftResult && rightResult))
			return false;
		if (temp1->left != nullptr)
			stk1.push(temp1->left);
		if (temp1->right != nullptr)
			stk1.push(temp1->right);
		if (temp2->left != nullptr)
			stk2.push(temp2->left);
		if (temp2->right != nullptr)
			stk2.push(temp2->right);
	}
	if (!(stk1.empty() && stk2.empty()))
		return false;
	return true;
}

源代码下载链接:点击进入下载博文页面。注:下载博文页面已被加密。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

2 × 4 =

13 + = 22