1164
备注:
|
2078
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 14: | 行号 14: |
typedef int key_type; | |
行号 16: | 行号 15: |
key_type key; | int key; |
行号 28: | 行号 27: |
int seq_search(seq_list *r, key_type key) { | int seq_search(seq_list *r, int key) { |
行号 44: | 行号 43: |
int bin_search(seq_list *r, key_type key) { | int bin_search(seq_list *r, int key) { |
行号 63: | 行号 62: |
=== 二叉排序树 === 二叉排序树是一棵空二叉树或者满足以下条件的二叉树: * 左子树为空树或者左子树上所有结点的值小于根结点的值; * 右子树为空树或者右子树上所有结点的值大于根结点的值; * 左子树和右子树也是二叉排序树。 二叉排序树表示 {{{#!cplusplus typedef struct datatype { int key; }datatype; struct node { datatype data; struct node *left, *right; }; }}} 二叉排序树的插入 {{{#!cplusplus struct node *insert_bst(struct node *root, datatype elem){ if(root == NULL) { root = malloc(sizeof(struct node)); root->data = elem; root->left = root->right = NULL; return root; } if(root->data.key < elem.key) root->right = insert_bst(root->right, elem); else if(root->data.key > elem.key) root->left = insert_bst(root->left, elem); } }}} |
查找
1. 概念
平均查找长度:
查找成功时的平均查找长度:
2. 线性结构的查找
查找结构:
2.1. 顺序查找
查找成功时的平均查找长度:(n+1)/2
查找不成功时的平均查找长度:n
2.2. 折半查找
折半查找要求元素先排序
查找成功时的平均查找长度
3. 树型结构查找
3.1. 二叉排序树
二叉排序树是一棵空二叉树或者满足以下条件的二叉树:
- 左子树为空树或者左子树上所有结点的值小于根结点的值;
- 右子树为空树或者右子树上所有结点的值大于根结点的值;
- 左子树和右子树也是二叉排序树。
二叉排序树表示
二叉排序树的插入
1 struct node *insert_bst(struct node *root, datatype elem){
2 if(root == NULL) {
3 root = malloc(sizeof(struct node));
4 root->data = elem;
5 root->left = root->right = NULL;
6 return root;
7 }
8 if(root->data.key < elem.key)
9 root->right = insert_bst(root->right, elem);
10 else if(root->data.key > elem.key)
11 root->left = insert_bst(root->left, elem);
12 }