二叉搜索树(c实现)

#include<stdio.h>
#include<stdlib.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

Node *newNode(int data);
Node *insert(Node *node, int data);
int size(Node *node);
int maxDepth(Node *node);
int minValue(Node *node);
int maxValue(Node *node);
int lookup(Node *node, int target);
void printPreorder(Node *node);
void printInorder(Node *node);
void printPostorder(Node *node);
void mirror(Node *node);
void doubleTree(Node *node);
int isBST(Node *node);
int sameTree(Node *a, Node *b);
void printPaths(Node *node);
void printPathsRecur(Node *node, int path[], int pathLen);
void printArray(int ints[], int len);

int main(void) {
    Node *root = newNode(10);
    /* following is the tree after above statement
            10
          /   \
         NULL  NULL
    */
    insert(root, 5);
    insert(root, 15);
    /* 2 and 3 become left and right children of 1
               10
             /   \
            5      15
         /    \    /  \
        NULL NULL NULL NULL
    */
    insert(root, 3);
    /* 4 becomes left child of 2
                  10
               /      \
              5        15
            /   \     /  \
           3   NULL NULL  NULL
          /  \
        NULL NULL
    */
    printf("size is %d\n", size(root));
    printf("max depth is %d\n", maxDepth(root));
    printf("min value is %d\n", minValue(root));
    printf("max value is %d\n", maxValue(root));
    printf("lookup 5, can find it? %d\n", lookup(root, 100));
    printPaths(root);
    printf("preorder:");
    printPreorder(root);
    printf("\n");
    printf("midorder:");
    printInorder(root);
    printf("\n");
    printf("postorder:");
    printPostorder(root);
    printf("\n");
    free(root);
    return 0;
}

/*
create a new node
*/
Node *newNode(int data) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
};

/*
Give a binary search tree and a number, inserts a new node
with the given number in the correct place in the tree.
Returns the new root pointer which the caller should
then use (the standard trick to avoid using reference
parameters).
*/
Node *insert(Node *node, int data) {
    // 1. If the tree is empty, return a new, single node
    if(node == NULL) {
        return newNode(data);
    }
    // 2. Otherwise, recur down the tree
    if(data < node->data) {
        node->left = insert(node->left, data);
    } else {
        node->right = insert(node->right, data);
    }
    //return the (unchanged) node pointer
    return node;
}

/*
Compute the number of nodes in a tree.
*/
int size(Node *node) {
    if(node == NULL) {
        return 0;
    } else {
        return (size(node->left) + 1 + size(node->right));
    }
}

/*
Compute the "maxDepth" of a tree -- the number of nodes along
the longest path from the root node down to the farthest leaf node.
*/
int maxDepth(Node *node) {
    if(node == NULL) {
        return 0;
    }
    int lDepth = maxDepth(node->left);
    int rDepth = maxDepth(node->right);
    return lDepth > rDepth ? lDepth + 1 : rDepth + 1;
}

/*
Given a non-empty binary search tree,
return the minimum data value found in that tree.
Note that the entire tree does not need to be searched.
*/
int minValue(Node *node) {
    Node *current = node;
    while(current->left != NULL) {
        current = current->left;
    }
    return current->data;
}

/*
Given a non-empty binary search tree,
return the maximum data value found in that tree.
Note that the entire tree does not need to be searched.
*/
int maxValue(Node *node) {
    Node *current = node;
    // loop down to find the leftmost leaf
    while(current->right != NULL) {
        current = current->right;
    }
    return current->data;
}

/*
Given a binary tree, return 1 if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/
int lookup(Node *node, int target) {
    // 1. Base case == empty tree
    // in that case, the target is not found so return false
    if(node == NULL) {
        return -1;
    }
    // 2. see if found here
    if(target == node->data) {
        return 1;
    }
    // 3. otherwise recur down the correct subtree
    if(target < node->data) {
        return lookup(node->left, target);
    } else {
        return lookup(node->right, target);
    }
}

/*
Ç°Ðò(¸ù×óÓÒ)
Given a binary tree, print its
nodes according to the "bottom-up"
preorder traversal.
*/
void printPreorder(Node *node) {
    if(node == NULL) {
        return;
    }
    printf("%d--", node->data);
    printPreorder(node->left);
    printPreorder(node->right);
}

