#include
#include
#include
#define MINUS_INFINITY -1000000000
#define PLUS_INFINITY 1000000000
typedef struct _node {
int key;
struct _node *L;
struct _node *R;
} BSTnode;
typedef BSTnode *BST;
/*** The following few functions are not part of the assignment. These
are implemented in order to generate valid inputs to buildBST.
***/
BST insert ( BST T, int x, int *size )
{
BSTnode *p, *q;
p = T; q = NULL;
while (p) {
if (p -> key == x) return T;
q = p;
if (x < p -> key) p = p -> L; else p = p -> R;
}
++(*size);
p = (BSTnode *)malloc(sizeof(BSTnode));
p -> key = x; p -> L = p -> R = NULL;
if (q == NULL) return p;
if (x < q -> key) q -> L = p; else q -> R = p;
return T;
}
BST buildOrigBST ( int n )
{
int size = 0;
BST T = NULL;
while (size < n) T = insert(T, 100 + rand() % 900, &size);
return T;
}
void storePreorder ( BST T, int *A, int *i )
{
if (T == NULL) return;
A[(*i)++] = T -> key;
storePreorder(T -> L, A, i);
storePreorder(T -> R, A, i);
}
void destroyTree ( BST T )
{
if (T == NULL) return;
destroyTree(T -> L);
destroyTree(T -> R);
free(T);
}
/*** End of the extra functions ***/
/*** This is the O(n log n)-time reconstruction of the tree from the
preorder listing, as given in the assignment statement. The space
requirement is O(h(T)). But h(T) can be Theta(n), so the worst-case
space requirement is O(n).
The function is commented, because a linear-time function is used
for the purpose of reconstruction.
***/
/***
BST buildBST ( int A[], int n )
{
BST T;
int l, r, m;
if (n == 0) return NULL;
T = (BSTnode *)malloc(sizeof(BSTnode));
T -> key = A[0];
if (n == 1) {
l = r = 0;
} else {
if (A[1] > A[0]) {
l = 0; r = n - 1;
} else if (A[n-1] < A[0]) {
l = n - 1; r = 0;
} else {
l = 1; r = n - 1;
while (r != l + 1) {
m = (l + r) / 2;
if (A[m] < A[0]) l = m; else r = m;
}
r = n - l - 1;
}
}
T -> L = buildBST(A+1,l);
T -> R = buildBST(A+l+1,r);
return T;
}
***/
/*** This is an O(n)-time and O(n)-space reconstruction algorithm. It
simulates the preorder traversal while creating the tree itself.
The space requirement can be reduced to O(h(T)) by implementing
the stacks as doubly linked lists. But since h(T) can be Theta(n),
this leads to no theoretical improvements in the worst-case space
complexity.
***/
BST buildBST ( int A[], int n )
{
BST *S; /* Pointer stack simulating the recursion stack during preorder traversal */
BST *LL; /* Another stack storing the last left turn (the parent) before reaching a node */
int top; /* Index of the top in the two stacks */
BST T; /* The root pointer to be returned */
BST p, q; /* Running pointers */
int i;
if (n == 0) return NULL;
S = (BST *)malloc(n * sizeof(BST));
LL = (BST *)malloc(n * sizeof(BST));
/* Create the root node */
T = (BST)malloc(sizeof(BSTnode));
T -> key = A[0]; T -> L = T -> R = NULL;
/* Initialize S and LL to one-element stacks */
top = 0;
S[top] = T; /* the freshly created root */
LL[top] = NULL; /* no left turn made so far */
/* A child of p is created in each iteration of the following loop */
p = T;
/* Loop for creating the nodes storing A[1], A[2], ..., A[n-1] */
for (i=1; i key) {
/* The key must be stored in the left child of p */
p -> L = (BST)malloc(sizeof(BSTnode)); /* Allocate memory */
++top; LL[top] = p; /* Case of a left turn */
p = S[top] = p -> L; /* Go to the created node */
p -> key = A[i]; p -> L = p -> R = NULL; /* Populate the new node */
} else {
/* The key is to be stored in the right child of a node, but of
which node? The search for this appropriate node v is based
upon the following observations.
(a) the right child of v must be NULL at this point
(b) the new key A[i] must be larger than v -> key
(c) v is the most distant from the current node p, among all
the nodes on the root-to-p path, which satisfy (a) and (b) */
while (1) {
/* A right turn violates (a), so we keep on looking at left
turns made so far. We keep on repeating until (b) fails
or no previous left turn exists. */
q = LL[top];
if ((q == NULL) || (A[i] < q -> key)) break;
while (S[top] != q) --top;
}
/* Now the appropriate node is found, whose right child will
store A[i] */
p = S[top];
p -> R = (BST)malloc(sizeof(BSTnode)); /* Allocate memory */
++top; p = S[top] = p -> R; /* Go to the new right child */
LL[top] = LL[top-1]; /* This is a case of right turn, so copy the previous left turn */
p -> key = A[i]; p -> L = p -> R = NULL; /* Populate the new node */
}
}
free(S); free(LL);
return T;
}
int isBST ( BST T, int l, int r )
{
int childIsBST;
if (T == NULL) return 1;
if ((T -> key < l) || (T -> key > r)) return 0;
childIsBST = isBST(T -> L, l, T -> key);
if (childIsBST == 0) return 0;
childIsBST = isBST(T -> R, T -> key, r);
return childIsBST;
}
void preorder ( BST T, int *i )
{
if (T == NULL) return;
if (*i == 0) printf(" ");
printf(" %d", T -> key);
++(*i);
if (*i == 19) {
printf("\n");
*i = 0;
}
preorder(T -> L, i);
preorder(T -> R, i);
}
BSTnode *inorderSuccessor ( BST T, int x )
{
BSTnode *p, *q;
q = NULL;
p = T;
while (p) {
if (p -> key == x) break;
if (x < p -> key) {
q = p;
p = p -> L;
} else {
p = p -> R;
}
}
if (p == NULL) return NULL;
if (p -> R) {
q = p -> R;
while (q -> L != NULL) q = q -> L;
}
return q;
}
/* Let x be found at a node pointed to by p. If p has a left child, the
successor is stored at the left child. Otherwise if p has a right child,
the successor is stored at that right child. Finally, if p is a leaf
node, the successor is stored in the node corresponding to the last
left turn with a non-empty right subtree. */
BSTnode *preorderSuccessor ( BST T, int x )
{
BSTnode *p, *q;
q = NULL;
p = T;
while (p) {
if (p -> key == x) break;
if (x < p -> key) {
if (p -> R) q = p -> R;
p = p -> L;
} else {
p = p -> R;
}
}
if (p == NULL) return NULL;
if (p -> L) q = p -> L;
else if (p -> R) q = p -> R;
return q;
}
int main ( int argc, char *argv[] )
{
int n, i, x;
BST T, p;
int *A;
if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
printf(" n = %d\n\n", n);
srand((unsigned int)time(NULL));
T = buildOrigBST(n);
A = (int *)malloc(n * sizeof(int));
i = 0; storePreorder(T,A,&i);
printf("+++ Array storing preorder listing of keys\n");
for (i=0; i key);
p = T;
while (p -> R) {
if ((p -> L) && (rand() % 2)) p = p -> L;
else p = p -> R;
}
x = p -> key; p = inorderSuccessor(T,x);
if (p == NULL)
printf(" Inorder successor of %d does not exist\n", x);
else
printf(" Inorder successor of %d is %d\n", x, p -> key);
p = T;
while (p -> R) p = p -> R;
x = p -> key; p = inorderSuccessor(T,x);
if (p == NULL)
printf(" Inorder successor of %d does not exist\n\n", x);
else
printf(" Inorder successor of %d is %d\n\n", x, p -> key);
x = A[rand() % n]; p = preorderSuccessor(T, x);
if (p == NULL)
printf(" Preorder successor of %d does not exist\n", x);
else
printf(" Preorder successor of %d is %d\n", x, p -> key);
p = T;
while ((p -> L) || (p -> R)) {
if (p -> R == NULL) p = p -> L;
else if (p -> L == NULL) p = p -> R;
else p = (rand() % 2) ? p -> L : p -> R;
}
x = p -> key; p = preorderSuccessor(T, x);
if (p == NULL)
printf(" Preorder successor of %d does not exist\n", x);
else
printf(" Preorder successor of %d is %d\n", x, p -> key);
x = A[n-1]; p = preorderSuccessor(T, x);
if (p == NULL)
printf(" Preorder successor of %d does not exist\n", x);
else
printf(" Preorder successor of %d is %d\n", x, p -> key);
exit(0);
}