数据结构之二叉树（C++）

二叉树

// 节点类模板
template<class T>
class LinkedNode
{
	template<class T>
	friend class LinkedBinTree;
public:
	LinkedNode()
	{
		m_pLeftchild = NULL;
		m_pRightchild = NULL;
	}
	LinkedNode(const T& x)
	{
		m_pLeftchild = m_pRightchild = NULL;
		m_data = x;
	}

private:
	T m_data;
	LinkedNode<T>* m_pLeftchild, * m_pRightchild;
};

// 二叉链表
template<class T>
class LinkedBinTree
{
public:
	LinkedBinTree();
	~LinkedBinTree();
	bool IsEmpty();
	LinkedNode<T>* CreatRoot(const T& x);	// 创建根节点
	void Clear();							// 清空树
	LinkedNode<T>* GetRoot();
	// 指定节点作为左孩子插入
	LinkedNode<T>* InsertLeftChild(LinkedNode<T>* pNode, const T& x);	// pNode是节点地址
	// 指定节点作为右孩子插入
	LinkedNode<T>* InsertRightChild(LinkedNode<T>* pNode, const T& x);
	bool ModiflyNodeValue(LinkedNode<T>* pNode, const T& x);
	bool GetNodeValue(LinkedNode<T>* pNode, T& x);
	LinkedNode<T>* GetLeftChild(LinkedNode<T>* pNode);
	LinkedNode<T>* GetRightChild(LinkedNode<T>* pNode);
	//递归方式 先序 中序 后序遍历
	void PreOrderTraverse(LinkedNode<T>* pNode);
	void InOrderTraverse(LinkedNode<T>* pNode);
	void PostOrderTraverse(LinkedNode<T>* pNode);
	//非递归方式 先序 中序 后序 逐层遍历
	void PreOrderTraverse();
	//void InOrderTraverse();
	//void PostOrderTraverse();
	void LevelOrderTraverse();
	// 非递归方式获取指定节点的双亲节点
	LinkedNode<T>* GetParent(LinkedNode<T>* pNode);
	// 删除以指定节点为根的子树
	void DeleteSubTree(LinkedNode<T>* pNode);
	// 由DeleteSubTree函数调用非递归的方式删除指定根的子树节点
	void DeleteSubTreeNode(LinkedNode<T>* pNode);
	// 非递归方式根据关键字查找节点
	LinkedNode<T>* SearchByKey(const T& x);
private:
	LinkedNode<T>* m_pRoot;	// 指向根节点的指针
};

// 创建空二叉树
template<class T>
LinkedBinTree<T>::LinkedBinTree()
{
	m_pRoot = NULL;		// 根节点为空
}

// 按指定元素值为根建树
template<class T>
LinkedNode<T>* LinkedBinTree<T>::CreatRoot(const T& x)
{
	// 若存在原本的根节点，修改
	if (m_pRoot != NULL)
		m_pRoot->m_data = x;
	// 若不存在，新建节点
	else
	{
		m_pRoot = new LinkedNode<T>(x);
	}
	return m_pRoot;
}

// 二叉树是否为空
template<class T>
bool LinkedBinTree<T>::IsEmpty()
{
	if (m_pRoot == NULL)
		return true;
	else
		return false;
}

// 获取根节点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetRoot()
{
	return m_pRoot;
}

// 指定节点作为左孩子插入
template<class T>
LinkedNode<T>* LinkedBinTree<T>::InsertLeftChild(LinkedNode<T>* pNode, const T& x)
{
	LinkedNode<T>* pNewNode;	// 待插入的节点
	if (pNode == NULL)			// 要插入的位置为空
		return NULL;
	pNewNode = new LinkedNode<T>(x);
	if (pNewNode == NULL)		//每次new之后都要判断new空间是否成功
		return NULL;
	pNode->m_pLeftchild = pNewNode;
	return pNewNode;
}

// 指定根节点pNode将x作为右孩子插入
template<class T>
LinkedNode<T>* LinkedBinTree<T>::InsertRightChild(LinkedNode<T>* pNode, const T& x)
{
	LinkedNode<T>* pNewNode;	// 待插入的节点
	if (pNode == NULL)			// 要插入的位置为空
		return NULL;
	pNewNode = new LinkedNode<T>(x);
	if (pNewNode == NULL)		//每次new之后都要判断new空间是否成功
		return NULL;
	pNode->m_pRightchild = pNewNode;
	return pNewNode;
}

// 修改指定节点元素值
template<class T>
bool LinkedBinTree<T>::ModiflyNodeValue(LinkedNode<T>* pNode, const T& x)
{
	if (IsEmpty())
		return false;
	else
	{
		pNode->m_data = x;
		return true;
	}
}

// 获取指定节点的元素值
template<class T>
bool LinkedBinTree<T>::GetNodeValue(LinkedNode<T>* pNode, T& x)
{
	if (pNode == NULL)
		return false;
	x = pNode->m_data;
	return true;
}

