CWYAlpha

Just another WordPress.com site

Thought this was cool: 判断整数序列是不是二叉查找树(BST)的后序遍历结果

leave a comment »


这里沿用传统二叉查找树(BST)的概念:所有左子树都小于根,右子树都大于根。(不止是直接孩子,还有间接孩子!)

现在给出一个整数序列,要求判断它是否是一棵二叉查找树BST的后序遍历结果。

如果去掉BST这个条件,我们一般是不能只根据后序遍历结果来确定某一棵树的。

有了BST这个条件后,我们可以这么做:

定义如下递归函数头:

int judge(int* arr, int start, int end)

(1)另root = end-1,则arr[root]为从start开始,end结束的子树的根(后序遍历么!)

(2)我们另i从start开始,一直++,直到碰到第一个arr[i]大于arr[root]的,那么此时的i已经位于右子树了。从start~i-1是左子树。

(3)显然从i~end-2是右子树,我们检查这段arr[j],如果有发现<arr[root]的,直接返回false。(右子树必须都大于根!)

(4)递归检查左子树 judge(arr, start, i-1) 和右子树 judge(arr, i, end-2)。如果某一个judge返回0,那么返回0,两个都1返回1。

(5)如果start==end时候,或者arr==NULL时(空树也是BST的一种!),可以直接返回1。

好了,代码如下:

#include <stdio.h>

int judge(int* arr, int start, int end)
{
	if(arr==NULL || start==end)
	{
		return 1;
	}else
	{
		// Find left sub tree(all small than root)
		int root = end-1;
		int i = start;
		int j = 0;
		for(i=start;i<root;i++)
		{
			if(arr[i]>arr[root])
			{
				break;
			}
		}
		// Check if right sub tree all bigger than root, else is fake BST
		j = i;
		for(;j<root;j++)
		{
			if(arr[j]<arr[root])
			{
				return 0;
			}
		}
		// Check left sub tree
		if(0==judge(arr, start, i-1))
		{
			return 0;
		}
		// Check right sub tree
		if(0==judge(arr, i, end-2))
		{
			return 0;
		}
		return 1;
	}	
}

int main()
{
	//int arr[7] = {5, 7, 6, 9, 11, 10, 8}; // Yes
	int arr[4] = {7, 4, 6, 5}; // Not
	printf("Is BST Post: %d \n", judge(arr, 0, sizeof(arr)/sizeof(int)-1));
	return 0;
}

from 四号程序员四号程序员: http://www.coder4.com/archives/3271

Written by cwyalpha

六月 4, 2012 在 2:28 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: