treedlg.cpp

二叉树的实现 构成二叉树的基本元素是二叉树中的结点

// TreeDlg.cpp : implementation file
//

#include "stdafx.h"
#include "testtree.h"
#include "TreeDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CTreeDlg dialog


CTreeDlg::CTreeDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTreeDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTreeDlg)
	m_ichildcount = 0;
	//}}AFX_DATA_INIT
}


void CTreeDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTreeDlg)
	DDX_Control(pDX, IDC_TREE1, m_tree);
	DDX_Text(pDX, IDC_EDIT1, m_ichildcount);
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CTreeDlg, CDialog)
	//{{AFX_MSG_MAP(CTreeDlg)
	ON_BN_CLICKED(IDC_BUTTON_PRINT, OnButtonPrint)
	ON_BN_CLICKED(IDC_BUTTON_PRINT2, OnButtonPrint2)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTreeDlg message handlers
typedef struct ENUM_PARAM
{
	CTreeCtrl* hTree;
	HTREEITEM hParent;
	DWORD processid;
}ENUM_WIN_PAAM;


int CTreeDlg::addtree(vector<HTREEITEM>&hTreeItemvec,CTreeCtrl& ctree,const HTREEITEM& hParentItem,const int ichild)
{
	if(ichild<=0)
		return 0;

	TV_INSERTSTRUCT TCItem;

	ZeroMemory(&TCItem,sizeof(TV_INSERTSTRUCT));
	CString strText;
	CString strdisplayText;
	CString strLeft ;
	CString strRight;
	if(hParentItem == NULL)
	{
		strText = _T("");
	}
	else
	{
		strText = ctree.GetItemText(hParentItem);
	}
			
	strLeft.Format("%d",atol(strText.Left(1))+1);//子节点的层级
	HTREEITEM hItem;
	for(int i=0; i<ichild; i++)
	{
		strdisplayText.Format("%s%s%d", strLeft, strText, i+1); 
		TCItem.hParent = hParentItem;
		TCItem.item.mask = TVIF_TEXT| TVIF_STATE| TVIF_PARAM| TVIS_EXPANDED;
		TCItem.item.pszText = strdisplayText.GetBuffer(0);
		TCItem.item.lParam = atol(strLeft);
		hItem = ctree.InsertItem(&TCItem);
		
	}

	return 0;
}



void CTreeDlg::OnOK() 
{
	// TODO: Add extra validation here
	UpdateData(TRUE);
	int ichildcount = m_ichildcount;

	TV_INSERTSTRUCT TCItem;

	ZeroMemory(&TCItem,sizeof(TV_INSERTSTRUCT));
	vector<HTREEITEM> hItemvec;
	HTREEITEM hParentItem = m_tree.GetSelectedItem();
	addtree(hItemvec,m_tree,hParentItem,ichildcount);
	m_tree.SelectItem(hParentItem);
	m_tree.Expand(hParentItem,TVE_EXPAND);

//	CDialog::OnOK();
}

//广度优先搜索
/*
算法:
1、找到这个节点的所有兄弟，并放入栈中
2、从栈中弹出一个节点
3、检查这个节点是否有子节点，若有则将子节点作为一个待找节点
4、当待找节点存在或是栈不为空时返回步骤1.
*/
void CTreeDlg::OnButtonPrint() 
{
	// TODO: Add your control notification handler code here
	HTREEITEM hItem = m_tree.GetRootItem();
	HTREEITEM childhItem = hItem;
	stack<HTREEITEM> stackItem;

	CString strText ;

	while (1)
	{
		//得到同一层所有的兄弟节点
		while ( childhItem)
		{
			strText = m_tree.GetItemText(childhItem);
			TRACE("%s\n",strText);
			stackItem.push(childhItem);
					
			childhItem = m_tree.GetNextItem( childhItem, TVGN_NEXT);
		} // end while

		//得到一个选定节点的子节点
		if(!stackItem.empty())
		{
			childhItem = stackItem.top();
			stackItem.pop();
			childhItem = m_tree.GetChildItem(childhItem);
		}
		else
		{
			break;//所有的兄弟节点已遍历，则全部结束
		}

	} // end while
}

//深度优先搜索
/*
算法：
1、找到一个节点的所有子节点
2、回退一格，找它的所有兄弟节点，一直回退到最后结束
3、找到所有兄弟节点的子节点
一共有两种情质的节点，一种为只找兄弟，一种为只找了节点
*/
void CTreeDlg::OnButtonPrint2() 
{
	// TODO: Add your control notification handler code here
	HTREEITEM hItem = m_tree.GetRootItem();
	HTREEITEM childhItem = hItem;
	stack<HTREEITEM> stackItemchi;//
	stack<HTREEITEM> stackItembro;//

	CString strText;
	while( 1)
	{
		//找到一个节点的所有子节点		
		while (childhItem)
		{	
			strText = m_tree.GetItemText(childhItem);
			TRACE("%s\n",strText);
			stackItemchi.push(childhItem);
			childhItem = m_tree.GetChildItem(childhItem);
		} // end while

		//回退一格，查找这些子节点的兄弟节点
		while ( !stackItemchi.empty())
		{
			childhItem = stackItemchi.top();
			stackItemchi.pop();
			childhItem = m_tree.GetNextItem(childhItem, TVGN_NEXT);//取一个兄弟
			if(childhItem != NULL)
			{
				stackItembro.push(childhItem);
			}

		} // end while

		if(!stackItembro.empty())
		{
			childhItem = stackItembro.top();//从兄弟节点中取一个节点
			stackItembro.pop();
		}
		else
		{
			break;
		}
		
	}

}