学步园

#include <iostream><br /> using namespace std;</p> <p>//顺序查找, 平均查找长度为(n + 1)/2<br /> int search_sq(int array[], int array_len, int key)<br /> {<br /> for (int i = 0; i < array_len; ++i)<br /> {<br /> if (key == array[i])<br /> {<br /> return i;<br /> }<br /> }</p> <p> return -1;<br /> }</p> <p>//二分查找,平均查找查找长度为〖log2 (N+1〗 - 1,但是序列必须是有序的<br /> int search_binary(int array[], int array_len, int key)<br /> {<br /> int left = 0;<br /> int right = array_len -1;</p> <p> while (left <= right)<br /> {<br /> int middle = (left + right)/2;<br /> if (array[middle] == key)<br /> {<br /> return middle;<br /> }</p> <p> else if (array[middle] > key)<br /> {<br /> right = middle - 1;<br /> }</p> <p> else<br /> left = middle + 1;</p> <p> }</p> <p> return -1;</p> <p>}</p> <p>//二叉树查找</p> <p>struct BSTreeNode<br /> {<br /> int data;<br /> BSTreeNode* left_child;//左孩子<br /> BSTreeNode* right_child; //右孩子<br /> };</p> <p>typedef BSTreeNode* BSTree; </p> <p>BSTreeNode* pNode = NULL;<br /> // 根据结点值创建数目<br /> void Create(BSTree& tree, int data)<br /> {</p> <p> if (tree == NULL)<br /> {<br /> tree = new BSTreeNode;<br /> tree->left_child = NULL;<br /> tree->right_child = NULL;<br /> tree->data = data;<br /> }</p> <p> else<br /> {<br /> if (tree->data > data)<br /> {<br /> Create(tree->left_child, data);<br /> }</p> <p> else if (tree->data < data)<br /> {<br /> Create(tree->right_child, data);<br /> }<br /> else<br /> return;<br /> }</p> <p>}</p> <p>//创建二叉树<br /> void CreateBSTree(int array[], int array_len)<br /> {<br /> for (int i = 0; i < array_len; ++i)<br /> {<br /> Create(pNode, array[i]);<br /> }<br /> }</p> <p>//查找树查找,平均查找查找长度为〖log2 (N+1〗 - 1<br /> BSTreeNode* search_binaryTree(BSTree tree, int data)<br /> {</p> <p> if (tree == NULL)<br /> {<br /> return NULL;<br /> }</p> <p> if (tree->data == data)<br /> {<br /> return tree;<br /> }</p> <p> else if (tree->data > data)<br /> {<br /> return search_binaryTree(tree->left_child, data);<br /> }</p> <p> else<br /> return search_binaryTree(tree->right_child, data);</p> <p>}</p> <p>int main()<br /> {</p> <p> int a[10] ={2, 5, 1, 8, 9};<br /> cout<<"顺序查找元素8的位置是:"<<search_sq(a, 5, 8)<<endl;</p> <p> int b[7] = {1, 2, 3, 3, 5, 6};</p> <p> cout<<"二分查找元素3的位置是:"<<search_binary(b, 7, 3)<<endl;<br /> CreateBSTree(a, 5);</p> <p> cout<<"二叉树查找是否存在8:";<br /> CreateBSTree(a, 5);<br /> BSTreeNode* find = search_binaryTree(pNode, 8);<br /> cout<<find->data<<endl;<br /> find = search_binaryTree(pNode, 10);<br /> if (find == NULL)<br /> {<br /> cout<<"不存在10!";<br /> }<br /> return 0;</p> <p>}