// 获取指定节点的左孩子
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetLeftChild(LinkedNode<T>* pNode)
{
	if (pNode == NULL)
		return NULL;
	return pNode->m_pLeftchild;
}

// 获取指定节点的右孩子
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetRightChild(LinkedNode<T>* pNode)
{
	if (pNode == NULL)
		return NULL;
	return pNode->m_pRightchild;
}

//递归方式 先序 中序 后序遍历
//先序：根 左 右， PNode这个根节点开始进行
template<class T>
void LinkedBinTree<T>::PreOrderTraverse(LinkedNode<T>* pNode)
{
	if (pNode == NULL)
		return NULL;
	cout << pNode->m_data << " ";	// 每次迭代输出一个节点（根）
	PreOrderTraverse(pNode->m_pLeftchild);
	PreOrderTraverse(pNode->m_pRightchild);
}

// 中序： 左 根 右
template<class T>
void LinkedBinTree<T>::InOrderTraverse(LinkedNode<T>* pNode)
{
	if (pNode == NULL)
		return NULL;
	InOrderTraverse(pNode->m_pLeftchild);
	cout << pNode->m_data << " ";	// 每次迭代输出一个节点（根）
	InOrderTraverse(pNode->m_pRightchild);
}

// 后序：左 右 根
template<class T>
void LinkedBinTree<T>::PostOrderTraverse(LinkedNode<T>* pNode)
{
	if (pNode == NULL)
		return NULL;
	PostOrderTraverse(pNode->m_pLeftchild);
	PostOrderTraverse(pNode->m_pRightchild);
	cout << pNode->m_data << " ";	// 每次迭代输出一个节点（根）
}


//非递归方式 先序 中序 后序 逐层遍历
// 先序：用栈
/*
* 1. 根入栈
* 2. 栈顶元素出栈并访问（根先出），栈顶元素有右子树右子树先入栈，有左子树左子树再入栈
* 3. 重复2直到栈空
*/
template<class T>
void LinkedBinTree<T>::PreOrderTraverse()
{
	LinkedNode<T>* pNode = NULL;
	// 存储LinkedNode<T>*类型的LinkStack为s
	LinkStack<LinkedNode<T>*> s;
	if (m_pRoot == NULL)
		return;
	// 根节点入栈
	s.Push(m_pRoot);
	// 栈不空时循环
	while (!s.IsEmpty())
	{
		// 栈顶元素出栈并被访问
		s.Pop(pNode);
		cout << pNode->m_data << " ";
		// 栈顶元素（子树根）有右子树右子树入栈
		if (pNode->m_pRightchild)
			s.Push(pNode->m_pRightchild);
		// 栈顶元素（子树根）有左子树左子树入栈
		if (pNode->m_pLeftchild)
			s.Push(pNode->m_pLeftchild);
	}
}

// 非递归逐层遍历
/*
* 1. 根节点入队
* 2. 队头元素出队且访问（cout），有左就左入队，有右就右入队
* 3. 直到队空
*/
template<class T>
void LinkedBinTree<T>::LevelOrderTraverse()
{
	// 存树根地址
	LinkQueue<LinkedBinTree<T>*> q;
	LinkedNode<T>* pNode = NULL;
	if (m_pRoot == NULL)
		return;
	q.Insert(m_pRoot);
	while (!q.IsEmpty())
	{
		q.Delete(pNode);
		cout << pNode->m_data << " ";
		if (pNode->m_pLeftchild)				// 如果左孩子存在
			q.Insert(pNode->m_pLeftchild);		// 左孩子入队，入队后下一次循环找左孩子的左右节点是否存在
		if (pNode->m_pRightchild)
			q.Insert(pNode->m_pRightchild);
	}
}

// 删除二叉树
template<class T>
LinkedBinTree<T>::~LinkedBinTree()
{
	Clear();
}

// 清空二叉树
template<class T>
void LinkedBinTree<T>::Clear()
{
	DeleteSubTree(m_pRoot);
}

// 非递归方式获取指定节点的双亲节点
// 参考逐层遍历
template<class T>
LinkedNode<T>* LinkedBinTree<T>::GetParent(LinkedNode<T>* pNode)
{
	LinkQueue<LinkedNode<T>*> q;
	LinkedNode<T>* pCurNode = NULL;
	// 若指定二叉树节点为空 返回空
	if (pNode == NULL)
		return NULL;
	// 若根节点为空，空树
	if (m_pRoot == NULL)
		return NULL;
	q.Insert(m_pRoot);
	while (!q.IsEmpty())
	{
		q.Delete(pCurNode);
		if (pCurNode->m_pLeftchild == pNode || pCurNode->m_pRightchild == pNode)
			return pCurNode;
		if (pCurNode->m_pLeftchild)
			q.Insert(pCurNode->m_pLeftchild);
		if (pCurNode->m_pRightchild)
			q.Insert(pCurNode->m_pRightchild);
	}
	return NULL;
}

