7 判断给定的二叉树是否是二叉排序树

二叉树是否是二叉排序树"/>

7 判断给定的二叉树是否是二叉排序树

来源刘H同学

来源刘H同学

来源刘H同学

问题描述 :

在二叉树的二叉链表存储形式建立的基础上，使用递归的程序设计方法，设计并完成判断一棵给定的二叉树是否是二叉排序树的算法。

初始条件：二叉树T。

操作结果：若T是二叉排序树，则返回true，否则返回false。

提示：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉排序树。

（4）递归遍历，左孩子的key比根节点的key小，右孩子的key比根节点的key大，一旦有不满足条件的就判定不是。

参考函数原型：

//判断是否是二叉排序树
template<class ElemType>
bool IsBST(BinaryTreeNode<ElemType> *root); //root为指向根结点的指针

方法2：

提示：

（1）首先对二叉树T进行一次中序遍历，遍历结果存放在顺序表A中

（2）针对顺序表A进行一趟冒泡排序。若交换标志不改变，则说明是一棵二叉排序树。

参考函数原型：

（1）主函数：针对顺序表A进行一趟冒泡排序，判断是否是二叉排序树

template<class ElemType>
bool IsBST(vector<ElemType> &A); //A为存放中序遍历结果的顺序表

（2）辅助函数1

//重载二叉树的中序遍历（用户函数）

template<class ElemType>
bool InOrderTraverse(BinaryTree<ElemType> &T, vector<ElemType> &A);

（3）辅助函数2

//重载二叉树的中序遍历（成员函数）

bool InOrderTraverse( BinaryTreeNode<ElemType> *root, vector<ElemType> &A, bool (*visit1)(BinaryTreeNode<ElemType> *root, vector<ElemType> &A) ) const;

（4）辅助函数3

//重写遍历的visit函数，将遍历结果依次存放在顺序表A中（为避免连锁改动，将函数名由visit改为visit1）

template<class ElemType>
bool visit1(BinaryTreeNode<ElemType> * root, vector<ElemType> &A);

输入说明 :

第一行：表示无孩子或指针为空的特殊分隔符

第二行：二叉树的层次次序序列（结点元素之间以空格分隔）（参见二叉树ADT的建立 20题）

输出说明 :

第一行：二叉树的中序遍历结果

第二行：true（是二叉排序树）/false（不是二叉排序树）

-------------------------------------------

null
E B F A D null J null null C null G null null null null I H

---------------

