二叉搜索树

一、基本概述

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 —百度百科

二、常用操作

1.定义结点结构体

typedef struct Node//定义节点结构体 { int data; struct Node *left;//指向左子节点 struct Node *right;//指向右子节点 }N;

2.定义二叉树的结构体

typedef struct Tree//定义二叉树结构体 { N *root;//根节点 }T;

3.定义创建结点函数

N *create_Node(int Data){ N *new_Node = (N *)malloc(sizeof(N)); new_Node->left = NULL; new_Node->right = NULL; new_Node->data = Data; return new_Node; }

4.结点的插入

void insert(T *tree, int Data){ N *new_Node = create_Node(Data); if(tree->root == NULL){ tree->root = new_Node;//创建根节点 return ; } else{ N *temp = tree->root;//创建一个临时节点去代替根节点 while(temp != NULL){ if(Data < temp->data){ if(temp->left == NULL){ temp->left = new_Node; return ; } else{ temp = temp->left; } } else{ if(Data > temp->data){ if(temp->right == NULL){ temp->right = new_Node; return ; } else{ temp = temp->right; } } } } } }

5.定义先序遍历函数(根–>左–>右)，采用递归的方法进行遍历

void preorder(N *node){ if(node != NULL){ printf("%d ", node->data); preorder(node->left); preorder(node->right); } }

6.定义中序遍历函数(左–>根–>右)，采用递归的方法进行遍历

中序遍历常用作排序

void in_Order(N *node){ if(node != NULL){ in_Order(node->left); printf("%d ", node->data); in_Order(node->right); } }

7.定义后序遍历函数(左–>右–>根)，采用递归的方法进行遍历

void post_Order(N *node){ if(node != NULL){ post_Order(node->left); post_Order(node->right); printf("%d ", node->data); } }

三、加入主函数代码实现

#include <stdio.h> #include <stdlib.h> typedef struct Node//定义节点结构体 { int data; struct Node *left;//指向左子节点 struct Node *right;//指向右子节点 }N; typedef struct Tree//定义二叉树结构体 { N *root; }T; //创建结点 N *create_Node(int Data){ N *new_Node = (N *)malloc(sizeof(N)); new_Node->left = NULL; new_Node->right = NULL; new_Node->data = Data; return new_Node; } //结点的插入 void insert(T *tree, int Data){ N *new_Node = create_Node(Data); if(tree->root == NULL){ tree->root = new_Node;//创建根节点 return ; } else{ N *temp = tree->root;//创建一个临时节点去代替根节点 while(temp != NULL){ if(Data < temp->data){ if(temp->left == NULL){ temp->left = new_Node; return ; } else{ temp = temp->left; } } else{ if(Data > temp->data){ if(temp->right == NULL){ temp->right = new_Node; return ; } else{ temp = temp->right; } } } } } } //先序遍历(根-->左-->右) void preorder(N *node){ if(node != NULL){ printf("%d ", node->data); preorder(node->left); preorder(node->right); } } //中序遍历(左-->根-->右) void in_Order(N *node){ if(node != NULL){ in_Order(node->left); printf("%d ", node->data); in_Order(node->right); } } //后序遍历(左-->右-->根) void post_Order(N *node){ if(node != NULL){ post_Order(node->left); post_Order(node->right); printf("%d ", node->data); } } int main() { T *myTree; myTree->root = NULL; int arr[7] = {7,5,8,3,2,1,9}; for(int i = 0; i < 7; i++){ insert(myTree, arr[i]); } printf("先序遍历:"); preorder(myTree->root); printf("\n"); printf("中序遍历:"); in_Order(myTree->root); printf("\n"); printf("中序遍历:"); post_Order(myTree->root); printf("\n"); free(myTree->root); return 0; }