avltreedemoview.cpp

AVL平衡二叉树。原本在这里下载了其他人的平衡二叉树

// AvlTreeDemoView.cpp : implementation of the CAvlTreeDemoView class
//

#include "stdafx.h"
#include "AvlTreeDemo.h"

#include "AvlTreeDemoDoc.h"
#include "AvlTreeDemoView.h"
#include "mainfrm.h"

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

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView

IMPLEMENT_DYNCREATE(CAvlTreeDemoView, CScrollView)

BEGIN_MESSAGE_MAP(CAvlTreeDemoView, CScrollView)
	//{{AFX_MSG_MAP(CAvlTreeDemoView)
	ON_COMMAND(IDM_AVLTREEDEMO, OnAvltreedemo)
	ON_COMMAND(IDM_INSERT, OnInsert)
	ON_COMMAND(IDM_REMOVE, OnRemove)
	ON_COMMAND(IDM_FIND, OnFind)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CScrollView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CScrollView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CScrollView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView construction/destruction

CAvlTreeDemoView::CAvlTreeDemoView()
{
	// TODO: add construction code here
	m_bPrintTree = FALSE;
	m_Tree = 0;
	memset(&m_tm, 0, sizeof(TEXTMETRIC));
}

CAvlTreeDemoView::~CAvlTreeDemoView()
{
	avlDestroy(m_Tree);
}

BOOL CAvlTreeDemoView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CScrollView::PreCreateWindow(cs);
}

void CAvlTreeDemoView::PrintTree(PAVL_NODE Node, int x1, int x2, int y, CDC *pDC)
{
	RECT rc;
	int len;
	char m_szData[16];
	len = sprintf(m_szData, "%d,%d", Node->weight, Node->data);
	rc.left = x2 - (len*m_tm.tmAveCharWidth)/2;
	rc.right = x2 + len*m_tm.tmAveCharWidth;
	rc.top = y+5;
	rc.bottom = y + 25;
	pDC->DrawText(m_szData, -1, &rc, DT_TOP|DT_NOPREFIX|DT_SINGLELINE);
	POINT pt;
	pt.x = x2 - 2;
	pt.y = rc.bottom + 2;
	pDC->MoveTo(pt);
	if(Node->left)
	{
		pt.x = x1 + (x2 - x1) / 2;
		pt.y = y + 52;
		pDC->LineTo(pt);
		PrintTree(Node->left, x1, pt.x, y + 55, pDC);
	}

	pt.x = x2 + 2;
	pt.y = rc.bottom + 2;
	pDC->MoveTo(pt);
	if(Node->right)
	{
		pt.x = x2 + (x2 - x1) / 2;
		pt.y = y + 52;
		pDC->LineTo(pt);
		PrintTree(Node->right, x2, pt.x, y + 55, pDC);
	}
}

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView drawing

void CAvlTreeDemoView::OnDraw(CDC* pDC)
{
	CAvlTreeDemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	if(m_bPrintTree)
	{
		if(m_tm.tmHeight == 0)
			pDC->GetTextMetrics(&m_tm);

		PAVL_NODE root = avlGetRootNode(m_Tree);
		PAVL_NODE node = root;
		while(node->right) node = node->right;
		DWORD maxID = node->weight;
		int maxlen=0;
		while(maxID > 0)
		{
			maxlen++;
			maxID /= 10;
		}
		
		CSize sizeTotal;
		sizeTotal.cx = (1<<root->height) * ((maxlen+2)*m_tm.tmAveCharWidth);
		sizeTotal.cy = root->height * 80;
		SetScrollSizes(MM_TEXT, sizeTotal);

		PrintTree(root, 0, sizeTotal.cx/2, 0, pDC);
	}
}

void CAvlTreeDemoView::OnInitialUpdate()
{
	CScrollView::OnInitialUpdate();

	CSize sizeTotal;
	// TODO: calculate the total size of this view
	sizeTotal.cx = sizeTotal.cy = 100;
	SetScrollSizes(MM_TEXT, sizeTotal);

	m_Tree = avlCreate();
}

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView printing

BOOL CAvlTreeDemoView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CAvlTreeDemoView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CAvlTreeDemoView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView diagnostics

#ifdef _DEBUG
void CAvlTreeDemoView::AssertValid() const
{
	CScrollView::AssertValid();
}

void CAvlTreeDemoView::Dump(CDumpContext& dc) const
{
	CScrollView::Dump(dc);
}

