设二叉树以二叉链表形式存放,用类C语言设计非递归算法判断一棵根结点为T的二叉树是否为二叉排序树。不使用栈,并且有详细注释
时间: 2023-06-13 11:02:37 浏览: 100
写一算法,判断一棵二叉树是否是一棵二叉排序树。
非递归算法判断一棵根结点为T的二叉树是否为二叉排序树,可以使用中序遍历的方式实现。由于二叉排序树的中序遍历结果是一个有序序列,因此只需要在中序遍历时判断当前节点的值是否小于等于前一个节点的值,即可判断二叉树是否为二叉排序树。
具体实现步骤如下:
1. 定义一个指针p指向当前节点,一个指针pre指向前一个节点,初始值为NULL。
2. 对于每个节点,先将其左子树中的所有节点入栈,直到左子树为空。
3. 弹出栈顶元素,即为当前节点,判断当前节点的值是否小于等于前一个节点的值,如果是,则不是二叉排序树;如果不是,则将前一个节点指针pre指向当前节点。
4. 将当前节点的右子树中的所有节点入栈,重复步骤2和3,直到所有节点都被遍历。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int isBST(TreeNode* root) {
TreeNode* p = root; // 当前节点指针
TreeNode* pre = NULL; // 前一个节点指针
int flag = 1; // 是否为二叉排序树的标志
while (p != NULL) {
// 将左子树中的所有节点入栈
while (p != NULL) {
// 将当前节点入栈
// 这里用链表的方式实现栈,栈顶元素为p,栈顶指针为next
next = (struct ListNode*)malloc(sizeof(struct ListNode));
next->val = p;
next->next = stack;
stack = next;
p = p->left;
}
// 弹出栈顶元素,即为当前节点
p = stack->val;
stack = stack->next;
// 判断当前节点的值是否小于等于前一个节点的值
if (pre != NULL && p->val <= pre->val) {
flag = 0;
break;
}
// 将前一个节点指针pre指向当前节点
pre = p;
// 将右子树中的所有节点入栈
p = p->right;
}
return flag;
}
```
注意:这里使用了链表实现栈,栈顶元素为p,栈顶指针为next。这样可以避免使用数组实现栈时需要预先确定栈的大小的问题。
阅读全文