// 删除以指定节点为根的子树，逻辑上
template<class T>
void LinkedBinTree<T>::DeleteSubTree(LinkedNode<T>* pNode)
{
	LinkedNode<T>* pParentNode = NULL;
	if (pNode == NULL)
		return;
	// 整棵树删除 根节点为空
	if (pNode = m_pRoot)
		m_pRoot = NULL;
	// 否则，若指定节点存在双亲节点，则将双亲节点的左/右孩子置空
	// pParentNode为指定节点的双亲结点，GetParent(pNode)有值说明有双亲节点
	else if ((pParentNode = GetParent(pNode)) != NULL)
	{
		if (pParentNode->m_pLeftchild == pNode)
			pParentNode->m_pLeftchild = NULL;
		if (pParentNode->m_pRightchild == pNode)
			pParentNode->m_pRightchild = NULL;
	}
	// 否则，指定节点不是树中节点
	else
		return;
	// 物理上删除子树
	DeleteSubTreeNode(pNode);
}

// 由DeleteSubTree函数调用非递归的方式删除指定根的子树节点，物理上
template<class T>
void LinkedBinTree<T>::DeleteSubTreeNode(LinkedNode<T>* pNode)
{
	LinkQueue<LinkedNode<T>*> q;
	LinkedNode<T>* pCurNode = NULL;
	if (pNode == NULL)
		return;
	q.Insert(pNode);
	while (!q.IsEmpty())
	{
		q.Delete(pCurNode);
		if (pCurNode->m_pLeftchild)
			q.Insert(pCurNode->m_pLeftchild);
		if (pCurNode->m_pRightchild)
			q.Insert(pCurNode->m_pRightchild);
		delete pCurNode;
	}
}

// 非递归方式根据关键字查找节点
template<class T>
LinkedNode<T>* LinkedBinTree<T>::SearchByKey(const T& x)
{
	LinkQueue<LinkedNode<T>*>q;
	LinkedNode<T>* pMatchNode = NULL;
	if (m_pRoot == NULL)
		return NULL;
	// 非递归层次遍历
	q.Insert(m_pRoot);
	while (!q.IsEmpty())
	{
		q.Delete(pMatchNode);	// 出队，队头元素放到pMatchNode
		if (pMatchNode->m_data == x)
			return pMatchNode;
		if (pMatchNode->m_pLeftchild)
			q.Insert(pMatchNode->m_pLeftchild);
		if (pMatchNode->m_pLeftchild)
			q.Insert(pMatchNode->m_pRightchild);
	}
	return NULL;
}

/*--------------二叉查找树------------
元素k插入排序树中，
*/
template<class T>
void InsertBST(LinkedBinTree<T>& btree, T K)
{
	LinkedNode<T>* pNode = NULL;
	LinkedNode<T>* pChild = NULL;
	T x;
	// 若树为空，直接插在根节点
	if (btree.IsEmpty())
	{
		btree.CreatRoot(K);
		return;
	}
	// 若树不为空，先得到树的树根，开始循环小的在左大的在右
	pNode = btree.GetRoot();
	while (pNode)
	{
		btree.GetNodeValue(pNode, x);
		// 若K已经是树中节点，不允许重复
		if (K == x)
			return;
		// K是新节点, 小的左大的右
		if (K < x)
		{
			// 根节点有左子树，继续找下一个左子树
			if ((pChild = btree.GetLeftChild(pNode)) != NULL)
				pNode = pChild;
			else
			{
				btree.InsertLeftChild(pNode, K);
				return;
			}
		}
		else
		{
			if ((pChild = btree.GetRightChild(pNode)) != NULL)
				pNode = pChild;
			else
			{
				btree.InsertRightChild(pNode, K);
				return;
			}
		}
	}
}

// 根据一组树生成二叉排序树
template<class T>
void CreatBST(T R[], int nSize, LinkedBinTree<T>& btree)
{
	// 元素依次插入二叉排序树中, R[]是数组
	for (int n = 0; n < nSize; n++)
		InsertBST(btree, R[n]);
}

// 递归方式二叉树查找
template<class T>
LinkedNode<T>* SearchBST(LinkedNode<T>* pRoot, T K)
{
	LinkedBinTree<T> btree;
	T x;
	// pBoot为空 查找失败
	if (pRoot == NULL)
		return NULL;
	btree.GetNodeValue(pRoot, x);	// 根节点值放到x里
	if (K == x)
		return pRoot;
	// 在左子树继续寻找
	else if (K < x)
		return SearchBST(btree.GetLeftChild(pRoot), K);
	else
		return SearchBST(btree.GetRightChild(pRoot), K);
}