Please enable Javascript to view the contents

二叉查找树

 ·  ☕ 1 分钟

什么是二叉查找树

定义

二叉查找树(BinarySearchTree)
是一种特殊的二叉树,它的递归定义如下:

  • 二叉查找树可以是一棵空树
  • 二叉查找树由根结点、左子树、右子树构成,其中左子树和右子树都是二叉查找树,二叉查找树每个结点的左子树上所有结点的数据域均小于或等于该结点的数据域,每个结点的右子树上所有结点的数据域均大于该结点的数据域。

由于二叉查找树本质上也是一颗二叉树,因此它的链式存储结构与普通的二叉树是一致的。

1
2
3
4
5
typedef BiSearchTree{
    ElementType data;
    BiSearchTree* lchild;
    BiSearchTree* rchild;
}Node, *BSTree;

操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
/* 建立二叉查找树 */
BSTree create_bstree(int* array, int num);

/* 前序遍历二叉树 */
void preorder_traversal(BSTree root);

/* 中序遍历二叉树 */
void inorder_traversal(BSTree root);

/* 后序遍历二叉树 */
void postorder_traversal(BSTree root);

/* 递归查找二叉树中值为val的结点 */
Node* search_bstree(BSTree root, ElementType data);

建立二叉查找树

建立二叉查找树的过程实际上就是先后插入n个结点的过程

1
2
3
BSTree create_bstree_node(int* array, int num){

}