Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Fast Binary Tree Operations

, 22 Jan 2005
Describes main binary tree operations.
binarytree_demo.zip
BinaryTreeDemo.exe
binarytree_src.zip
BinaryTreeDemo.dsp
Sample
BinaryTreeDemo.clw
res
BinaryTreeDemo.ico
icon1.ico
icon2.ico
BinaryTreeDemo.dsw
// BinaryTreeDemoDlg.cpp : implementation file
//

#include "stdafx.h"
#include "BinaryTreeDemo.h"
#include "BinaryTreeDemoDlg.h"
#include ".\binarytreedemodlg.h"
#include "FolderBrowse.h"
#include "Anchor.h"

#include <fcntl.h>
#include <sys/stat.h>
#include <io.h>

#pragma warning(disable:4311)

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

#define DELIMITERS		" \r\n\t!@#$%^&*()_+-={}|\\:\"'?�/.,<>������;"
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	enum { IDD = IDD_ABOUTBOX };

	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support

// Implementation
protected:
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()


// CBinaryTreeDemoDlg dialog



CBinaryTreeDemoDlg::CBinaryTreeDemoDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CBinaryTreeDemoDlg::IDD, pParent)
{
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	m_strFolder = AfxGetApp()->GetProfileString("Options", "Folder");
	m_strExt = AfxGetApp()->GetProfileString("Options", "Extension", "cpp,c,h,txt,log");
	m_bRedBlack = AfxGetApp()->GetProfileInt("Options", "Read Black", 0);

	m_rbTree.NoRepeat = true;
	m_size = CSize(0, 0);
}

void CBinaryTreeDemoDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	DDX_Control(pDX, IDC_STATUS, m_staticStatus);
	DDX_Control(pDX, IDC_TREE1, m_tree);
	DDX_Text(pDX, IDC_EDIT1, m_strFolder);
	DDX_Text(pDX, IDC_EDIT2, m_strExt);
	DDX_Check(pDX, IDC_CHECK1, m_bRedBlack);
}

BEGIN_MESSAGE_MAP(CBinaryTreeDemoDlg, CDialog)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
	ON_BN_CLICKED(IDC_BROWSE, OnBnClickedBrowse)
	ON_BN_CLICKED(IDOK, OnBnClickedOk)
	ON_BN_CLICKED(IDC_CLEAR, OnBnClickedClear)
	ON_BN_CLICKED(IDC_DELETE, OnBnClickedDelete)
	ON_BN_CLICKED(IDC_SUCCESSOR, OnBnClickedSuccessor)
	ON_BN_CLICKED(IDC_PREDECESSOR, OnBnClickedPredecessor)
	ON_BN_CLICKED(IDC_MIN, OnBnClickedMin)
	ON_BN_CLICKED(IDC_MAX, OnBnClickedMax)
	ON_NOTIFY(TVN_ITEMEXPANDING, IDC_TREE1, OnTvnItemexpandingTree1)
	ON_WM_SIZE()
	ON_BN_CLICKED(IDC_CHECK1, OnBnClickedCheck1)
	ON_WM_DESTROY()
END_MESSAGE_MAP()


// CBinaryTreeDemoDlg message handlers

BOOL CBinaryTreeDemoDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon

	m_imageList.Create(16, 16, ILC_MASK, 0, 2);	
	m_imageList.Add(AfxGetApp()->LoadIcon(IDI_RED));
	m_imageList.Add(AfxGetApp()->LoadIcon(IDI_BLACK));
	if (m_bRedBlack)
		m_tree.SetImageList(&m_imageList, TVSIL_NORMAL);
	else
		m_tree.SetImageList(NULL, TVSIL_NORMAL);
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CBinaryTreeDemoDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CBinaryTreeDemoDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this function to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CBinaryTreeDemoDlg::OnQueryDragIcon()
{
	return static_cast<HCURSOR>(m_hIcon);
}

void CBinaryTreeDemoDlg::OnBnClickedBrowse()
{
	CFolderBrowse browse;
	if(browse.Browse(m_strFolder) == false)
		return;
	m_strFolder = browse.m_strFolder;
	AfxGetApp()->WriteProfileString("Options", "Folder", m_strFolder);
	UpdateData(false);
}

