binary_tree.cpp

如何将ABCDEFG按照指定的顺序

#include <string.h>
#include <stdio.h>
#include <assert.h>

struct TreeNode
{
	char val;
	TreeNode * pLeft;
	TreeNode * pRight;
};

int CmpTreeNode(TreeNode *p1, TreeNode *p2)
{
	assert((0!=p1) && (0!=p2));
	return (p1->val-p2->val);
}

TreeNode * InsertNode(TreeNode *pRoot, TreeNode *pNode)
{
	if (0==pNode)
		return pRoot;

	if (0==pRoot)
	{
		return pNode;
	}

	if (CmpTreeNode(pNode, pRoot)<0)
	{
		pRoot->pLeft = InsertNode(pRoot->pLeft, pNode);
		return pRoot;
	}
	else
	{
		pRoot->pRight = InsertNode(pRoot->pRight, pNode);
		return pRoot;
	}
}

void PrintTree(TreeNode *pRoot)
{
	if (0==pRoot)
		return;

	PrintTree(pRoot->pLeft);
	printf("node %p: val %c\n", pRoot, pRoot->val);
	PrintTree(pRoot->pRight);
}

void FreeTree(TreeNode *pRoot)
{
	if (0==pRoot)
		return;
	TreeNode * pLeft = pRoot->pLeft;
	TreeNode * pRight = pRoot->pRight;
	FreeTree(pLeft);
	FreeTree(pRight);
	delete pRoot;
}

int main()
{
	char numbers[] = { 'i', 'm', 'd', 'a', 'c', 'b', 'f', 'e', 'g', 'h'};
	TreeNode *pRoot = 0;
	for (unsigned i=0; i<sizeof(numbers)/sizeof(numbers[0]); ++i)
	{
		TreeNode *pNode = new TreeNode;
		pNode->val = numbers[i];
		pNode->pLeft = pNode->pRight = 0;
		pRoot = InsertNode(pRoot, pNode);
	}

	PrintTree(pRoot);

	FreeTree(pRoot);

	return 0;
}