A,B,C,D,E,F,G,H,I,J
true

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <sstream>
#include<queue>
using namespace std;
bool flag=0;
vector<string> ans;
vector<string>pre, in, post;
vector<string>depart_string(string str)
{vector<string>ans;stringstream s(str);string temp;while (s >> temp){ans.push_back(temp);}return ans;
}
template<class ElemType>
struct BinaryTreeNode
{ElemType data;BinaryTreeNode<ElemType> *LChild, *RChild;BinaryTreeNode() : LChild(NULL), RChild(NULL) {} //构造函数1，用于构造根结点BinaryTreeNode(const ElemType &item, BinaryTreeNode<ElemType> *Lptr = NULL, BinaryTreeNode<ElemType> *Rptr = NULL) //构造函数2，用于构造其他结点//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面{LChild = Lptr;RChild = Rptr;data = item;}ElemType getData(){return data;   //取得结点中的数据}void SetLChild( BinaryTreeNode<ElemType> *link ){LChild = link;    //修改结点的左孩子域}void SetRChild( BinaryTreeNode<ElemType> *link ){RChild = link;    //修改结点的右孩子域}void SetData( ElemType value ){data = value;    //修改结点的data域}BinaryTreeNode<ElemType> * GetLChild() const{return LChild;   //获取左孩子结点}BinaryTreeNode<ElemType> * GetRChild() const{return RChild;   //获取左孩子结点}
};
//二叉树
template<class ElemType>
class BinaryTree
{
private:BinaryTreeNode<ElemType> *root;   // 头指void BinaryTreeDestroy_Cursive( BinaryTreeNode<ElemType> *T ) //销毁树（递归准备，private）{if(T){BinaryTreeDestroy_Cursive(T->LChild);BinaryTreeDestroy_Cursive(T->RChild);free(T);T=NULL;}}
public://无参数的构造函数BinaryTree():root(NULL) {}//带参数的构造函数BinaryTree(const ElemType &item){root = new BinaryTreeNode<ElemType>(item);}//生成树void makeBinaryTree( const ElemType &item, BinaryTree &left, BinaryTree &right);//拷贝构造函数//LinkQueue(LinkQueueList<ElemType> &Queue);//析构函数~BinaryTree(){BinaryTreeDestroy(root);}//重载函数:赋值//LinkList<ElemType>& operator=(LinkList<ElemType> &List);//销毁树void BinaryTreeDestroy( BinaryTreeNode<ElemType> *p){BinaryTreeDestroy_Cursive(p);}//销毁子树void ChildDestroy(int flag);//返回二叉树结点的个数int BinaryTreeSize( BinaryTreeNode<ElemType> *T ) const;//判断二叉树是否为空bool BinaryTreeisEmpty() const{return root == NULL;}//获取根结点元素值ElemType GetRootData() const{return root->data;}//bool Location(ElemType &x, BinaryTreeNode<ElemType> * &location);//设置根结点void SetRoot(BinaryTreeNode<ElemType> * p){root = p;}//获取根结点BinaryTreeNode<ElemType> * GetRoot() const{return root;}//前序遍历void PreOrderTraverse( BinaryTreeNode<ElemType> *T,int &num) const;  //前序遍历（递归）//num的初始值为0，作用为控制输出格式（最后1个结点后不加“，”）//中序遍历void InOrderTraverse( BinaryTreeNode<ElemType> *T,int &num) const;  //中序遍历（递归）//后序遍历void PostOrderTraverse( BinaryTreeNode<ElemType> *T,int &num) const;  //后序遍历（递归）void LayerOrderTraverse(BinaryTreeNode<ElemType>*T,int &num)const;void GetParent_Cursive(BinaryTreeNode<ElemType> * parent, ElemType &x, BinaryTreeNode<ElemType> * &result) const;void Location_Cursive( BinaryTreeNode<ElemType> * root, const ElemType &x, BinaryTreeNode<ElemType> * &location );//建立二叉树的存储结构BinaryTreeNode<ElemType>* CreateBinaryTree(vector<ElemType> &x, ElemType &empty, int &n);int GetBinaryTreeHeight( BinaryTreeNode<ElemType> *root )const;void Location_Child( BinaryTreeNode<ElemType> *T, ElemType &x, int flag, BinaryTreeNode<ElemType> * &location ) const;bool ChildTreeDestroy(BinaryTree<ElemType>&T,BinaryTreeNode<ElemType> *root, int flag);bool Insert_ChildTree( BinaryTreeNode<ElemType> * parent, BinaryTreeNode<ElemType> * child, int flag );void Assign_NodeData( BinaryTreeNode<ElemType> * root, ElemType &x, ElemType &value );BinaryTreeNode<ElemType> * Get_Sibling( BinaryTreeNode<ElemType> *parent, BinaryTreeNode<ElemType> *location, int flag ) const;int CountDegreeTwo( BinaryTreeNode<ElemType> *T ) const;
};
//中序遍历
template<class ElemType>
void BinaryTree<ElemType>::InOrderTraverse(BinaryTreeNode<ElemType>* T, int&num) const
{if (T){InOrderTraverse(T->GetLChild(), num );if(num==0){cout<<T->data;num++;ans.push_back(T->data);}else{cout<<','<<T->data;ans.push_back(T->data);num++;}InOrderTraverse(T->GetRChild(), num );}
}
//叉树的存储结构 (外壳）
template<class ElemType>
void CreateTree(BinaryTree<ElemType> &T, ElemType &str, ElemType &empty)
{ElemType tmp;vector<ElemType> t;stringstream input_T(str);while(input_T >> tmp){t.push_back(tmp);}BinaryTreeNode<ElemType> *root;int num = 0;root = T.CreateBinaryTree(t, empty, num);T.SetRoot(root);
}
//建立二叉树的存储结构 (递归部分，成员函数）
template<class ElemType>
BinaryTreeNode<ElemType>* BinaryTree<ElemType>::CreateBinaryTree(vector<ElemType> &x, ElemType &empty, int &n)
{ElemType ch = x[n];n++;if (ch == empty){return NULL;}else{BinaryTreeNode<ElemType> *Node = new BinaryTreeNode<ElemType>;Node->data = ch;Node->LChild = CreateBinaryTree(x, empty, n);Node->RChild = CreateBinaryTree(x, empty, n);return Node;}
}
template<class ElemType>
void createnode(BinaryTreeNode<ElemType>*t,ElemType x)//创建一个结点
{t->SetData(x);t->SetLChild(NULL);t->SetRChild(NULL);
}
template<class ElemType>
void CreateTree_Layer(BinaryTree<ElemType>& T, ElemType& str, ElemType& empty)//层次结构建立二叉树
{vector<string>s = depart_string(str);queue<BinaryTreeNode<ElemType>*>q;int b = 0;BinaryTreeNode<ElemType>* temp = new BinaryTreeNode<ElemType>;;createnode(temp, s[b]);q.push(temp);T.SetRoot(temp);while (!q.empty()){BinaryTreeNode<ElemType>* x = q.front();q.pop();if (b == s.size() - 1)//关键点 ①：他最后的空指针有可能缺省{x->SetLChild(NULL);x->SetRChild(NULL);continue;}if (s[++b] != empty){BinaryTreeNode<ElemType>* t = new BinaryTreeNode<ElemType>;;createnode(t, s[b]);x->SetLChild(t);q.push(t);}else{x->SetLChild(NULL);}if (b == s.size() - 1)//关键点 ②：他最后的空指针有可能缺省 可能只写了最后一个结点的左边空指针，没有写右边空指针{x->SetRChild(NULL);continue;}if (s[++b] != empty){BinaryTreeNode<ElemType>* t = new BinaryTreeNode<ElemType>;;createnode(t, s[b]);x->SetRChild(t);q.push(t);}else{x->SetRChild(NULL);}}
}
int main()
{string empty, str;getline(cin, empty);getline(cin, str);BinaryTree<string>T;CreateTree_Layer(T, str, empty);int n=0;T.InOrderTraverse(T.GetRoot(),n);cout<<endl;for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(ans[i]>ans[j]){flag=1;break;}}}if(flag==1){cout<<"false";}else{cout<<"true";}return 0;}