二叉搜索树的前序遍历序列
将二叉树画出来，得到其前序遍历序列，争取发现一些规律，发现规律后就属于实现问题
观察该序列，发现，根节点在第一个位置上，其后左子树都小于根节点，右子树大于该节点
根节点的左右子树相当于另一颗树，可以用同样的方法得到
故
bool verifyPreorderSequence(int *s,int length)
{
if(s == NULL || length <= 0)//判断返回条件
return false;
int root = s[0];//根节点
int i = 1;
for(;i < length;++i)//找到左子树序列
if (s[i] > root) break;
for(int j = i;j < length;++j)//右子树序列中如果有一个节点小于根节点，说明不是二叉树的前序序列
if(s[j] < root)
return false;
bool left = true;
if(i > 1) //从大于1开始，是因为咱们在序列s[1]开始比较
left = verifyPreorderSequence(s + 1,i - 1);
bool right = true;
if(i < length)
right = verifyPreorderSequence(s + i,length - i);//s + i 是右子树序列，length - i 是序列大小
return (left && right);
}
相应的可以判断某整数数组是否是某二叉搜索树的后续遍历序列此时根节点在序列的最后一位左子树都比根节点小右子树相应都大于根节点
bool verifySequenceOfBST(int *s,int length){if(s == NULL || length <= 0)return false;int root = s[length - 1];int i = 0;for(;i < length - 1;++i)if(s[i] > root) break;int j = i;for(; j < length - 1;++j)if(s[j] < root)return false;bool left = true;if(i > 0)left = verifySequenceOfBST(s,i);bool right = true;if(i < length - 1)right = verifySequenceOfBST(s + i,length - i - 1);//length - i - 1是右子树的大小return (left && right);}
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。