二叉排序树和平衡二叉树（哈喜老师）

1.二叉排序树1.1二叉排序树的概念1.2与二叉排序树的相关的操作1.2.1求平均查找长度1.2.2查找某个元素代码不重要// 代码不重要重要的是要明白查找某个元素的过程// 二叉排序树BST的查找函数// 参数T 是二叉排序树根节点key 是要查找的关键字元素// 返回值找到则返回对应节点指针没找到则返回 NULLBSTNode*BST_Search(BiTree T,ElemType key){// 循环条件树不为空 且 还没找到目标关键字while(T!NULLkey!T-data){if(keyT-data)TT-lchild;// 关键字 当前节点值 → 去左子树查找elseTT-rchild;// 关键字 当前节点值 → 去右子树查找}// 退出循环要么找到节点返回该节点的地址要么TNULL查找失败returnT;}1.2.3在二叉排序树中插入元素代码不重要// 代码不重要重要的是要明白插入某个元素的过程// 二叉排序树的插入函数递归实现// 参数T 为二叉排序树根节点的引用k 为待插入的关键字// 返回值插入成功返回 1失败关键字已存在返回 0intBST_Insert(BiTreeT,KeyType k){// 情况1当前子树为空找到插入位置if(TNULL){// 为新节点分配内存空间T(BiTree)malloc(sizeof(BSTNode));// 将关键字存入新节点T-datak;// 新节点为叶子节点左右孩子初始化为空T-lchildT-rchildNULL;return1;// 插入成功返回1}// 情况2树中已存在相同关键字的节点不允许重复插入elseif(kT-data){return0;// 插入失败返回0}// 情况3待插入关键字小于当前节点值递归插入到左子树elseif(kT-data){returnBST_Insert(T-lchild,k);}// 情况4待插入关键字大于当前节点值递归插入到右子树else{returnBST_Insert(T-rchild,k);}}例题1.2.4删除二叉排序树中的某个元素这里听王道的课知识点不常考习题1易习题2难2.平衡二叉树2.1平衡二叉树的概念2.2在平衡二叉树中插入新结点找最小不平衡子树LL型RR型LR型RL型2.3删除结点考的少2.4真题真题1易真题2中真题3难