网站后台如何修改密码,免费模板下载个人简历,哪个网站做体检预约的,tpshop开源商城定义
二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。 一个二叉搜索树可以为空#xff0c;如果它不为空#xff0c;它将满足以下性质#xff1a;
非空左子树的所有键值小于其根节点的键值非空右子树的所有键值都大于其根结点的键值左…定义
二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。 一个二叉搜索树可以为空如果它不为空它将满足以下性质
非空左子树的所有键值小于其根节点的键值非空右子树的所有键值都大于其根结点的键值左、右子树都是二叉树
动态查找
查找操作Find
在二叉搜索树中查找关键字为X的结点返回其所在结点的地址。查找过程如下
查找从树的根节点开始若树为空返回NULL搜索树非空则根节点关键字和X比较依据结果需要进行不同的处理 若根节点键值小于X在根节点右子树中查找 若根节点的键值大于X在根节点的左子树中查找 若两者比较结果相等搜索完成。
递归代码
Position Find_RE(BinTree BT, ElementType X) {if (!BT) {return NULL;}if (X BT-Data) {return Find_RE(BT-Right, X);}else if(X BT-Data){return Find_RE(BT-Left, X);}else{return BT;}
}迭代函数
Position Find_D(BinTree BT, ElementType X) {BinTree T BT;while (T) {if (T-Data X) {T T-Left;}else if (T-Data X) {T T-Right;}else{return T;}}
}查找最大和最小元素
根据二叉搜索树的性质最大元素一定在最右分支的尾端最小元素一定在最左分支的尾端。 递归函数
Position FindMin(BinTree BT) {if (!BT) {return NULL;}else if(!BT-Left){return BT;}else{return FindMin(BT-Left);}
}迭代函数
Position FindMinD(BinTree BT) {BinTree T BT;while (T-Left) {T T-Left;}return T;
}找最大值只需要把left换成right
插入
BinTree Insert(BinTree BT, ElementType X) {if (!BT) {BT (BinTree)malloc(sizeof(struct TNode));BT-Data X;BT-Left BT-Right NULL;}else {if (X BT-Data) {BT-Right Insert(BT-Right, X);}else if (X BT-Data) {BT-Left Insert(BT-Left, X);}}return BT;
}删除
二叉搜索树的删除比较复杂需要考虑节点的位置
叶结点 可以直接删除将其父节点指针置空即可。只有一个孩子结点 要修改其父节点的指针指向要删除结点的孩子结点。有左、右两颗树 究竟用哪颗子树的根结点来填充删除节点的位置有两种选择方式选择左子树的最大元素或者选择右子树的最小元素。无论哪种方式最后被选择的结点必定最多只有一个孩子。
采用右子树的最小元素的删除代替策略。 代码思路 先找到要删除元素的位置若其具有左右子树找到该位置的右子树里面的最小元素赋值到该位置上在其右子树中删除最小元素递归调用若只有一个子树或者没有易操作。 BinTree DeleteBT(BinTree BT, ElementType X) {Position p;if (!BT) {printf(cant find the node\n);}else {if (X BT-Data) {BT-Right DeleteBT(BT-Right, X);}else if (X BT-Data) {BT-Left DeleteBT(BT-Left, X);}else {if (BT-Left BT-Right) {//FIND THE Min OF Right TREEp FindMin(BT-Right);BT-Data p-Data;BT-Right DeleteBT(BT-Right, p-Data);}else {p BT;if (!BT-Left) {BT BT-Right;}else { BT BT-Left; }free(p);}}}return BT;
}
