Created
March 16, 2014 13:29
-
-
Save tinylamb/9583240 to your computer and use it in GitHub Desktop.
Revisions
-
tinylamb created this gist
Mar 16, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,87 @@ /* * ========================================================= * Filename: BST.c * Description: 二叉搜索树 * * ========================================================= */ #include <stdio.h> #include <stdlib.h> //数据集定义 typedef struct node{ int elem; struct node *left; struct node *right; }Node; /*--------------------------------------------------- * 基于二叉搜索树的方法 *---------------------------------------------------*/ Node *BinarySearch(Node *root , int target); Node *Insert(Node *root ,int target); Node *FindMin(Node *root); Node *FindMax(Node *root); Node *Delete(Node *root ,int target); int main(){ } Node *BinarySearch(Node *root , int target){ if (root == NULL) return NULL; else if (root->elem == target) return root; else if (root->elem >target) return BinarySearch(root->left , target); else return BinarySearch(root->right , target); } Node *Insert(Node *root ,int target){ if (root == NULL){ root = malloc (sizeof(Node)); root->elem = target; root->left = root->right = NULL; } else if (target < root->elem) root->left = Insert(root->left, target);//这里让root->left 是否多余? else if (target > root->elem) root->right = Insert(root->right ,target); return root; } Node *FindMin(Node *root){ if (root){ while (root->left) root = root->left; } return root; } Node *FindMax(Node *root){ if (root == NULL)//递归的base case return NULL; else if (root->right == NULL) return root;//递归中何时用return?见evernote笔记 else return FindMax(root->right); } Node *Delete(Node *root ,int target){ if(root == NULL) printf("target is not in the tree"); else if (target < root->elem) root->left = Delete(root->left ,target); else if (target > root->elem) root->right = Delete(root->right ,target); else if (root->left && root->right){//如果要删除的节点有两个子节点 Node *temp = FindMin(root->right); root->elem = temp->elem; root->right = Delete(root->right , root->elem); } else{//如果有最多一个节点 Node *temp = root; if (root->left == NULL) root = root->right; else if (root->right == NULL) root = root->left; free(temp); } return root; }