设二叉树以二叉链表形式存放,用类C语言设计非递归算法判断一棵根结点为T的二叉树是否为二叉排序树。不使用栈和已有的算法,并且有详细注释
时间: 2023-06-13 08:02:42 浏览: 111
设两棵二叉树的根结点地址分别为P及Q,采用二叉链表的形式存储这二棵树上所有的结点。请编写程序,判断它们是否相似。
非递归算法判断一棵根结点为T的二叉树是否为二叉排序树,我们可以利用中序遍历的特性来判断。
中序遍历二叉排序树的结果是一个递增的有序序列,因此我们可以在中序遍历的过程中判断当前节点是否比前一个节点的值大,如果不是,则说明这棵树不是二叉排序树。
具体实现思路如下:
1. 定义一个指针cur指向当前节点,一个指针pre指向前一个节点,一个标志变量flag表示是否为第一个节点。
2. 首先将cur指针指向根节点,然后进入循环,循环条件是cur不为空或者栈不为空。每次循环开始时,先将cur指向的节点压入栈中,然后将cur指针指向其左子节点,直到cur为空。
3. 当cur为空时,从栈中弹出一个节点,判断是否为第一个节点(即pre是否为空),如果是,则将flag标志置为true,并将pre指向该节点;如果不是,则判断当前节点的值是否比pre的值大,如果不是,则说明这棵树不是二叉排序树,返回false;如果是,则将pre指向该节点。
4. 最后将cur指向其右子节点,然后继续循环。
5. 如果循环结束后,没有返回false,则说明这棵树是二叉排序树,返回true。
完整代码如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
bool isBST(TreeNode* root) {
if (root == NULL) {
return true;
}
TreeNode* cur = root;
TreeNode* pre = NULL;
bool flag = false;
while (cur != NULL || !stack_empty()) {
while (cur != NULL) {
stack_push(cur);
cur = cur->left;
}
cur = stack_pop();
if (!flag) {
flag = true;
} else if (cur->val <= pre->val) {
return false;
}
pre = cur;
cur = cur->right;
}
return true;
}
```
在代码中,我们使用了一个栈辅助实现中序遍历,stack_push表示入栈,stack_pop表示出栈,stack_empty表示判断栈是否为空。
阅读全文