二叉树,排序二叉树(续)

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

上一篇文章是讲了一些二叉树的一些知识,本文介绍几个二叉树常用的算法

求树的高:二叉树的高是左子树的高和右子树高的最大值再加上1,所以根据递归的定义很快就能得出来算法实现的伪代码

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;
		}
	}
}


统计树的叶子节点个数:叶子节点是孩子节点都为空的节点,要统计叶子节点的个数,可以在遍历的过程中判断节点的孩子节点是否都为空就可以了,代码如下:

int LeafCount(BLGTree& bt)
{
	int nLeafCount = 0;	//叶子节点个数
	if (bt != NULL)
	{
		LeafCount(bt->lchild);
		LeafCount(bt->rchild);
		if (bt->lchild == NULL && bt->rchild == NULL)
		{
			nLeafCount ++;
		}
	}
	return nLeafCount;
}


树的层次遍历:树的层次遍历树指从根节点开始遍历,然后每一层都是从左到右的顺序就行遍历,这样就完成了层次遍历,在遍历过程中用队列实现,具体操作入下:

1. 队列 Q 初始化;

2. 如果二叉树非空,将根指针入队;

3.  循环直到队列Q为空

      3.1 q=队列Q的队头元素出队;

      3.2 访问结点q的数据域;

      3.3 若结点q存在左孩子,则将左孩子指针入队;

      3.4 若结点q存在右孩子,则将右孩子指针入队;

具体代码如下,队列用的STL中的

void levelOrder(BLGTree &bt)
{
	deque<BLGNode *> nodeQueue;
	if (bt != NULL)
	{
		nodeQueue.push_back(bt);
		while (!nodeQueue.empty())
		{
			BLGNode* queueHead = nodeQueue.at(0);
			printf("%d\t",queueHead->data);
			nodeQueue.pop_front();
			if (queueHead->lchild)
			{
				nodeQueue.push_back(queueHead->lchild);
			}
			if (queueHead->rchild)
			{
				nodeQueue.push_back(queueHead->rchild);
			}
		}
	}
}


以上就是一些比较简单的算法,还希望大家可以补充补充!


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