二叉树,排序二叉树

长平狐 发布于 2013/12/25 17:25
阅读 142
收藏 0

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相对复杂的,很多人甚至看不懂算法的意思,不能理解。其实一开始接触这些东西还是挺晕的,不过你多看几遍,上机实现可能你就会觉得没那么复杂。因为你最后会发现,这些数据结构对于提高程序设计的能力有很大帮助,也是软件开发中必不可少的。

     二叉树表示方法一般有两种,第一种一般是顺序存储结构,将二叉树中的节点信息存入一个一维数组中。

第二种也是比较常用的方法,用链表表示,其节点有值,左子树指针和右子树指针,有时候为了算法方便,也许会有双亲节点指针。其结构一般如下:

//BLG树的链表表示形式
typedef struct BLGNode 
{
	int data;			//数据域
	struct BLGNode *lchild;	//左孩子
	struct BLGNode *rchild;	//右孩子
}BLGNode,* BLGTree;


这里没有用到泛型,就用了整型值作为代表。

二叉排序树也是一种二叉树,也叫做二叉搜索树,是一种动态的搜索结构,它的左子树的节点的值小于根节点的值,右子树节点的值大于根节点的值,左右子树也分别是一棵二叉排序树。它的中序遍历就是值得升序排序。所以这种树叫做排序树。

下面就是相关的实现代码,

void initBTree(struct BLGNode **bt)
{
	*bt = NULL;
}

bool emptyBLGTree(BLGTree bt)
{
	if (bt != NULL)
	{
		return true;
	}
	return 0;
}

int blgtreeDepth(BLGTree &bt)
{
	//如果树为空,则返回0结束递归
	if (NULL == bt)
	{
		return 0;
	}
	else
	{
		int depth1 = blgtreeDepth(bt->lchild);	//左子树深度
		int depth2 = blgtreeDepth(bt->rchild);	//右子树深度
		if (depth1 > depth2)
		{
			return depth1 + 1;
		}
		else
		{
			return depth2 + 1;
		}
	}
}

void ClearBLGTree(BLGTree *bt)
{
	//
	if (*bt != NULL)
	{
		ClearBLGTree(&((*bt)->lchild));
		ClearBLGTree(&((*bt)->rchild));
		free(*bt);
		*bt = NULL;
	}
	return;
}

void preOrder(BLGTree &bt)
{
	//
	if (bt != NULL)
	{
		printf("%d\t",bt->data);
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
	return;
}

void inOrder(BLGTree &bt)
{
	if (bt != NULL)
	{
		inOrder(bt->lchild);
		printf("%d\t",bt->data);
		inOrder(bt->rchild);
	}
	return;
}

void postOrder(BLGTree &bt)
{
	if (bt != NULL)
	{
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		printf("%d\t",bt->data);
	}
	return;
}

int InsertBLG(BLGTree& bt,int e)
{
	//为新增的一个节点分配空间
	BLGNode* p = (BLGNode *)malloc(sizeof(BLGNode));
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;

	if (bt == NULL)
	{
		bt = p;
		return 1;
	}
	else
	{
		if (e < bt->data)
		{
			InsertBLG(bt->lchild,e);	//插入到左子树
		}
		else
		{
			InsertBLG(bt->rchild,e);	//插入到右子树
		}
		return 1;
	}
	return 0;
}

void CreateBLGTree(BLGTree& bt,int* value,int cnt)
{
	int i = 0;
	initBTree(&bt);		//先把树根置为空
	for (;i < cnt; i ++)
	{
		InsertBLG(bt,value[i]);
	}

	return;
}


上面的代码经过测试可用,如果还需要什么地方改进,大家都可以讨论。


原文链接:http://blog.csdn.net/zhouxuguang236/article/details/7920639
加载中
返回顶部
顶部