DOC

Binary search tree demo program

By Teresa Adams,2014-12-28 03:36
14 views 0
Binary search tree demo program

/* Binary search tree demo program

    Exercise: 課堂公布

    Homework 6:

    (a) 設計一個副程式;將一維陣列的所有數植;轉換成一個binary search

    tree;並將這個treeroot傳回

     treeNode* createTreeFromArray(int dataArray[], int arrayLen);

     呼叫範例; tree = createTreeFromArray(dataArray, arrayLen);

    (b) 寫一個副程式刪除一個值為keynode;並將這個treeroot傳回及驗

    證結果

     treeNode* deleteNode(treeNode *tree, int key);

     呼叫範例; tree = deleteNode(tree,40);

    */

#include

    #include

typedef struct treeNode {

     int data;

     treeNode *leftChild, *rightChild; };

treeNode* createTree();

    treeNode* search(treeNode *root, int key); treeNode* iterSearch(treeNode *tree, int key); treeNode* insertNode(treeNode *tree, int num); treeNode* modifiedSearch(treeNode *tree, int key);

int main()

    {

     treeNode *tree, *ans;

     tree=createTree();

     ans=search(tree,30);

     if (ans)

     printf("%d is found\n",ans->data);

     ans=iterSearch(tree,80);

     if (ans)

     printf("%d is found\n",ans->data);

     tree=insertNode(tree,80);

     ans=iterSearch(tree,80);

     if (ans)

     printf("%d is found\n",ans->data);

     getchar();

     return 0;

    }

treeNode* createTree()

    {

     treeNode *left, *right, *parent;

     left=(treeNode *) malloc(sizeof(treeNode));

     left->data=2;

     left->leftChild=NULL;

     left->rightChild=NULL;

     parent=(treeNode *) malloc(sizeof(treeNode));

     parent->data=5;

     parent->leftChild=left;

     parent->rightChild=NULL;

     left=parent;

     right=(treeNode *) malloc(sizeof(treeNode));

     right->data=40;

     right->leftChild=NULL;

     right->rightChild=NULL;

     parent=(treeNode *) malloc(sizeof(treeNode));

     parent->data=30;

     parent->leftChild=left;

     parent->rightChild=right;

     return parent;

    }

    treeNode* search(treeNode *root, int key) {

     if (!root)

     return NULL;

     if (key == root->data)

     return root;

     if (key < root->data)

     return search(root->leftChild,key);

     return search(root->rightChild,key); }

    treeNode* iterSearch(treeNode *tree, int key) {

     while (tree)

     {

     if (key == tree->data)

     return tree;

     if (key < tree->data)

     tree = tree->leftChild;

     else tree = tree->rightChild;

     }

     return NULL;

    }

    treeNode* insertNode(treeNode *tree, int num) {

     treeNode *ptr;

     treeNode *temp = modifiedSearch(tree, num);

     if (temp || !tree)

     {

     ptr = (treeNode *) malloc(sizeof(treeNode));

     ptr->data = num; /* create a new node */

     ptr->leftChild = ptr->rightChild = NULL;

     if (tree) /* add the new node to the child of temp*/

     if (numdata)

     temp->leftChild = ptr;

     else

     temp->rightChild = ptr;

     else /* tree is empty, so a new tree with one node is created*/

     tree = ptr;

     }

     return tree;

    }

treeNode* modifiedSearch(treeNode *tree, int key)

    {

     treeNode* lastNode;

     if (!tree)

     return NULL;

     while (tree)

     {

     if (key == tree->data)

     return NULL;

     lastNode = tree;

     if (key < tree->data)

     tree = tree->leftChild;

     else

     tree = tree->rightChild;

     }

     return lastNode;

    }

Report this document

For any questions or suggestions please email
cust-service@docsford.com