DOC

# Binary search tree demo program

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