displaydlg.cpp

来自「winsail v2.0是用于DOS下的图形界面空间系统」· C++ 代码 · 共 1,590 行 · 第 1/3 页

	return(m_pRoot);
}


//函数功能：得到根结点
CTreeNode* CTree::GetRoot(CTreeNode *pTreeNode)
{
	if (pTreeNode == NULL)
	{
		return (NULL);
	}
	
	while (NULL != pTreeNode->pParent)
	{
		pTreeNode = pTreeNode->pParent;
	}
	return(pTreeNode);
}

//函数功能：求双亲
CTreeNode* CTree::GetParent(CTreeNode *pTreeNode)
{
	return(pTreeNode->pParent);
}

//函数功能：求孩子
CTreeNode* CTree::GetChild(CTreeNode* pTreeNode, DWORD dwIndex)
{
	//判断结点的合法性
	if (pTreeNode == NULL)
	{
		return(NULL);
	}

	CTreeNode* pChild = pTreeNode->Node.Tree.pChild;

	DWORD dwPoint = 0;
	while ((dwPoint++) < dwIndex && NULL != pChild)
	{
		//如果是最后一棵子树
		if (dwIndex == 0xFFFFFFFFlu  && pChild->Node.Tree.pSibling == NULL)
		{
			break;
		}

		pChild = pChild->Node.Tree.pSibling;
	}
	

	return(pChild);
}

//函数功能：求右兄弟
CTreeNode* CTree::GetRightSibling(CTreeNode* pTreeNode, DWORD dwIndex)
{
	//判断结点的合法性
	if (pTreeNode == NULL)
	{
		return(NULL);
	}

	CTreeNode* pSibling = pTreeNode->Node.Tree.pSibling;

	DWORD dwPoint = 0;
	while ((dwPoint++) < dwIndex && NULL != pSibling)
	{
		//如果是最后一棵子树
		if (dwIndex == 0xFFFFFFFFlu  && pSibling->Node.Tree.pSibling == NULL)
		{
			break;
		}

		pSibling = pSibling->Node.Tree.pSibling;
	}
	

	return(pSibling);
}

//函数功能：插入子树
BOOL CTree::InsertChild(CTreeNode* pTarget, DWORD dwIndex, CTreeNode* pSource)
{
	//判断指针的合法性
	if (NULL == pTarget || NULL == pSource)
	{
		return(FALSE);
	}


	CTreeNode* pChild = NULL;
	//第一棵子树
	if (dwIndex == 0)
	{
		pSource->pParent = pTarget;
		pSource->Node.Tree.pSibling = pTarget->Node.Tree.pChild;
		pTarget->Node.Tree.pChild = pSource;
		return (TRUE);
	}
	//最后一棵子树
	else if (dwIndex == 0xFFFFFFFFlu)
	{
		pSource->pParent = pTarget;

		pChild = this->GetChild(pTarget, 0xFFFFFFFFlu);
		//第一棵子树
		if (pChild == NULL)
		{			
			pSource->Node.Tree.pSibling = pTarget->Node.Tree.pChild;
			pTarget->Node.Tree.pChild = pSource;
		}
		//最后一棵子树
		else
		{
			pSource->Node.Tree.pSibling = NULL;
			pChild->Node.Tree.pSibling = pSource;
		}
		return(TRUE);
	}
	//不是第一棵子树
	else
	{
		pChild = this->GetChild(pTarget, dwIndex - 1);
		if (pChild != NULL)
		{
			pSource->pParent = pTarget;
			pSource->Node.Tree.pSibling = pChild->Node.Tree.pSibling;
			pChild->Node.Tree.pSibling = pSource;
			return (TRUE);
		}
	}

	return(FALSE);
}