/*
ÖÐÐò(×ó¸ùÓÒ)
Given a binary tree, print its
nodes according to the "bottom-up"
midorder traversal.
*/
void printInorder(Node *node) {
    if(node == NULL) {
        return;
    }
    printInorder(node->left);
    printf("%d--", node->data);
    printInorder(node->right);
}

/*
ºóÐò(×óÓÒ¸ù)
Given a binary tree, print its
nodes according to the "bottom-up"
postorder traversal.
*/
void printPostorder(Node *node) {
    if (node == NULL) return;
    // first recur on both subtrees
    printPostorder(node->left);
    printPostorder(node->right);
    // then deal with the node
    printf("%d--", node->data);
}

/*
Change a tree so that the roles of the
left and right pointers are swapped at every node.
So the tree...
       4
      / \
     2   5
    / \
   1   3

is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(Node *node) {
    if(node == NULL) {
        return;
    }
    Node *temp;
    //do the subtree
    mirror(node->left);
    mirror(node->right);
    // swap the pointers in this node
    temp = node->left;
    node->left = node->right;
    node->right = temp;
}

/*
For each node in a binary search tree,
create a new duplicate node, and insert
the duplicate as the left child of the original node.
The resulting tree should still be a binary search tree.
So the tree...
    2
   / \
  1   3

Is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
*/
void doubleTree(Node *node) {
    struct node *oldLeft;
    if (node == NULL) return;
    // do the subtrees
    doubleTree(node->left);
    doubleTree(node->right);
    // duplicate this node to its left
    oldLeft = node->left;
    node->left = newNode(node->data);
    node->left->left = oldLeft;
}

/*
Returns 1 if a binary tree is a binary search tree.
a.  5   -> TRUE
   / \
  2   7


b.  5   -> FALSE, because the 6 is not ok to the left of the 5
   / \
  6   7


c.   5  -> TRUE
    / \
   2   7
  /
 1

d.   5  -> FALSE, the 6 is ok with the 2, but the 6 is not ok with the 5
    / \
   2   7
  / \
 1   6
*/
int isBST(Node *node) {
    if(node == NULL) {
        return 1;
    }
    if(node->left != NULL && maxValue(node->left) > node->data) {
        return -1;
    }
    if(node->right != NULL && minValue(node->right) <= node->data) {
        return -1;
    }
    if(!isBST(node->left) || !isBST(node->right)) {
        return -1;
    }
    return 1;
}

/*
Given two trees, return 1 if they are
structurally identical.
*/
int sameTree(Node *a, Node *b) {
    // 1. both empty -> true
    if (a == NULL && b == NULL) return 1;
    // 2. both non-empty -> compare them
    else if (a != NULL && b != NULL) {
        return(
                  a->data == b->data &&
                  sameTree(a->left, b->left) &&
                  sameTree(a->right, b->right)
              );
    }
    // 3. one empty, one not -> false
    else return -1;
}

/*
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.
We'll define a "root-to-leaf path" to be a sequence of nodes in
a tree starting with the root node and proceeding downward to a leaf
(a node with no children). We'll say that an empty tree contains
no root-to-leaf paths. So for example, the following tree
has exactly four root-to-leaf paths:
          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1
Root-to-leaf paths:
   path 1: 5 4 11 7
   path 2: 5 4 11 2
   path 3: 5 8 13
   path 4: 5 8 4 1
*/
void printPaths(Node *node) {
    int path[1000];
    printPathsRecur(node, path, 0);
}

/*
Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.
*/
void printPathsRecur(Node *node, int path[], int pathLen) {
    if (node == NULL) return;
    // append this node to the path array
    path[pathLen] = node->data;
    pathLen++;
    // it's a leaf, so print the path that led to here
    if (node->left == NULL && node->right == NULL) {
        printArray(path, pathLen);
    } else {
        // otherwise try both subtrees
        printPathsRecur(node->left, path, pathLen);
        printPathsRecur(node->right, path, pathLen);
    }
}

//Utility that prints out an array on a line.
void printArray(int ints[], int len) {
    int i;
    printf("Root-to-leaf paths: ");
    for (i = 0; i < len; i++) {
        printf("%d ", ints[i]);
    }
    printf("\n");
}