植物网站设计方案ink域名网站

二叉排序树

二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

基本步骤

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

插入算法：

首先执行查找算法，找出被插结点的父亲结点。

判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

若二叉树为空。则首先单独生成根结点。

注意：新插入的结点总是叶子结点。

void InsertBST(t，key)

//在二叉排序树中插入查找关键字key

{

if(t==NULL){

t=new BiTree;

t->lchild=t->rchild=NULL;

t->data=key;

return; }

if(keydata ) InsertBST(t->lchild,key);

else InsertBST (t->rchild, key );

}

void CreateBiTree(tree,d【 】,n）

//n个数据在数组d中，tree为二叉排序树根

{tree=NULL;

for(i=0;i InsertBST(tree,d);

}

方法一 用递归的方法实现

测试代码

#include <stdio.h>
#include <stdlib.h>#include "bintree.h"void show_menu(void){printf("*******二叉排序树功能测试**********\n");printf("**1. 插入元素 \n");printf("**2. 删除元素 \n");printf("**3. 查找某元素是否在树中 \n");printf("**4. 树是否为空 \n");printf("**5. 树中元素个数 \n");printf("**6. 树的高度 \n");printf("**7. 树的先序遍历 \n");printf("**8. 树的中序遍历 \n");printf("**9. 树的后序遍历 \n");printf("**10.树的层序遍历 \n");printf("**11. 清空树 \n");printf("**0. 退出 \n");printf(">>>>");
}void travel(int n){printf("%d ",n);
}void test_bin_tree(void){BinTree tree = NULL;bin_tree_init(&tree);while(true){show_menu();int opt = 0;int elem = 0;int ret = 0;bool f = true;scanf("%d",&opt);switch(opt){case 1:printf("请输入要插入二叉排序树中的元素:");scanf("%d",&elem);ret = bin_tree_insert(&tree,elem);if(ret == 0){printf("插入成功！\n");}else{if(ret == -1){printf("插入失败!内存问题!\n");}else{printf("树中已有该元素，插入失败!\n");}}break;case 2:printf("请输入要删除的元素:");scanf("%d",&elem);ret = bin_tree_delete(&tree,elem);if(ret == 0){printf("删除成功!\n");}else{printf("删除失败!树中没有该元素!\n");}break;case 3:printf("请输入要查找树中是否存在的元素:");scanf("%d",&elem);if(bin_tree_contain(tree,elem)){printf("树中存在该元素!\n");}else{printf("树中没有该元素!\n");}break;case 4:bin_tree_empty(tree)?puts("空空如也！\n"):puts("树中有元素!\n");case 5:printf("树中元素个数:%u\n",bin_tree_size(tree));case 6:printf("树的高度为:%u\n",bin_tree_hight(tree));break;case 7:bin_tree_front_travel(tree,travel);printf("\n");case 8:bin_tree_mid_travel(tree,travel);printf("\n");case 9:bin_tree_back_travel(tree,travel);printf("\n");case 10:bin_tree_layer_travel(tree,travel);printf("\n");break;case 11:bin_tree_clear(&tree);break;case 0:bin_tree_destroy(&tree);return; }}
}int main(int argc, char *argv[]) {test_bin_tree();return 0;
}

头文件

#ifndef _BIN_TREE_H__
#define _BIN_TREE_H__#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//二叉(排序)树的结点类型   
typedef struct BNode{int elem;struct BNode *lchild;//struct BNode *lchild,*rchild;struct BNode *rchild;
}BNode,*BinTree;#define BNODESIZE sizeof(struct BNode)//BinTree tree = NULL;   bin_tree_init(&tree);
void bin_tree_init(BinTree* ptree);//struct BNode **proot;  *proot = NULL;
int bin_tree_insert(BinTree* ptree,int elem);
int bin_tree_delete(BinTree *ptree,int elem);
void bin_tree_clear(BinTree *ptree);
void bin_tree_destroy(BinTree *ptree); bool bin_tree_empty(BinTree tree);
size_t bin_tree_size(BinTree tree);
size_t bin_tree_hight(BinTree tree);
//查找 
bool bin_tree_contain(BinTree tree,int elem);void bin_tree_front_travel(BinTree tree,void (*travel)(int));
void bin_tree_mid_travel(BinTree tree,void (*travel)(int));
void bin_tree_back_travel(BinTree tree,void (*travel)(int));
void bin_tree_layer_travel(BinTree tree,void (*travel)(int));#endif //_BIN_TREE_H__

函数实现