//函数功能：删除子树
BOOL CTree::DeleteChild(CTreeNode* pTreeNode, DWORD dwIndex)
{
	if (pTreeNode == NULL)
	{
		return(FALSE);
	}

	CTreeNode* pSibling = NULL;
	CTreeNode* pSibling2 = NULL;
	CTreeNode* pChild = this->GetChild(pTreeNode, dwIndex);

	if (pChild == NULL)
	{
		return(FALSE);
	}

	//第一个孩子
	if (dwIndex == 0)
	{
		//修改当前结点的第一个孩子：结点的兄弟结点作为当前结点的孩子
		pTreeNode->Node.Tree.pChild = 
			pTreeNode->Node.Tree.pChild->Node.Tree.pSibling;
	}
	//最后一个孩子
	else if (dwIndex == 0xFFFFFFFFlu)
	{
		pChild = pTreeNode->Node.Tree.pChild;

		pSibling2 = pChild;
		pSibling = pChild->Node.Tree.pSibling;

		while (pSibling->Node.Tree.pSibling != NULL)
		{
			pSibling2 = pSibling;
			pSibling = pSibling->Node.Tree.pSibling;
		}
			

		//第一个孩子
		if (pSibling == NULL)
		{
			//修改当前结点的第一个孩子：NULL
			pTreeNode->Node.Tree.pChild = NULL;;
		}
		//不是第一个孩子
		else
		{
			pSibling2->Node.Tree.pSibling = NULL;

			//修改要删除结点为孩子
			pChild = pSibling;		
		}

	}
	//中间孩子
	else
	{		
		//后一个兄弟		
		pSibling = this->GetChild(pTreeNode, dwIndex + 1);
		//前一个兄弟		
		pSibling2 = this->GetChild(pTreeNode, dwIndex - 1);

		//修改兄弟
		pSibling2->Node.Tree.pSibling = pSibling;
	}

	//删除指定结点
	pChild->pParent = NULL;
	pChild->Node.Tree.pSibling = NULL;
	this->DeleteTree(pChild, m_pDeleteUser);	
	return(FALSE);
}

//函数功能：访问结点操作
CTreeNode* CTree::VisitTree(CTreeNode* pTreeNode, void* pUser, int nCol)
{
	if (m_pVisitFc == NULL)
	{
		return(NULL);
	}
	return (m_pVisitFc(this, pTreeNode, pUser, m_nDegree, nCol));
}

//函数功能：析离结点操作
CTreeNode* CTree::MoveTree(CTreeNode* pTreeNode, void* pUser)
{
	if (m_pMoveFc == NULL)
	{
		return(NULL);
	}
	return (m_pMoveFc(pTreeNode, pUser));
}

//函数功能：删除结点操作
CTreeNode* CTree::DeleteTree(CTreeNode* pTreeNode, void* pUser)
{
	if (m_pDeleteFc == NULL)
	{
		return(NULL);
	}
	return (m_pDeleteFc(pTreeNode, pUser));
}

int CBinaryTree::CalcMaxDegree()
{
	this->TraverseBinaryTree(CTree::CalcDegreeFc, 
		NULL, TRAVERSING_BINARYTREE_FIRST);
	return (m_nMaxDegree);
}

//函数功能：建立树
BOOL CBinaryTree::BuildBinaryTree(CTreeNode* pRoot,
		CTreeNode* pChildL, CTreeNode* pChildR)
{
	this->ClearTree();
	
	if (pRoot == NULL)
	{
		return(TRUE);
	}

	//设置根结点
	m_pRoot = pRoot;
	//设置左结点
	m_pRoot->Node.BinaryTree.wFlagL = 0;
	m_pRoot->Node.BinaryTree.pChildL = pChildL;
	//设置右结点
	m_pRoot->Node.BinaryTree.wFlagR = 0;
	m_pRoot->Node.BinaryTree.pChildR = pChildR;

	//设置左孩子结点的父亲
	if (NULL != pChildL)
	{
		pChildL->pParent = pRoot;
	}

	//设置右孩子结点的父亲
	if (NULL != pChildR)
	{
		pChildR->pParent = pRoot;
	}

	return(TRUE);
}


//遍历筛选函数
CTreeNode* CTree::CalcDegreeFc(CTree* pTree, CTreeNode* pTreeNode, void* pUser, int nDegree, int nCol)
{
	return(NULL);
}


