/* 二叉查找树，中序遍历为从小到大的顺序，在查找树基本平衡时，复杂度logn，若退化成一条线时，复杂度n */
#include<stdio.h> #include<malloc.h> #include <memory.h> #include<stdlib.h> #include <time.h> typedef struct _SearchTree { int data; int times; struct _SearchTree *pLChild; struct _SearchTree *pRChild; }SearchTree; void addNode(SearchTree **node, int value) { SearchTree *tmp = *node; if (NULL == tmp) { tmp = (SearchTree *)malloc(sizeof(SearchTree)); if (NULL == tmp) { printf("malloc error\n"); return; } memset(tmp, 0, sizeof(SearchTree)); tmp->data = value; tmp->times = 1; *node = tmp; } else { if (value < tmp->data) { addNode(&(tmp->pLChild), value); } else if (value > tmp->data) { addNode(&(tmp->pRChild), value); } else { tmp->times++; } } } void firtPrint(SearchTree *node) { int i; if (NULL != node) { for (i = 0; i < node->times; i++) { printf("%d\n", node->data); } firtPrint(node->pLChild); firtPrint(node->pRChild); } } void midPrint(SearchTree *node) { int i; if (NULL != node) { midPrint(node->pLChild); for (i = 0; i < node->times; i++) { printf("%d\n", node->data); } midPrint(node->pRChild); } } void lastPrint(SearchTree *node) { int i; if (NULL != node) { lastPrint(node->pLChild); lastPrint(node->pRChild); for (i = 0; i < node->times; i++) { printf("%d\n", node->data); } } } void freeNode(SearchTree *node) { if (NULL != node) { freeNode(node->pLChild); freeNode(node->pRChild); free(node); node = NULL; } } SearchTree *searchNode(SearchTree *node, int value) { if (NULL == node) { return NULL; } if (value == node->data) { return node; } else if (value > node->data) { return searchNode(node->pRChild, value); } else { return searchNode(node->pLChild, value); } } #define CAPACITY 500 int main(int argc, char *argv[]) { int array[CAPACITY] = {0}; int i; int value; int randNum; SearchTree *tmp; SearchTree *root = NULL; if (argc > (CAPACITY + 1)) { return -1; } for (i = 1; i < argc; i++) { addNode(&root, atoi(argv[i])); } /* 先序遍历 */ printf("先序遍历 start\n"); firtPrint(root); printf("先序遍历 end\n"); /* 中序遍历 */ printf("中序遍历 start\n"); midPrint(root); printf("中序遍历 end\n"); /* 后续遍历 */ printf("后序遍历 start\n"); lastPrint(root); printf("后序遍历 end\n"); /* 查找 */ srand((int) time(0)); randNum = rand()%(argc-1); tmp = searchNode(root, atoi(argv[randNum])); if (NULL != tmp) { printf("\n search index:%d, num:%d, actual:%d, times:%d \n", randNum, atoi(argv[randNum]), tmp->data, tmp->times); } else { printf("\n search num:%d, not found \n"); } /* 释放内存 */ freeNode(root); return 0; }