验证二叉搜索树

验证二叉搜索树

提示：欲买桂花同载酒，终不似，少年游

文章目录

• 验证搜索二叉树
• • 思路
  • 方式1
  • 方式2(不正确)
  • 方式三
  • 迭代法
  • 另
  • 运行截图
• 可执行

验证搜索二叉树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

思路

这里递归的方法我相信大家应该是有一点想法的 使用递归，那么使用哪种递归方式呢？这里认为都是可以的，但是为了体现二叉搜索树的特点，这里当然是使用中序 因为之前我们就说过 中序遍历一个二叉搜索树 其中得到的结果是一个有序的序列

方式1

void InTravel(BiTree* T){if(T==NULL){return ;}InTravel(T->Lchild);result.push_back(T->data);InTravel(T->Rchild);
}

方式2(不正确)

但是这样写却不对 原因如下 尽管每一个结点都是满足根结点大于左节点 根结点小于右结点 但是若是如下这种 就会运行处这样的结果

bool InTravel2(BiTree* T){bool left;bool right; if(T->Lchild==NULL&&T->Rchild==NULL){return true;}if(T->Lchild){if(T->data>T->Lchild->data){left=InTravel2(T->Lchild);} else{cout<<"在结点"<<T->data<<"不满足条件"<<endl; return false;	}}if(T->Rchild){if(T->data<T->Rchild->data){right=InTravel2(T->Rchild);} else{cout<<"在结点"<<T->data<<"不满足条件"<<endl; return false;	}		}return left&&right;
}

方式三

这里方式三有点像线索二叉树的时候 定义一个全局遍历Pre 一直指向T的前一个结点
有点难度

BiTree* Pre=NULL; 
bool InTravel3(BiTree* T){bool left;bool right;if(T==NULL){return true;};left=InTravel3(T->Lchild);if(Pre!=NULL&&Pre->data>T->data){cout<<"方式三在结点"<<Pre->data<<"不满足条件"<<endl;return false;	}Pre=T;right=InTravel3(T->Rchild);return left&&right;
} 

迭代法

自然就是使用中序的迭代了

bool InTravel4(BiTree* T){stack<BiTree*> S;BiTree* Pre=NULL;if(T==NULL) return true;S.push(T);while(!S.empty()){//在这个判空之前肯定要先玩里面放东西 BiTree* cur=S.top();if(cur==NULL){//说明下一个结点是第二次访问了  此时再一次弹出 然后取此时的元素 S.pop();cur=S.top(); if(Pre!=NULL&&Pre->data>cur->data){cout<<"方法四在结点"<<Pre->data<<"处不匹配"<<endl;return false;}S.pop();Pre=cur; }else{S.pop();if(cur->Rchild)S.push(cur->Rchild);S.push(cur);//这里不需要判空 因为是先弹出 在加入所以不会为空 S.push(NULL);//再结点前面添加还是后面添加呢 我想应该是后面 因为只有这这样访问的时候才能先于结点察觉到此时下一个结点第二次访问了 if(cur->Lchild)S.push(cur->Lchild);	}} return true;
} 

另

本题迭代中依然可以使用一个结果集来存放遍历的 然后再进行判断是否是从小到大的

运行截图

可执行

#include<bits/stdc++.h>
typedef struct BiTree{int data;BiTree* Lchild=NULL;BiTree* Rchild=NULL; 
}BiTree;
using namespace std;
int root;
vector<int> result;
BiTree* PreCreatTree(BiTree* &T){//前序创造一个树int input; cin>>input;if(input==-1){T==NULL;return NULL;}else{T=(BiTree*)malloc(sizeof(BiTree));T->data=input;T->Lchild=PreCreatTree(T->Lchild);T->Rchild=PreCreatTree(T->Rchild);return T;}
}
void InTravel(BiTree* T){if(T==NULL){return ;}InTravel(T->Lchild);result.push_back(T->data);InTravel(T->Rchild);
}
bool InTravel2(BiTree* T){bool left;bool right; if(T->Lchild==NULL&&T->Rchild==NULL){return true;}if(T->Lchild){if(T->data>T->Lchild->data){left=InTravel2(T->Lchild);} else{cout<<"在结点"<<T->data<<"不满足条件"<<endl; return false;	}}if(T->Rchild){if(T->data<T->Rchild->data){right=InTravel2(T->Rchild);} else{cout<<"在结点"<<T->data<<"不满足条件"<<endl; return false;	}		}return left&&right;
}
//z这种方式有些像线索二叉树
BiTree* Pre=NULL; 
bool InTravel3(BiTree* T){bool left;bool right;if(T==NULL){return true;};left=InTravel3(T->Lchild);if(Pre!=NULL&&Pre->data>T->data){cout<<"方式三在结点"<<Pre->data<<"不满足条件"<<endl;return false;	}Pre=T;right=InTravel3(T->Rchild);return left&&right;
} 
bool InTravel4(BiTree* T){stack<BiTree*> S;BiTree* Pre=NULL;if(T==NULL) return true;S.push(T);while(!S.empty()){//在这个判空之前肯定要先玩里面放东西 BiTree* cur=S.top();if(cur==NULL){//说明下一个结点是第二次访问了  此时再一次弹出 然后取此时的元素 S.pop();cur=S.top(); if(Pre!=NULL&&Pre->data>cur->data){cout<<"方法四在结点"<<Pre->data<<"处不匹配"<<endl;return false;}S.pop(); Pre=cur;}else{S.pop();if(cur->Rchild)S.push(cur->Rchild);S.push(cur);//这里不需要判空 因为是先弹出 在加入所以不会为空 S.push(NULL);//再结点前面添加还是后面添加呢 我想应该是后面 因为只有这这样访问的时候才能先于结点察觉到此时下一个结点第二次访问了 if(cur->Lchild)S.push(cur->Lchild);	}} return true;
} 
void PreTravel(BiTree* T){if(T==NULL) return;cout<<T->data<<" ";PreTravel(T->Lchild);PreTravel(T->Rchild);
}
int main(){BiTree* T;cout<<"请输入创建的树的值零表示空结点"<<endl;PreCreatTree(T);PreTravel(T);cout<<endl;InTravel(T);if(InTravel4(T)){cout<<"方式四判断是一个二叉搜索树"<<endl;}else{cout<<"方式四判断不是一个二叉搜索树"<<endl;}if(InTravel3(T)){cout<<"方式三判断是一个二叉搜索树"<<endl;}else{cout<<"方式三判断不是一个二叉搜索树"<<endl;}if(InTravel2(T)){cout<<"方式二判断是一个二叉搜索树"<<endl;}else{cout<<"方式二判断不是一个二叉搜索树"<<endl;}for(int i=0;i<result.size()-1;i++){if(result[i]>result[i+1]){cout<<"方式一判断此时不是一个二叉搜索树"<<endl; cout<<"在结点"<<result[i]<<"处不能满足条件"<<endl; return 0;}} cout<<"方式一判断是一个二叉搜索树"<<endl; return 1;
}

csdn
所谓废话，关键是废话需要如何写。 我们都知道，只要有意义，那么就必须慎重考虑。 在这种困难的抉择下，本人思来想去，寝食难安。 就我个人来说，废话对我的意义，不能不说非常重大。 问题的关键究竟为何? 一般来讲，我们都必须务必慎重的考虑考虑。 而这些并不是完全重要，更加重要的问题是， 现在，解决废话的问题，是非常非常重要的。 所以， 问题的关键究竟为何? 这种事实对本人来说意义重大，相信对这个世界也是有一定意义的。