CString GetExt(CString strName)
{
	int nIndex = strName.Find('.');
	strName.MakeLower();
	return nIndex > 0 ? strName.Mid(nIndex) : "";
}

CString Commas(int nValue)
{
	CString str;
	str.Format("%d", nValue);
	nValue = str.GetLength()-3;
	while(nValue > 0)
		str.Insert(nValue, ','), nValue -= 3;
	return str;
}

int CBinaryTreeDemoDlg::ParseFolder(LPCSTR lpcsFolder)
{
	int nParsedSize = 0;
	CString strFolder = lpcsFolder;
	CString strExt = '.'+m_strExt+'.', str;
	strExt.Replace(',', '.');
	_finddata_t ff;
	int nFound = (int)_findfirst(strFolder+"\\*.*", &ff);
	while(nFound != -1)
	{
		if(ff.attrib&_A_SUBDIR)
		{
			if(ff.name[0] != '.')
				nParsedSize += ParseFolder(strFolder+"\\"+ff.name);
		}
		else
		{
			str = GetExt(ff.name)+'.';
			if(ff.size > 0 && str.IsEmpty() == false && strExt.Find(str) != -1)
			{
				nParsedSize += ff.size;
				m_staticStatus.SetWindowText(strFolder+"\\"+ff.name);

				int nFile = _open(strFolder+"\\"+ff.name, _O_BINARY|_O_RDONLY, 0);
				int nLength = _filelength(nFile);
				char* pBuffer = new char[nLength+1];
				_read(nFile, pBuffer, nLength);
				_close(nFile);
				pBuffer[nLength] = 0;

				char *pToken = strtok(pBuffer, DELIMITERS);
				while(pToken)
				{
					if(m_bRedBlack)
						m_rbTree.Insert(pToken)->Data = 0;
					else
						m_rbTree.CBinaryTree<string, LPCSTR, HTREEITEM, HTREEITEM>::Insert(pToken)->Data = 0;
					pToken = strtok(NULL, DELIMITERS);
				}
				delete pBuffer;
			}
		}
		if(_findnext(nFound, &ff) == -1)
			break;
	}
	return nParsedSize;
}

void CBinaryTreeDemoDlg::OnBnClickedOk()
{
	UpdateData();

	m_tree.DeleteAllItems();

	DWORD dw = ::GetTickCount();
	int nParsedSize = ParseFolder(m_strFolder);
	dw = ::GetTickCount()-dw;

	if(m_rbTree.Root)
	{
		CString str;
		str.Format("%s (%s)", m_rbTree.Root->Key.c_str(), Commas(m_rbTree.Root->Count));
		InsertItem(-1, m_rbTree.Root, TVI_ROOT);
	}

	m_staticStatus.SetWindowText("Parsing "+Commas(nParsedSize/1024)+" KB, Found "+Commas(m_rbTree.GetCount())+" tokens, in "+Commas(dw/1000)+" secs");
}

void CBinaryTreeDemoDlg::OnBnClickedClear()
{
	m_tree.DeleteAllItems();
	m_rbTree.RemoveAll();
}

void CBinaryTreeDemoDlg::OnBnClickedDelete()
{
	UpdateData(TRUE);

	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	TNODE* pParent = pNode->Parent;
	if(m_bRedBlack)
		m_rbTree.Delete((CRBTreeNode<string, HTREEITEM>*)pNode);
	else
		m_rbTree.CBinaryTree<string, LPCSTR, HTREEITEM, HTREEITEM>::Delete(pNode);

	m_tree.DeleteAllItems();
	if(m_rbTree.Root)
	{
		InsertItem(-1, m_rbTree.Root, TVI_ROOT);
		Expand(pParent?pParent:m_rbTree.Root);
	}
}

void CBinaryTreeDemoDlg::OnBnClickedSuccessor()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Successor(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedPredecessor()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Predecessor(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedMin()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Min(pNode));
}

void CBinaryTreeDemoDlg::OnBnClickedMax()
{
	HTREEITEM hIT = m_tree.GetSelectedItem();
	if(hIT == NULL)
	{
		AfxMessageBox("Please, Select node in the tree first");
		return;
	}
	TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
	Select(m_rbTree.Max(pNode));
}

