• 7 判断给定的二叉树是否是二叉排序树---来源刘H同学


    来源刘H同学

    来源刘H同学

    来源刘H同学

    问题描述 :

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

    初始条件:二叉树T。

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

    提示:

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

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

    参考函数原型:

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

    方法2:

    提示:

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

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

    参考函数原型:

    (1)主函数:针对顺序表A进行一趟冒泡排序,判断是否是二叉排序树

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

    (2)辅助函数1

    //重载二叉树的中序遍历(用户函数)

    template
    bool InOrderTraverse(BinaryTree &T, vector &A);

    (3)辅助函数2

    //重载二叉树的中序遍历(成员函数)

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

    (4)辅助函数3

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

    template
    bool visit1(BinaryTreeNode * root, vector &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

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. using namespace std;
    12. bool flag=0;
    13. vector ans;
    14. vectorpre, in, post;
    15. vectordepart_string(string str)
    16. {
    17. vectorans;
    18. stringstream s(str);
    19. string temp;
    20. while (s >> temp)
    21. {
    22. ans.push_back(temp);
    23. }
    24. return ans;
    25. }
    26. template<class ElemType>
    27. struct BinaryTreeNode
    28. {
    29. ElemType data;
    30. BinaryTreeNode *LChild, *RChild;
    31. BinaryTreeNode() : LChild(NULL), RChild(NULL) {} //构造函数1,用于构造根结点
    32. BinaryTreeNode(const ElemType &item, BinaryTreeNode *Lptr = NULL, BinaryTreeNode *Rptr = NULL) //构造函数2,用于构造其他结点
    33. //函数参数表中的形参允许有默认值,但是带默认值的参数需要放后面
    34. {
    35. LChild = Lptr;
    36. RChild = Rptr;
    37. data = item;
    38. }
    39. ElemType getData()
    40. {
    41. return data; //取得结点中的数据
    42. }
    43. void SetLChild( BinaryTreeNode *link )
    44. {
    45. LChild = link; //修改结点的左孩子域
    46. }
    47. void SetRChild( BinaryTreeNode *link )
    48. {
    49. RChild = link; //修改结点的右孩子域
    50. }
    51. void SetData( ElemType value )
    52. {
    53. data = value; //修改结点的data域
    54. }
    55. BinaryTreeNode * GetLChild() const
    56. {
    57. return LChild; //获取左孩子结点
    58. }
    59. BinaryTreeNode * GetRChild() const
    60. {
    61. return RChild; //获取左孩子结点
    62. }
    63. };
    64. //二叉树
    65. template<class ElemType>
    66. class BinaryTree
    67. {
    68. private:
    69. BinaryTreeNode *root; // 头指
    70. void BinaryTreeDestroy_Cursive( BinaryTreeNode *T ) //销毁树(递归准备,private)
    71. {
    72. if(T)
    73. {
    74. BinaryTreeDestroy_Cursive(T->LChild);
    75. BinaryTreeDestroy_Cursive(T->RChild);
    76. free(T);
    77. T=NULL;
    78. }
    79. }
    80. public:
    81. //无参数的构造函数
    82. BinaryTree():root(NULL) {}
    83. //带参数的构造函数
    84. BinaryTree(const ElemType &item)
    85. {
    86. root = new BinaryTreeNode(item);
    87. }
    88. //生成树
    89. void makeBinaryTree( const ElemType &item, BinaryTree &left, BinaryTree &right);
    90. //拷贝构造函数
    91. //LinkQueue(LinkQueueList &Queue);
    92. //析构函数
    93. ~BinaryTree()
    94. {
    95. BinaryTreeDestroy(root);
    96. }
    97. //重载函数:赋值
    98. //LinkList& operator=(LinkList &List);
    99. //销毁树
    100. void BinaryTreeDestroy( BinaryTreeNode *p)
    101. {
    102. BinaryTreeDestroy_Cursive(p);
    103. }
    104. //销毁子树
    105. void ChildDestroy(int flag);
    106. //返回二叉树结点的个数
    107. int BinaryTreeSize( BinaryTreeNode *T ) const;
    108. //判断二叉树是否为空
    109. bool BinaryTreeisEmpty() const
    110. {
    111. return root == NULL;
    112. }
    113. //获取根结点元素值
    114. ElemType GetRootData() const
    115. {
    116. return root->data;
    117. }
    118. //bool Location(ElemType &x, BinaryTreeNode * &location);
    119. //设置根结点
    120. void SetRoot(BinaryTreeNode * p)
    121. {
    122. root = p;
    123. }
    124. //获取根结点
    125. BinaryTreeNode * GetRoot() const
    126. {
    127. return root;
    128. }
    129. //前序遍历
    130. void PreOrderTraverse( BinaryTreeNode *T,int &num) const; //前序遍历(递归)//num的初始值为0,作用为控制输出格式(最后1个结点后不加“,”)
    131. //中序遍历
    132. void InOrderTraverse( BinaryTreeNode *T,int &num) const; //中序遍历(递归)
    133. //后序遍历
    134. void PostOrderTraverse( BinaryTreeNode *T,int &num) const; //后序遍历(递归)
    135. void LayerOrderTraverse(BinaryTreeNode*T,int &num)const;
    136. void GetParent_Cursive(BinaryTreeNode * parent, ElemType &x, BinaryTreeNode * &result) const;
    137. void Location_Cursive( BinaryTreeNode * root, const ElemType &x, BinaryTreeNode * &location );
    138. //建立二叉树的存储结构
    139. BinaryTreeNode* CreateBinaryTree(vector &x, ElemType &empty, int &n);
    140. int GetBinaryTreeHeight( BinaryTreeNode *root )const;
    141. void Location_Child( BinaryTreeNode *T, ElemType &x, int flag, BinaryTreeNode * &location ) const;
    142. bool ChildTreeDestroy(BinaryTree&T,BinaryTreeNode *root, int flag);
    143. bool Insert_ChildTree( BinaryTreeNode * parent, BinaryTreeNode * child, int flag );
    144. void Assign_NodeData( BinaryTreeNode * root, ElemType &x, ElemType &value );
    145. BinaryTreeNode * Get_Sibling( BinaryTreeNode *parent, BinaryTreeNode *location, int flag ) const;
    146. int CountDegreeTwo( BinaryTreeNode *T ) const;
    147. };
    148. //中序遍历
    149. template<class ElemType>
    150. void BinaryTree::InOrderTraverse(BinaryTreeNode* T, int&num) const
    151. {
    152. if (T)
    153. {
    154. InOrderTraverse(T->GetLChild(), num );
    155. if(num==0)
    156. {
    157. cout<data;
    158. num++;
    159. ans.push_back(T->data);
    160. }
    161. else
    162. {
    163. cout<<','<data;
    164. ans.push_back(T->data);
    165. num++;
    166. }
    167. InOrderTraverse(T->GetRChild(), num );
    168. }
    169. }
    170. //叉树的存储结构 (外壳)
    171. template<class ElemType>
    172. void CreateTree(BinaryTree &T, ElemType &str, ElemType &empty)
    173. {
    174. ElemType tmp;
    175. vector t;
    176. stringstream input_T(str);
    177. while(input_T >> tmp)
    178. {
    179. t.push_back(tmp);
    180. }
    181. BinaryTreeNode *root;
    182. int num = 0;
    183. root = T.CreateBinaryTree(t, empty, num);
    184. T.SetRoot(root);
    185. }
    186. //建立二叉树的存储结构 (递归部分,成员函数)
    187. template<class ElemType>
    188. BinaryTreeNode* BinaryTree::CreateBinaryTree(vector &x, ElemType &empty, int &n)
    189. {
    190. ElemType ch = x[n];
    191. n++;
    192. if (ch == empty)
    193. {
    194. return NULL;
    195. }
    196. else
    197. {
    198. BinaryTreeNode *Node = new BinaryTreeNode;
    199. Node->data = ch;
    200. Node->LChild = CreateBinaryTree(x, empty, n);
    201. Node->RChild = CreateBinaryTree(x, empty, n);
    202. return Node;
    203. }
    204. }
    205. template<class ElemType>
    206. void createnode(BinaryTreeNode*t,ElemType x)//创建一个结点
    207. {
    208. t->SetData(x);
    209. t->SetLChild(NULL);
    210. t->SetRChild(NULL);
    211. }
    212. template<class ElemType>
    213. void CreateTree_Layer(BinaryTree& T, ElemType& str, ElemType& empty)//层次结构建立二叉树
    214. {
    215. vectors = depart_string(str);
    216. queue*>q;
    217. int b = 0;
    218. BinaryTreeNode* temp = new BinaryTreeNode;;
    219. createnode(temp, s[b]);
    220. q.push(temp);
    221. T.SetRoot(temp);
    222. while (!q.empty())
    223. {
    224. BinaryTreeNode* x = q.front();
    225. q.pop();
    226. if (b == s.size() - 1)//关键点 ①:他最后的空指针有可能缺省
    227. {
    228. x->SetLChild(NULL);
    229. x->SetRChild(NULL);
    230. continue;
    231. }
    232. if (s[++b] != empty)
    233. {
    234. BinaryTreeNode* t = new BinaryTreeNode;;
    235. createnode(t, s[b]);
    236. x->SetLChild(t);
    237. q.push(t);
    238. }
    239. else
    240. {
    241. x->SetLChild(NULL);
    242. }
    243. if (b == s.size() - 1)//关键点 ②:他最后的空指针有可能缺省 可能只写了最后一个结点的左边空指针,没有写右边空指针
    244. {
    245. x->SetRChild(NULL);
    246. continue;
    247. }
    248. if (s[++b] != empty)
    249. {
    250. BinaryTreeNode* t = new BinaryTreeNode;;
    251. createnode(t, s[b]);
    252. x->SetRChild(t);
    253. q.push(t);
    254. }
    255. else
    256. {
    257. x->SetRChild(NULL);
    258. }
    259. }
    260. }
    261. int main()
    262. {
    263. string empty, str;
    264. getline(cin, empty);
    265. getline(cin, str);
    266. BinaryTreeT;
    267. CreateTree_Layer(T, str, empty);
    268. int n=0;
    269. T.InOrderTraverse(T.GetRoot(),n);
    270. cout<
    271. for(int i=0;i-1;i++)
    272. {
    273. for(int j=i+1;j
    274. {
    275. if(ans[i]>ans[j])
    276. {
    277. flag=1;
    278. break;
    279. }
    280. }
    281. }
    282. if(flag==1)
    283. {
    284. cout<<"false";
    285. }
    286. else
    287. {
    288. cout<<"true";
    289. }
    290. return 0;
    291. }

  • 相关阅读:
    LeetCode 热题 100 | 图论(二)
    什么是50ETF期权开户条件,怎么开期权交易权限?
    【JavaWeb】数据库连接池
    面试计算机网络八股文十问十答第十期
    数据结构与算法 | 图(Graph)
    欧盟消费品重金属含量法规简介
    springboot+vue+elementUI 公司财务固定资产管理系统#毕业设计
    【复杂网络】关于复杂网络中的动力学系统重构的文献资料整理
    win11安装anaconda, tenserflow gpu 版本 ,cuda toolkit ,cudnn
    大数据-玩转数据-Flink SQL编程实战 (热门商品TOP N)
  • 原文地址:https://blog.csdn.net/Ultravioletrays/article/details/126799781