CAvlTreeDemoDoc* CAvlTreeDemoView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CAvlTreeDemoDoc)));
	return (CAvlTreeDemoDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CAvlTreeDemoView message handlers

void CAvlTreeDemoView::OnAvltreedemo() 
{
	// TODO: Add your command handler code here

	int testvalues[] = {9009, 5611, 5611, 1416, 20377, 12953, 25707, 9009, 31773,
		15315 , 16051 , 19386 , 4258, 14116, 30814, 6431,
		16772, 16524, 21055, 19062 , 3279, 27637, 9828, 20517,
		26021, 21259, 3739, 26707, 12000, 13645, 21558, 24476,
		18681, 24164, 3340, 18953, 14121, 18100, 2496, 18495,
		8141, 8754, 31046, 11510, 11279, 20853, 26018, 5805,
		2755, 26895, 28147, 20892, 6799, 17181,	25009, 5611 ,
		32591, 20253, 8499, 30241, 9911, 5120, 26484, 4575,
		58    , 6272, 24854, 24782, 27691, 9652, 13479, 10710,
		9763, 6114, 24612, 31377, 11938, 12692, 4027, 13055,
		30713};
	
	for(int i=0;i<sizeof(testvalues)/4;i++)
	{
		avlInsert(m_Tree, testvalues[i], rand()%100);
/*
		if(!m_pFreeItem)
		{
			PAVL_BUFFER buffer = (PAVL_BUFFER)new char[4096];
			int number;

			buffer->dwBufferSize = 4096;
			buffer->Next = m_pItemBuffer;
			m_pItemBuffer = buffer;

			number = (4096 - sizeof(AVL_BUFFER)) / sizeof(INDX_ITEM);
			pItem = (PINDX_ITEM)((PBYTE)buffer+sizeof(AVL_BUFFER));
			m_pFreeItem = pItem;
			for(int j=0; j<number-1; j++)
			{
				pItem->Next = pItem+1;
				pItem++;
			}
			pItem->Next = NULL;
		}
		pItem = m_pFreeItem;
		m_pFreeItem = m_pFreeItem->Next;

		pItem->Length = sprintf(pItem->DirectoryName, "directory %d", i);
		pItem->dwID = testvalues[i];

		m_Tree.Insert((DWORD)pItem);
*/
	}
	
	m_bPrintTree = TRUE;

	// Invalidate client area.
	Invalidate();
}

void CAvlTreeDemoView::OnInsert() 
{
	// TODO: Add your command handler code here
	CMainFrame *pFrame = (CMainFrame *)AfxGetMainWnd();
	char szData[256];
	PCHAR stopChar, startChar;
	BOOL bInsertion = FALSE;

	DWORD dwID;
	int i, number;

	memset(szData, 0, 256);
	pFrame->m_dlgBar.GetDlgItemText(IDC_EDIT_NODE_NUMBER, szData, 255);
	if(strlen(szData) == 0)
	{
		AfxMessageBox("Please input a node number in the edit box.");
		return;
	}
	((CEdit*)(pFrame->m_dlgBar.GetDlgItem(IDC_EDIT_NODE_NUMBER)))->SetSel((DWORD)0xffff0000, FALSE);

	startChar = szData;
	while(strlen(startChar))
	{
		dwID = (ULONG)strtod(startChar, &stopChar);
		if(stopChar == startChar)
		{
			startChar++;
			continue;
		}
		startChar = stopChar;
		
		//Allocate memory for node.
/*
		if(!m_pFreeItem)
		{
			if(!(buffer = (PAVL_BUFFER)new char[4096]))
				return;
			buffer->dwBufferSize = 4096;
			buffer->Next = m_pItemBuffer;
			m_pItemBuffer = buffer;
			number = (4096 - sizeof(AVL_BUFFER)) / sizeof(INDX_ITEM);
			pItem = (PINDX_ITEM)((PBYTE)buffer+sizeof(AVL_BUFFER));
			
			m_pFreeItem = pItem;
			for(i=0; i<number-1; i++)
			{
				pItem->Next = pItem+1;
				pItem++;
			}
			pItem->Next = NULL;
		}
		
		pItem = m_pFreeItem;
		m_pFreeItem = m_pFreeItem->Next;
		
		pItem->Length = sprintf((char*)pItem->DirectoryName, "directory %d", dwID);
		pItem->dwID = dwID;
*/
		
		if( 0 != avlInsert(m_Tree, dwID, rand()%100) )
			bInsertion = TRUE;
	}

	if(bInsertion)
	{
		m_bPrintTree = TRUE;
		// Invalidate client area.
		Invalidate();
	}
}

void CAvlTreeDemoView::OnRemove() 
{
	// TODO: Add your command handler code here
	CMainFrame *pFrame = (CMainFrame *)AfxGetMainWnd();
	CString strID;
	char *stopstring;

	PAVL_NODE node;

	if( m_Tree==0 || avlGetRootNode(m_Tree)==NULL )
	{
		AfxMessageBox("Invalid AVL-Tree!");
		return;
	}

	pFrame->m_dlgBar.GetDlgItemText(IDC_EDIT_NODE_NUMBER, strID);
	((CEdit*)(pFrame->m_dlgBar.GetDlgItem(IDC_EDIT_NODE_NUMBER)))->SetSel((DWORD)0xffff0000, FALSE);

	if ( avlRemove(m_Tree, (int)strtod(strID, &stopstring)) )
	{
		Invalidate();
	}
}

void CAvlTreeDemoView::OnFind() 
{
	CMainFrame *pFrame = (CMainFrame *)AfxGetMainWnd();
	CString strID;
	char *stopstring;
	int			w;
	unsigned long lval;

	pFrame->m_dlgBar.GetDlgItemText(IDC_EDIT_NODE_NUMBER, strID);
	((CEdit*)(pFrame->m_dlgBar.GetDlgItem(IDC_EDIT_NODE_NUMBER)))->SetSel((DWORD)0xffff0000, FALSE);

	w = (int)strtod(strID, &stopstring);
	if ( avlFind(m_Tree, w, &lval) )
	{
		//Invalidate();
		CString		str;
		str.Format("Find the node : %d, %d", w, lval);
		AfxMessageBox(str);
	}
	else
		AfxMessageBox("没找到");
}


static int g_NodeIndex = 0;
static void PrintNode(PAVL_NODE node)
{
	if ( NULL != node->left )
		PrintNode(node->left);
	if ( node )
	{
		debug("%3d（%3d）\t", node->weight, node->data);
		if ( ++g_NodeIndex % 5 == 0 )
			debug("\n");
	}
	if ( NULL != node->right )
		PrintNode(node->right);
}
void PrintBlock()
{
	PAVL_NODE	root;
	g_NodeIndex = 0;
	root = avlGetRootNode(g_pNffsDev_debug->mapCache.cacheTree);
	if ( root == NULL )
		return ;
	debug("--------------虚拟块号（逻辑块号）对应关系表，--------------\n");
	PrintNode(root);
	debug("\n");
}