void CBinaryTreeDemoDlg::OnTvnItemexpandingTree1(NMHDR *pNMHDR, LRESULT *pResult)
{
	LPNMTREEVIEW pNMTreeView = reinterpret_cast<LPNMTREEVIEW>(pNMHDR);
	
	HTREEITEM hIT = pNMTreeView->itemNew.hItem;
	if((TVIS_EXPANDED&pNMTreeView->itemNew.state) == 0 
		&& (TVIS_EXPANDEDONCE&pNMTreeView->itemNew.state) == 0
		&& pNMTreeView->hdr.code == TVN_ITEMEXPANDING)
	{
		TNODE* pNode = (TNODE*)m_tree.GetItemData(hIT);
		for(int nChild = 0; nChild < 2; nChild++)
			if(pNode != m_rbTree.Nil && pNode->Childs[nChild] != m_rbTree.Nil)
				InsertItem(nChild, pNode->Childs[nChild], hIT);

	}
	*pResult = 0;
}

void CBinaryTreeDemoDlg::OnSize(UINT nType, int cx, int cy)
{
	CDialog::OnSize(nType, cx, cy);

	if(m_size.cx > 0 && nType != SIZE_MINIMIZED)
	{
		Anchor(this, IDCANCEL, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDOK, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_CLEAR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_BROWSE, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_DELETE, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_SUCCESSOR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_PREDECESSOR, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_MIN, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_MAX, A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_EDIT1, A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_EDIT2, A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_TREE1, A_BOTTOM|A_LEFT|A_RIGHT|A_TOP, m_size, CSize(cx, cy));
		Anchor(this, IDC_STATUS, A_BOTTOM|A_LEFT|A_RIGHT, m_size, CSize(cx, cy));
		Anchor(this, IDC_CHECK1, A_BOTTOM|A_LEFT, m_size, CSize(cx, cy));
	}	
	m_size = CSize(cx, cy);	
}

void CBinaryTreeDemoDlg::InsertItem(int nChild, TNODE* pNode, HTREEITEM hParent)
{
	if(pNode == m_rbTree.Nil || pNode == NULL)
		return;
	TV_ITEM Item;
	Item.mask = TVIF_CHILDREN;
	Item.cChildren = 1;

	CString str;
	str.Format("[%s] %s (%s)", nChild < 0 ? "Root":(nChild?"R":"L"), pNode->Key.c_str(), Commas(pNode->Count));
	HTREEITEM itemNew;
	if(m_bRedBlack)
		itemNew	= m_tree.InsertItem(str, ((RBTNODE*)pNode)->Color, ((RBTNODE*)pNode)->Color, hParent, TVI_LAST);
	else
		itemNew	= m_tree.InsertItem(str, hParent, TVI_LAST);
	pNode->Data = itemNew;
	m_tree.SetItemData(itemNew, (DWORD)pNode);
	if(pNode->Childs[0] != m_rbTree.Nil || pNode->Childs[1] != m_rbTree.Nil)
	{
		Item.hItem = itemNew;
		m_tree.SetItem(&Item);
	}
}

void CBinaryTreeDemoDlg::Expand(TNODE* pNode)
{
	TNODE* node = m_rbTree.Root;
	int nResult;
	while(node && (nResult = node->Key.compare(pNode->Key)) != 0)
	{
		m_tree.Expand(node->Data, TVE_EXPAND);
		node = node->Childs[nResult < 0];
	}
	m_tree.Expand(pNode->Data, TVE_EXPAND);
	m_tree.SelectItem(pNode->Data);
}

void CBinaryTreeDemoDlg::Select(TNODE* pNode)
{
	if(pNode)
		Expand(pNode);
}

void CBinaryTreeDemoDlg::OnBnClickedCheck1()
{
	UpdateData();

	if (m_bRedBlack)
		m_tree.SetImageList(&m_imageList, TVSIL_NORMAL);
	else
		m_tree.SetImageList(NULL, TVSIL_NORMAL);
}

void CBinaryTreeDemoDlg::OnDestroy()
{
	UpdateData();

	AfxGetApp()->WriteProfileString("Options", "Folder", m_strFolder);
	AfxGetApp()->WriteProfileString("Options", "Extension", m_strExt);
	AfxGetApp()->WriteProfileInt("Options", "Read Black", m_bRedBlack);

	CDialog::OnDestroy();
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author


| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 23 Jan 2005
Article Copyright 2004 by Hatem Mostafa
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid