首页 > 代码库 > 数据结构快速回顾——二叉查找树

数据结构快速回顾——二叉查找树

2024-07-09 06:18:39   219人阅读

 

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 任意节点的左、右子树也分别为二叉查找树。
  4. 没有键值相等的节点（no duplicate nodes）。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(log n)，意味着树的所有节点平均深度为nlogn。。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

 

二叉查找树应用广泛

1、二叉查找树用于排序

步骤：

1）构建二叉查找树BST；

2）中序遍历BST；

 

通过分析（算法导论里面有具体分析）可知，快速排序原理和二叉搜索树的构建是一致的，只不过比较的顺序不同。

BST具体实现如下：

 

 

 

  1 #include<stdio.h>  2   3 typedef    struct node  4 {  5     int value;  6     struct node* pleft;  7     struct node* pright;  8       9 }BNode; 10  11 void Visit(BNode *pRoot) 12 { 13     printf("%d\t",pRoot->value); 14 } 15 void InOrderTraverse(BNode *pRoot) 16 { 17     if(pRoot == NULL) 18         return; 19     InOrderTraverse(pRoot->pleft); 20     Visit(pRoot); 21     InOrderTraverse(pRoot->pright); 22 } 23 //由于可能改变指针位置，所以使用指针的引用作为形参  24 BNode* InsertBST(BNode *&root, int value) 25 { 26     if(root == NULL) 27     { 28         BNode* n = new BNode(); 29         n->value =http://www.mamicode.com/ value; 30         n->pleft = NULL; 31         n->pright = NULL; 32         root = n; 33         return root; 34     }     35     if(root->value < value) 36     { 37         root->pright = InsertBST(root->pright, value); 38     } 39     else  40     { 41         root->pleft = InsertBST(root->pleft, value); 42     } 43     return root; 44 } 45  46 //由于可能改变指针位置，所以使用指针的引用作为形参  47 void InsertBST2(BNode *&root, int val) 48 { 49  50     BNode* n = new BNode(); 51     n->value =http://www.mamicode.com/ val; 52     n->pleft = NULL; 53     n->pright = NULL; 54      55     if(!root) 56     { 57         root = n; 58         return; 59     } 60      61     BNode* tmp = root; 62     while(tmp) 63     { 64         if(tmp->value < n->value) 65         { 66             if(tmp->pright) 67             { 68                 tmp = tmp->pright;     69                 continue;             70             } 71             else 72             { 73                 tmp->pright = n; 74                 return; 75             } 76         } 77         else 78         { 79             if(tmp->pleft) 80             { 81                 tmp = tmp->pleft;     82                 continue;             83             } 84             else 85             { 86                 tmp->pleft = n; 87                 return; 88             } 89                  90         } 91     } 92 } 93  94 int main() 95 { 96  97     BNode* pnode = NULL; 98      99     int data[8]= {3,2,6,3,8,6,1,4};100     for(int i=0;i <8;i++)101     {102         //InsertBST2(pnode,data[i]);103         InsertBST(pnode,data[i]);104     }105     106     InOrderTraverse(pnode);107     return 0;108 }109

 

 


联系
我们