【数据结构与算法】二叉树

二叉树

一.二叉树的结构
二.二叉树的插入
- 1.根的插入
- 2.其他的插入
三.二叉树的删除
- 1.找到删除节点
- 2.删除节点的子节点只有一个或没有
- 3.删除节点的子节点有两个
四.完整代码

一.二叉树的结构

树的形式多种多样,但是我们最常用的还是二叉树.在二叉树中最长用的又数二叉搜索树.
在这里插入图片描述
这就是一个二叉搜索树,可以看到每个节点的左边都小于右边.

对于二叉树的实现,我们采用的链式结构

在这里插入图片描述

就是两个指针一个数据,跟双向链表差不多,但是两个节点之间不是双向连接.
左右指针都是指向的新的节点.

二.二叉树的插入

插入就要符合我们的规律,左边的的小于右边的.

1.根的插入

在这里插入图片描述
对要插入的节点,我们做防御性编程,同时对左右孩子设置为空.

当姚插入的是根节点是空,我们直接将新姚插入的节点设置为根节点.
如果不为空,先用变量进行保存,因为我们要进行遍历.

2.其他的插入

姚找到插入的位置就需姚遍历,找到要插入节点的父节点.
在这里插入图片描述
如果要插入的数据小于根节点的数据,就往左边遍历,否则右边遍历,直到tmp为空,那么parent就是要删除节点的父节点.

找到位置后然后进行插入:
在这里插入图片描述
如果要插入的数据小于父节点的数据,就插入在左边,否则右边.

三.二叉树的删除

对于删除稍稍有点复杂,有好几种情况如下.

1.找到删除节点

还是需要遍历到要删除节点:
在这里插入图片描述
如果当前节点不为空,同时当前节点的数据不是我们要删除的数据,那么我们一直遍历.
如果要删除节点的数据小于当前节点就往左边遍历,否则右边.

如果最后遍历为空,那么就是没有找到姚删除的节点.

2.删除节点的子节点只有一个或没有

当找到要删除的节点后,如果要删除节点的左边为空,就将姚删除节点的右边节点连接到要删除节点的位置,同理姚删除节点的右边为空的时候,就将要删除节点的左边连接到要删除的节点.
如果姚删除节点没有左右子节点了,那么连接的就是空.

在这里插入图片描述

如果父节点为空,那么就是要删除根节点,直接将刚刚子节点作为根节点.
在这里插入图片描述
要删除节点的父节点直接将原来的孩子改变成为原来孩子的孩子.

3.删除节点的子节点有两个

在这里插入图片描述
我们这里选择找右子树的最小值,先将要删除节点的右孩子找到,然后根据二叉搜索树的性质,我们需要一直找其左子节点,能够找到最小的值.
找到最小的值后,然后将其赋值给要删除的节点.

在这里插入图片描述

然后对刚刚找到的最小值位置进行删除,其父节点等于其要删除节点的孩子节点.
在这里插入图片描述

四.完整代码

#include <stdio.h>
#include <iostream>
#include <assert.h>typedef int ElemType;
#define isLess(a,b)(a<b)
#define isEqual(a,b)(a==b)typedef struct _Bnode
{ElemType data;struct _Bnode* lchild, * rchild;
}Bnode,Btree;bool InsertBtree(Btree** root, Bnode* node)
{Bnode* tmp = NULL;Bnode* parent = NULL;if (!node) {return false;}else{node->lchild = NULL;node->rchild = NULL;}if (*root){tmp = *root;}else{*root = node;return true;}while (tmp!=NULL){parent = tmp;printf("父节点: %d\n", parent->data);if (isLess(node->data, tmp->data)){tmp = tmp->lchild;}else{tmp = tmp->rchild;}}if (isLess(node->data, parent->data)){parent->lchild = node;}else{parent->rchild = node;}return true;
}int findMax(Btree* root)
{assert(root != NULL);/*if (root->rchild == NULL){return root->data;}return findMax(root->rchild);*/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)return NULL;if (root->lchild == NULL && root->rchild != NULL)return root->rchild;if (root->lchild != NULL && root->rchild == NULL)return root->lchild;int val = findMax(root->lchild);root->data = val;root->lchild = DeleteNode(root->lchild, val);return root;
}Btree* DeleteNodeNonRecursive(Btree* root, int key) {Btree* current = root;Btree* parent = NULL;while (current != NULL && current->data != key) {parent = current;if (key < current->data) {current = current->lchild;}else {current = current->rchild;}}if (current == NULL) {return root; // 未找到节点}// 处理叶子节点或只有一个子节点的情况if (current->lchild == NULL || current->rchild == NULL) {Btree* newCurrent;if (current->lchild == NULL) {newCurrent = current->rchild;}else {newCurrent = current->lchild;}if (parent == NULL) {root = newCurrent;}else if (parent->lchild == current) {parent->lchild = newCurrent;}else {parent->rchild = newCurrent;}}else { // 有两个子节点的情况Btree* successor = current->rchild;Btree* successorParent = current;while (successor->lchild != NULL) {successorParent = successor;successor = successor->lchild;}current->data = successor->data;if (successorParent->lchild == successor) {successorParent->lchild = successor->rchild;}else {successorParent->rchild = successor->rchild;}}return root;
}int main()
{int test[] = { 19,7,25,5,11,15,21,61 };Bnode* root = NULL, * node = NULL;for (int i = 0; i < sizeof(test) / sizeof(test[0]); i++){node = new Bnode;node->data = test[i];InsertBtree(&root, node);}DeleteNode(root, 5);system("pause");return 0;
}