二叉排序树

二叉排序树是一种便于查找的一种有序树。其中二叉排序树的左子树均小于其根结点的值，右子树均大于其根结点的值。所以二叉排序树是一种递归的方式建立和查询以及插入。由于二叉树的删除有点儿复杂，所以没有给出代码。删除大体上是三种情况：1.直接删除叶子结点2.删除只带有一个分支的结点，让其分支节点直接代替其根结点3.删除多个分支的结点，让删除结点的中序序列直接后继代替被删结点。下面请看详细的代码：

#include <iostream>#include <stdio.h>#include <stdlib.h>/* run this program using the console pauser or add your own getch, system("pause") or input loop */typedef struct BSTNode{    int data;    struct BSTNode *lchild,*rchild;}BSTNode,*BiTree;//二叉排序树的插入int BST_Insert(BiTree &T,int key){    if(T==NULL){        T = (BSTNode*)malloc(sizeof(BSTNode));        T->data = key;        T->lchild = T->rchild = NULL;        return 1;    }    else if(key == T->data){        return 0;    }    else if(key > T->data){        return BST_Insert(T->rchild,key);    }    else{        return BST_Insert(T->lchild,key);    }} //二叉排序树的查找BSTNode* BST_Search(BiTree T,int key){    if(T==NULL){        return NULL;    }    else if(key > T->data){        return BST_Search(T->rchild);    }    else{        return BST_Search(T->lchild);    }}//构造二叉排序树void Create_BST(BiTree &T,int num[],int n){    T = NULL;    int i = 0;    while(i<n){        BST_Insert(T,num[i]);        i++;    }} int main(int argc, char** argv) {    int num[] = {1,2,3,4,5};    BiTree T;    Create_BST(T,num,5);    BST_Search(T,3);    return 0;}

更多相关文章

随机推荐