建设银行大厂支行网站,手机网站建设计,贵阳市住房和城乡建设部网站,京东网站架构目录 二叉排序树的定义
二叉排序树的查找
二叉排序树的插入 二叉排序树的定义
二叉排序树的定义 二叉排序树#xff08;Binary Sort Tree#xff0c; BST#xff09;#xff0c;也称二叉查找树。 二叉排序树或者是一棵空树#xff0c;或者是一棵具有下列特性的非空二叉…目录 二叉排序树的定义
二叉排序树的查找
二叉排序树的插入 二叉排序树的定义
二叉排序树的定义 二叉排序树Binary Sort Tree BST也称二叉查找树。 二叉排序树或者是一棵空树或者是一棵具有下列特性的非空二叉树 1 若左子树非空则左子树上所有结点关键字均小于根结点的关键字值 2 若右子树非空则右子树上所有结点关键字均大于根结点的关键字值 3 左、右子树本身也分别是一棵二叉排序树。
由定义可知二叉排序树是一个递归的数据结构可以方便的使用递归算法对二叉排序树进行各种运算。 根据二叉树的定义可得左子树结点值 根结点值 右子树结点值。 所以对二叉排序树进行中序遍历可以得到一个递增的有序序列。 二叉排序结点结构
typedef struct BiTNode
{int data;struct BiTNode *left, *right;
}BiTNode,*Bitree;
二叉排序树的查找
二叉排序树的查找是从根结点开始的沿某个分支逐层向下进行比较的过程。 其查找过程描述如下若二叉排序树非空则将给定值与根结点的关键字比较若相等则查找成功若不等则当根结点的关键字值大于给定关键字值时在根结点的左子树中查找否则在根结点的右子树中查找。
递归查找
Bitree SearchBST(Bitree root, int key){if(root-data key){return root;}else if(key root-data){return SearchBST(root-left, key);}else{return SearchBST(root-right, key);}
}非递归查找
//查找的非递归算法
Bitree SearchBST(Bitree root, int key){Bitree p root;while(p!NULL p-data!key){if(key p-data)p p-left;elsep p-right;}return p;
}二叉排序树的插入
//插入的递归算法
Bitree Insert(Bitree root, int x) {if (root NULL) {root (Bitree)malloc(sizeof(BiTNode));root-data;root-left NULL;root-right NULL;return root;}if (x root-data) {root-left Insert(root-left, x);}if (x root-data) {root-right Insert(root-right, x);}return root;
}
//插入的非递归算法
void Inser_Node(Bitree T, int key)
{Bitree parent NULL;Bitree p T;Bitree s (Bitree)malloc(sizeof(BiTNode));s-data key;s-left NULL;s-right NULL;if (T NULL){T s;return;}while (p ! NULL){parent p;if (p-data key)//在左孩子继续查找{p p-left;}if (p-data key){p p-right;}}if (parent-data key){parent-left s;}else {parent-right s;}}
根据书上代码将查找和插入整合
/****************书上代码***************************/
int SearchBST(Bitree T,int key, Bitree f, Bitree p)
{if (!T){p f;return 0;}else if(T-datakey){p T;printf(有重复);return 1;}else if (T-data key){return SearchBST(T-left, key, T, p);}else{return SearchBST(T-right, key, T, p);}
}
void InserBST(Bitree T, int key)
{Bitree p;if (SearchBST(T, key, NULL, p)0)//查找失败进行插入{Bitree s (Bitree) malloc(sizeof(BiTNode));s-data key;s-left NULL;s-right NULL;if (!p){T s;}else if (key p-data){p-left s;//被插入点作为*s左孩子}else {p-right s;}}
}