//函数功能：插入左子树
BOOL CBinaryTree::InsertChildL(CTreeNode* pNode, CTreeNode* pChildL)
{
	//移去原来的右子树
	if ((pNode->Node.BinaryTree.pChildL != NULL && 
			m_pRoot->Node.BinaryTree.wFlagL == 0) && NULL != m_pMoveFc)
	{
		m_pMoveFc(pNode->Node.BinaryTree.pChildL, m_pMoveUser);
		pNode->Node.BinaryTree.pChildL = NULL;
	}
	
	//设置新的右子树
	m_pRoot->Node.BinaryTree.wFlagL = 0;
	pNode->Node.BinaryTree.pChildL = pChildL;

	//设置子树的父亲
	if (pChildL != NULL)
	{
		pChildL->pParent = pNode;
	}
	return(TRUE);
}
//函数功能：插入右子树
BOOL CBinaryTree::InsertChildR(CTreeNode* pNode, CTreeNode* pChildR)
{
	//移去原来的右子树
	if ((pNode->Node.BinaryTree.pChildR != NULL && 
		m_pRoot->Node.BinaryTree.wFlagR == 0 ) &&NULL != m_pMoveFc)
	{
		m_pMoveFc(pNode->Node.BinaryTree.pChildR, m_pMoveUser);
		pNode->Node.BinaryTree.pChildR = NULL;
	}
	
	//设置新的右子树
	m_pRoot->Node.BinaryTree.wFlagR = 0;
	pNode->Node.BinaryTree.pChildR = pChildR;

	//设置子树的父亲
	if (pChildR != NULL)
	{
		pChildR->pParent = pNode;
	}
	return(TRUE);
}
//函数功能：以结点为根的遍历操作
CTreeNode* CBinaryTree::TraverseBinaryTree(CTreeNode* pTreeNode)
{
	CTreeNode* pTreeNode_Target = NULL;
	//指针不能为空
	if (pTreeNode == NULL)
	{
		if (m_pnCol != NULL && m_nDegree >= 2)
		{
			for (int i = m_nDegree + 1; i < MAX_TREE_DEGREE; i++)
			{
				m_pnCol[i - 1] += 1 << (i - m_nDegree);
			}

		}
		return(NULL);
	}

	int nOldDegree = m_nDegree;
	//统计最大度
	if (m_nMaxDegree < m_nDegree)
	{
		m_nMaxDegree = m_nDegree;
	}

	//根据不同的遍历类型，作出“先序”、“中序”、“后序”遍历树操作
	switch (m_nVisitStyle)
	{
		//先序遍历
		case TRAVERSING_BINARYTREE_FIRST:
		{
			//度计算
			m_nDegree += 0;			
			//访问根结点
			pTreeNode_Target = this->VisitTree(
				pTreeNode, m_pVisitUser, m_pnCol[m_nDegree - 1]);
			//列计算
			if (m_pnCol != NULL)
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否是返回结果
			if (pTreeNode_Target != NULL)
			{
				return(pTreeNode_Target);
			}

			//度计算
			m_nDegree++;
			//遍历左子树
			if (0 == pTreeNode->Node.BinaryTree.wFlagL)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildL);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildL == NULL &&
					pTreeNode->Node.BinaryTree.wFlagL == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否返回结果
			if(pTreeNode_Target != NULL)
			{
				return (pTreeNode_Target);
			}
	

			//度计算
			m_nDegree += 0;
			//遍历右子树
			if (0 == pTreeNode->Node.BinaryTree.wFlagR)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildR);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildR == NULL &&
					pTreeNode->Node.BinaryTree.wFlagR == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否返回结果
			if(pTreeNode_Target != NULL)
			{
				return (pTreeNode_Target);
			}


			break;
		}
		//中序遍历
		case TRAVERSING_BINARYTREE_MIDDLE:
		{
			//度计算
			m_nDegree++;
			//遍历左子树
			if (0 == pTreeNode->Node.BinaryTree.wFlagL)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildL);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildL == NULL &&
					pTreeNode->Node.BinaryTree.wFlagL == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否返回结果
			if(pTreeNode_Target != NULL)
			{
				return (pTreeNode_Target);
			}

			//度计算
			m_nDegree--;
			//访问根结点
			pTreeNode_Target = this->VisitTree(
				pTreeNode, m_pVisitUser, m_pnCol[m_nDegree - 1]);
			//列计算
			if (m_pnCol != NULL)
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否是返回结果
			if (pTreeNode_Target != NULL)
			{
				return(pTreeNode_Target);
			}


			//度计算
			m_nDegree += 1;
			//遍历右子树
			if (pTreeNode->Node.BinaryTree.wFlagR == 0)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildR);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildR == NULL &&
					pTreeNode->Node.BinaryTree.wFlagR == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否返回结果
			if(pTreeNode_Target != NULL)
			{
				return (pTreeNode_Target);
			}

			break;
		}
		//后序遍历
		case TRAVERSING_BINARYTREE_LAST:
		{
			//度计算
			m_nDegree++;
			//遍历左子树
			if (pTreeNode->Node.BinaryTree.wFlagL == 0)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildL);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildL == NULL &&
					pTreeNode->Node.BinaryTree.wFlagL == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}
			//是否返回结果
			if(pTreeNode_Target != NULL)
			{
				return (pTreeNode_Target);
			}

			//度计算
			m_nDegree += 0;
			//遍历右子树
			if (pTreeNode->Node.BinaryTree.wFlagR == 0)
			{
				pTreeNode_Target = this->TraverseBinaryTree(
					pTreeNode->Node.BinaryTree.pChildR);
			}
			//列计算
			if (m_pnCol != NULL && 
				(pTreeNode->Node.BinaryTree.pChildR == NULL &&
					pTreeNode->Node.BinaryTree.wFlagR == 0))
			{
				m_pnCol[m_nDegree - 1] += 1;
			}