二叉搜索树的使用
//这一个版本写的是较为简单的树,分为了三个部分组成, 主要是利用栈的思想来进行前序遍历我们的树,本程序没有采用递归去前序遍历,用递归的话效率过低,不推荐使用. //本程序所实现的功能有 //插入元素(必须小于栈的最大容量). 前序遍历 二叉搜索树的删除(必须小于当前树内元素的个数) .再次前序遍历 .查找指定节点
teer.h #pragma once #define MAX_NODE 1024 typedef int ElemeType; typedef struct _Bnode { ElemeType data; //元素类型 struct _Bnode *lchild, *rchild; //指向左右孩子结点 }Bnode, Btree;
stack.h #pragma once #include<stdlib.h> #include<stdio.h> #include"tree.h" #define MaxSize 128 //预分配空间, 这个数值根据实际大小预估确定 typedef struct _SqStack { Bnode *base; //栈底指针 Bnode *top; //栈顶指针 }SqStack; //构造一个空栈S bool InitStack(SqStack &S) { S.base = new Bnode[MaxSize]; //为栈分配最大容量 if (!S.base) return false; //空间分配失败 S.top = S.base; //top初始化为base,空栈 return true; } //插入元素e为新的栈顶元素 bool PushStack(SqStack &S, Bnode e) { if (S.top - S.base == MaxSize) return false; //栈满 *(S.top++) = e; return true; } //删除S的栈顶元素,暂存在变量e bool PopStack(SqStack &S, Bnode &e) { if (S.base == S.top) return false; //栈空 e = *(--S.top); return true; } //返回S的栈顶元素,栈顶指针不变 Bnode *GetTop(SqStack &S) { if (S.top != S.base) { //栈非空 return S.top - 1; //返回栈顶元素的值,栈顶指针不变 } else { //这种情况是栈空的状况 return NULL; } } //返回栈中元素个数 int GetSize(SqStack &S) { return(S.top - S.base); } //判断栈是否为空 bool IsEmpty(SqStack &S) { if (S.top == S.base) { return true; } else { return false; } } //销毁栈 void DestroyStack(SqStack &S) { if (S.base) { free(S.base); S.base = NULL; S.top = NULL; } }
tree.cpp //1.插头 2. 全插 3.前序遍历 4.二叉搜索树的删除 5.再次前序遍历 6.查找指定节点 #include<iostream> #include<Windows.h> #include"stack.h" using namespace std; static int length = 0; //插入元素 bool InsertBnode(Btree* &root, Bnode* node) { Btree *tmp=NULL, *parent = NULL;; if (!node) return false; //待插入的节点为空时,直接就返回 //将待插入的节点的左右后指针清空,为了以后的插入做准备 node->lchild = NULL; node->rchild = NULL; //如果没有根节点那么,根节点的值就等于要插入结点的值 if (root->data == NULL) { root->data = node->data; length++; return true; } //再有根节点的情况下 tmp = root; //先让这个临时指针指向我们的根结点,代替我们的根节点移动从而去和要插入结点比较 while (tmp) { //遍历能比较的点,知道tmp指向的结点的左右子节点都不存在为止 parent = tmp; //让parent 充当现在的父节点,tmp就能继续向下实现遍历了 if (node->data > parent->data) { //当要插入结点大于我们的父节点时tmp继续向下遍历 tmp = tmp->rchild; } else { //当要插入结点小于我们的父节点时tmp继续向下遍历 tmp = tmp->lchild; } } //现在已经到了最后的结点了,现在比较带插入结点和这个parent结点哪个大就能确定待插入结点的位置 if (node->data > parent->data) { //待插入结点大于父节点 放右边 parent->rchild = node; } else { //待插入结点小于父节点 放左边 parent->lchild= node; } length++; return true; } //前序遍历 void proprint(Btree* root) { Btree tmp; SqStack stack; InitStack(stack); PushStack(stack, *root); //根节点进栈 while (!(IsEmpty(stack))) { //栈为空，所有节点均已处理 PopStack(stack, tmp); //要遍历的节点 printf("- %d -", tmp.data); //打印要便利的节点的值 if (tmp.rchild != NULL) { PushStack(stack, *(tmp.rchild)); //右子节点先入栈，后处理 } if (tmp.lchild != NULL) { PushStack(stack, *(tmp.lchild)); //左子节点后入栈，接下来先 处理 } } DestroyStack(stack); //将我们的之前创建好的栈销毁掉 } //寻找二叉搜索树左子树上最大的结点 int findMax(Btree* root) { //方式二 采用循环 while(root->rchild){ root = root->rchild; } return root->data; } //删除指定元素 Btree* DeleteNode(Btree* root, int key) { if (root == NULL) return NULL;//没有找到删除节点 if (root->data > key) { root->lchild = DeleteNode(root->lchild, key); return root; } if (root->data < key) { root->rchild = DeleteNode(root->rchild, key); return root; } //删除节点不存在左右子节点，即为叶子节点，直接删除 if (root->lchild == NULL && root->rchild == NULL) { length--; return NULL; } //删除节点只存在右子节点，直接用右子节点取代删除节点 if (root->lchild == NULL && root->rchild != NULL) { length--; return root->rchild; } //删除节点只存在左子节点，直接用左子节点取代删除节点 if (root->lchild != NULL && root->rchild == NULL){ length--; return root->lchild; } //删除节点存在左右子节点，直接用左子节点最大值取代删除节点 int val = findMax(root->lchild); root->data=val; root->lchild = DeleteNode(root->lchild,val); length--; return root; } /** * 使用非递归方式查找结点 */ bool QueryByLoop(Bnode* root, int Element) { while (root != NULL && root->data!= Element) { if (Element <root->data) { root = root->lchild; } else { root = root->rchild; } } if (root == NULL) { return false; } else { return true; } } int main(void) { Btree *s=new Btree; s->lchild = s->rchild = NULL; s->data = NULL; Bnode *node; //将第一个数据插入到树作为根节点 node = new Bnode; cout << "请输入你想要入树的元素个数(不得超过本栈的最大容量: " << MaxSize << "): "; int num=-1; cin >> num; //不让用户输入的值超过栈的最大容量 while (1) { if (num > MaxSize) { cout << "输入的个数超过了本栈的最大容量,请重新输入!!!! "; cout << "请输入你想要入树的元素个数(不得超过本栈的最大容量: " << MaxSize << "): "; cin >> num; } else { break; } } //插入头结点 cout << "请输入你想要插入的元素: "; cin>>node->data; if(InsertBnode(s, node)) { cout << "插入元素 " << node->data << "成功! " << endl; } else { cout << "插入元素失败! " << endl; } for (int i = 1; i < num; i++) { node = new Bnode; cout << "请输入你想要插入的元素: "; cin >> node->data; if (InsertBnode(s, node)) { cout << "插入元素 " << node->data << "成功! " << endl;; } else { cout << "插入元素失败! " << endl; } } //前序遍历树 proprint(s); cout << "一共有 " << length << " 个元素" << endl; //二叉搜索树的删除 cout << "请输入你要删除的元素的个数(不能超过现在的树的最大个数: " << length << "): "; int Element; cout << endl; cin >> num; while (1) { if (num > length) { cout << "输入的个数超过了本栈的最大容量,请重新输入!!!! "; cout << "请输入你想要入树的元素个数(不得超过本栈的最大容量: " << length << "): "; cin >> num; } else { break; } } for (int i = 0; i < num; i++) { cout << "请输入你想删除的值: "; cin >> Element; DeleteNode(s, Element); cout << "***********************************************" << endl; proprint(s); cout << "一共有 " << length << " 个元素)" << endl; cout << "***********************************************" << endl; } cout << "请输入你想要查找的值: " << endl; cin >> Element; if (QueryByLoop(s, Element)) { cout << "查找成功!! 查找的值是: " << Element << endl; } else { cout << "查找失败!不存在这个值" << endl; } proprint(s); cout << "一共有 " << length << " 个元素" << endl; system("pause"); return 0; }
