严蔚敏数据结构 |
您所在的位置：网站首页 › 二叉排序树c语言代码 › 严蔚敏数据结构 |
|
目录 一、二叉查找树的数据类型——二叉树 二、二叉查找树的中序遍历（用于查看二叉查找树的数据元素） 三、二叉查找树的查找操作 递归版： 非递归版： 四、二叉查找树的插入操作 算法步骤 代码： 递归版： 非递归版： 五、二叉查找树的删除操作 算法步骤： 代码： 递归版： 非递归版： 六、总代码 递归版总代码： 非递归版总代码： 一、二叉查找树的数据类型——二叉树 #include #include #include #define NOTFOUND -1 #define FOUND -2 #define ALREADT_EXIST - 3 typedef int Status; typedef struct BiNode { int data; BiNode* lchild; BiNode* rchild; }BiNode, * BiTree; 二、二叉查找树的中序遍历（用于查看二叉查找树的数据元素） void MidTraverse(BiTree T) { if (!T)return; MidTraverse(T->lchild); printf("%d ", T->data); MidTraverse(T->rchild); } 三、二叉查找树的查找操作 递归版： Status Search(BiTree T, int key) { if (!T)return NOTFOUND; else if (T->data < key) { deepth++; return Search(T->rchild, key); } else if (T->data > key) { deepth++; return Search(T->lchild, key); } else return FOUND; } 非递归版： int deepth; Status Search(BiTree T, int key) { while (T) { if (T->data < key)T = T->rchild; else if (T->data > key)T = T->lchild; else return FOUND; deepth++; } return NOTFOUND; }其中的deepth表示深度，注意在每次查找时将深度初始化为1。 四、二叉查找树的插入操作 算法步骤1.如果当前节点为空，直接在此节点分配空间，并初始化要插入的值，以及将左右节点设为空。 2.如果当前节点小于要插入的数，向右子树的方向走，反之亦然。 3.如果当前节点等于要插入的数，直接返回。 代码： 递归版： Status Insert(BiTree& T, int x) { if (!T) { T = (BiNode*)malloc(sizeof(BiNode)); T->data = x; T->lchild = T->rchild = NULL; return 1; } else if (T->data < x)return Insert(T->rchild, x); else if (T->data > x)return Insert(T->lchild, x); else return 2; } 非递归版： void Insert(BiTree& T, int x) { if (T == NULL) { T = (BiNode*)malloc(sizeof(BiNode)); T->data = x; T->lchild = T->rchild = NULL; return; } BiTree p = T, pre = T; while (p != NULL && p->data != x) { if (p->data < x) { pre = p; p = p->rchild; } else if (p->data > x) { pre = p; p = p->lchild; } } p = (BiNode*)malloc(sizeof(BiNode)); p->data = x; p->lchild = p->rchild = NULL; if (pre->data > x)pre->lchild = p; else pre->rchild = p; }pre的作用是便于找到p的父节点 五、二叉查找树的删除操作 算法步骤：注意：每次删除前将Pre的值赋为NULL 1.如果当前节点为空，证明要删除的数在二叉查找树中不存在 2.如果当前节点小于要删除的数，则向右寻找，反之亦然 3.如果已经找到当前要删除的数，则分为以下三种情况讨论 （1）左右子树均为空，则将此节点释放并将父节点指向的这个地方设为NULL；（注意特判：根节点没有pre，即根节点的pre值为NULL，直接释放根节点即可，此时就变为了一棵空树） （2）左子树为空或者右子树为空，这里只讨论左子树为空的情况，这时，将该结点的pre指向该结点的右子树即可（同样需要特判，如果删除的是根节点，左子树为空，删除根节点时只需要将根节点赋值为其右子树即可，同时释放原来的那个根节点的空间） （3）左右子树均不为空，则可以将左子树的最右下或右子树的最左下元素赋给要删除的节点，这样便可以达到删除原来结点的目的，这里只讨论删除左子树的最右下元素的情况：找到这个元素后将其值赋给原来要删除的结点，再去删除左子树最右下的元素即可。 代码： 递归版： BiTree Pre; Status Delete(BiTree& T, int key) { if (!T)return NOTFOUND; else if (T->data < key){ Pre = T; return Delete(T->rchild, key); } else if (T->data > key){ Pre = T; return Delete(T->lchild, key); } else{ if (!T->lchild && !T->rchild){ if (!Pre) { free(T); return true; } if (Pre->lchild == T)Pre->lchild = NULL; else Pre->rchild = NULL; free(T); return true; } else if (!T->lchild || !T->rchild){ if (Pre == NULL){ BiTree p = T; if (T->lchild)T = T->lchild; else T = T->rchild; free(p); return true; } if (T->lchild){ if (Pre->lchild == T)Pre->lchild = T->lchild; else Pre->rchild = T->lchild; } else{ if (Pre->lchild == T)Pre->lchild = T->rchild; else Pre->rchild = T->rchild; } return true; } else{ BiTree p; Pre = T; for (p = T->lchild; p->rchild; Pre = p, p = p->rchild); T->data = p->data; return Delete(p, p->data); } } } 非递归版： BiTree Pre; Status Delete(BiTree& T, int key) { BiTree p = T; Pre = NULL; while (p) { if (p->data > key) { Pre = p; p = p->lchild; } else if (p->data < key) { Pre = p; p = p->rchild; } else { if (!p->lchild && !p->rchild) { if (!Pre) { free(p); return true; } if (Pre->lchild == p)Pre->lchild = NULL; else Pre->rchild = NULL; free(p); return true; } else if (!p->lchild || !p->rchild) { if (!Pre) { p = T; if (T->lchild)T = T->lchild; else T = T->rchild; free(p); return true; } if (p->lchild) { if (Pre->lchild == p)Pre->lchild = p->lchild; else Pre->rchild = p->lchild; } else { if (Pre->lchild == p)Pre->lchild = p->rchild; else Pre->rchild = p->rchild; } free(p); return true; } else { BiTree q; for (Pre = p,q = p->lchild; q->rchild; Pre = q, q = q->rchild); p->data = q->data; if (Pre->lchild == q)Pre->lchild = q->lchild; else Pre->rchild = q->lchild; } return true; } } return NOTFOUND; } 六、总代码 递归版总代码： #include #include #include #define NOTFOUND -1 #define FOUND -2 typedef int Status; typedef struct BiNode { int data; BiNode* lchild; BiNode* rchild; }BiNode, * BiTree; int deepth; void MidTraverse(BiTree T) { if (!T)return; MidTraverse(T->lchild); printf("%d %d %d\n", T->data,T->lchild==NULL,T->rchild==NULL); MidTraverse(T->rchild); } Status Insert(BiTree& T, int x) { if (!T) { T = (BiNode*)malloc(sizeof(BiNode)); T->data = x; T->lchild = T->rchild = NULL; return 1; } else if (T->data < x)return Insert(T->rchild, x); else if (T->data > x)return Insert(T->lchild, x); else return 2; } Status Search(BiTree T, int key) { if (!T)return NOTFOUND; else if (T->data < key) { deepth++; return Search(T->rchild, key); } else if (T->data > key) { deepth++; return Search(T->lchild, key); } else return FOUND; } BiTree Pre; Status Delete(BiTree& T, int key) { if (!T)return NOTFOUND; else if (T->data < key){ Pre = T; return Delete(T->rchild, key); } else if (T->data > key){ Pre = T; return Delete(T->lchild, key); } else{ if (!T->lchild && !T->rchild){ if (!Pre) { free(T); return true; } if (Pre->lchild == T)Pre->lchild = NULL; else Pre->rchild = NULL; free(T); return true; } else if (!T->lchild || !T->rchild){ if (Pre == NULL){ BiTree p = T; if (T->lchild)T = T->lchild; else T = T->rchild; free(p); return true; } if (T->lchild){ if (Pre->lchild == T)Pre->lchild = T->lchild; else Pre->rchild = T->lchild; } else{ if (Pre->lchild == T)Pre->lchild = T->rchild; else Pre->rchild = T->rchild; } return true; } else{ BiTree p; Pre = T; for (p = T->lchild; p->rchild; Pre = p, p = p->rchild); T->data = p->data; return Delete(p, p->data); } } } int main() { int x, q, k; BiTree T = NULL; printf("输入操作次数："); scanf("%d", &q); while (q--) { printf("请输入k和x,中间用空格隔开，k为123时分别表示查找、插入、删除值为x的结点："); scanf("%d%d", &k, &x); if (k == 1) { deepth = 1; int t = Search(T, x); if (t == NOTFOUND)printf("没有找到这个数。\n"); else printf("找到了！,这个数在第%d层\n", deepth); } else if (k == 2) { if (Search(T, x) == NOTFOUND)Insert(T, x); else printf("该数已存在！\n"); } else { Pre = NULL; int t = Delete(T, x); if (t == NOTFOUND)printf("没找到你要删的数。\n"); else printf("删除成功！\n"); } printf("中序遍历序列为：\n"); //printf("%d %d %d\n", T->data, T->lchild == NULL, T->rchild == NULL); MidTraverse(T); puts(""); } return 0; } 非递归版总代码： #include #include #include #define NOTFOUND -1 #define FOUND -2 #define ALREADT_EXIST - 3 typedef int Status; typedef struct BiNode { int data; BiNode* lchild; BiNode* rchild; }BiNode, * BiTree; int deepth; void MidTraverse(BiTree T) { if (!T)return; MidTraverse(T->lchild); printf("%d ", T->data); MidTraverse(T->rchild); } void Insert(BiTree& T, int x) { if (T == NULL) { T = (BiNode*)malloc(sizeof(BiNode)); T->data = x; T->lchild = T->rchild = NULL; return; } BiTree p = T, pre = T; while (p != NULL && p->data != x) { if (p->data < x) { pre = p; p = p->rchild; } else if (p->data > x) { pre = p; p = p->lchild; } } p = (BiNode*)malloc(sizeof(BiNode)); p->data = x; p->lchild = p->rchild = NULL; if (pre->data > x)pre->lchild = p; else pre->rchild = p; } Status Search(BiTree T, int key) { while (T) { if (T->data < key)T = T->rchild; else if (T->data > key)T = T->lchild; else return FOUND; deepth++; } return NOTFOUND; } BiTree Pre; Status Delete(BiTree& T, int key) { BiTree p = T; Pre = NULL; while (p) { if (p->data > key) { Pre = p; p = p->lchild; } else if (p->data < key) { Pre = p; p = p->rchild; } else { if (!p->lchild && !p->rchild) { if (!Pre) { free(p); return true; } if (Pre->lchild == p)Pre->lchild = NULL; else Pre->rchild = NULL; free(p); return true; } else if (!p->lchild || !p->rchild) { if (!Pre) { p = T; if (T->lchild)T = T->lchild; else T = T->rchild; free(p); return true; } if (p->lchild) { if (Pre->lchild == p)Pre->lchild = p->lchild; else Pre->rchild = p->lchild; } else { if (Pre->lchild == p)Pre->lchild = p->rchild; else Pre->rchild = p->rchild; } free(p); return true; } else { BiTree q; for (Pre = p,q = p->lchild; q->rchild; Pre = q, q = q->rchild); p->data = q->data; if (Pre->lchild == q)Pre->lchild = q->lchild; else Pre->rchild = q->lchild; } return true; } } return NOTFOUND; } int main() { int x, q, k; BiTree T = NULL; printf("输入操作次数："); scanf("%d", &q); while (q--) { printf("请输入k和x,中间用空格隔开，k为123时分别表示查找、插入、删除值为x的结点："); scanf("%d%d", &k, &x); if (k == 1) { deepth = 1; int t = Search(T, x); if (t == NOTFOUND)printf("没有找到这个数。\n"); else printf("找到了！,这个数在第%d层\n", deepth); } else if (k == 2) { if (Search(T, x) == NOTFOUND)Insert(T, x); else printf("该数已存在！\n"); } else { int t = Delete(T, x); if (t == NOTFOUND)printf("没找到你要删的数。\n"); else printf("删除成功！\n"); } printf("中序遍历序列为："); MidTraverse(T); puts(""); } return 0; } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |