二叉树算法算法【二叉树的创建、插入、删除、查找】
一、原理https://i-blog.csdnimg.cn/direct/0890f593239d4c158ab822481c26b9b6.png
1.1、二叉排序树的插入
https://i-blog.csdnimg.cn/direct/2fc309449e96421ab3a74b610c27be2f.png
https://i-blog.csdnimg.cn/direct/560016f5da0f4de88b2db2146b129ce8.png
https://i-blog.csdnimg.cn/direct/8146cbc8ef494861be2af0b9009c6616.png
https://i-blog.csdnimg.cn/direct/675956f19ebd465089378812d76cc89d.png
1.2、二叉树的删除
https://i-blog.csdnimg.cn/direct/b94007e359744e4e95477346a3b0cefe.png
（1）删除度为0的节点，就是末了的叶子节点，直接删除就可以了.
（2）删除度为1的节点，就是爷爷节点接收孙子节点。
https://i-blog.csdnimg.cn/direct/b0c62e15730843feb5d04a203fa2cb26.png
（3）删除度为2的节点就是找到该节点的前驱和后继，然后降当前节点与前驱节点的值交换，就酿成了前面两度为0或者1的节点删除的情况，然后在进行删除就可以了。
https://i-blog.csdnimg.cn/direct/fdc417006f0440fbab45baa76bfde402.png
https://i-blog.csdnimg.cn/direct/49eab4bac7b14b3dbfb7a50ababe9ab7.png
二、代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/* 对二叉树的的操作 */
/* 二叉树的节点 */
typedef struct Node
{
int key;
struct Node* Lchild, * Rchild;
}g_Node;
/* 创建一个节点 */
g_Node* getNewNode(int key)
{
g_Node* node = (g_Node*)malloc(sizeof(g_Node));
node->key = key;
node->Lchild = NULL;
node->Rchild = NULL;
return node;
}
/* 向树中某个节点后插入如一个随机数节点:采用递归的方式插入树中元素 */
//g_Node* insert(g_Node* root, int key)
//{
// if (NULL == root)return getNewNode(key);
// //随机插入树的左边或者右边
// if (rand() % 2)root->Lchild = insert(root->Lchild, key);
// else root->Rchild = insert(root->Rchild, key);
// return root;
//}
/* 向树中插入顺序树：创建二叉树 */
g_Node* insert(g_Node* root, int key)
{
if (NULL == root)return getNewNode(key);
//随机插入树的左边或者右边
if (key < root->key)root->Lchild = insert(root->Lchild, key);
else root->Rchild = insert(root->Rchild, key);
return root;
}
/* 从根节点清理掉一个树:采用递归深入清理的方式 */
void clear(g_Node* root)
{
if (NULL == root) return;
clear(root->Lchild);
clear(root->Rchild);
free(root);
return;
}
/* 二叉树打印函数：采用递归的方式，向内打印 */
int tot = 0;
void displayTree_V2(g_Node* root) {
if (root == NULL) return;
int start, end;
tot += 1;
start = tot;
if (root->Lchild) displayTree_V2(root->Lchild);
if (root->Rchild) displayTree_V2(root->Rchild);
tot += 1;
end = tot;
printf("%d : [%d, %d]\n", root->key, start, end);
return;
}
#define MAX_NODE 20
void displayTree_V1(g_Node* root) {
g_Node* queue;
int head, tail;
head = tail = 0;
queue = root;
while (head < tail) {
g_Node* node = queue;
printf("\nnode : %d\n", node->key);
if (node->Lchild) {
queue = node->Lchild;
printf("\t%d->%d (left)\n", node->key, node->Lchild->key);
}
if (node->Rchild) {
queue = node->Rchild;
printf("\t%d->%d (right)\n", node->key, node->Rchild->key);
}
head++; //如果打印到了结尾了，tail索引就不会在增加，但是head还是增加的，最终就会跳出循环
}
return;
}
/* 二叉树的查找:递归的方式向下查找 */
bool findBinaryTree(g_Node* root, int key)
{
bool ret;
if (NULL == root) return false;
if (key == root->key) return true;
if (key < root->key) ret = findBinaryTree(root->Lchild, key);
else ret = findBinaryTree(root->Rchild, key);
return ret;
}
/* 找到节点的前驱节点 */
g_Node* getProNode(g_Node* root)
{
if (NULL == root) return root;
root = root->Lchild;
while (root) root = root->Rchild;
return root;
}
/*
* 二叉树删除节点:
* （1）删除度为0的节点
* （2）删除度为1的节点
* （3）删除度为2的节点：找到节点的前驱，之后与前驱节点交换，
* 降为删除度为0和度为1的节点。
*/
g_Node* deleteNodeTree(g_Node* root, int key)
{
if (NULL == root) return root;
if (key < root->key) root->Lchild = deleteNodeTree(root->Lchild, key);
else if(key>root->key) root->Rchild = deleteNodeTree(root->Rchild, key);
else {
//删除度为0的节点
if (root->Lchild == NULL && root->Rchild == NULL)
{
free(root); //直接删除
return NULL;
} //删除度为1的节点
else if (root->Lchild == NULL || root->Rchild == NULL)
{ //root的子节点由root的父节点承接
g_Node* temp = root->Lchild ? root->Lchild : root->Rchild;
free(root);
return temp;
}
else//删除度为2的节点
{
g_Node* temp = getProNode(root); //找到节点的前驱
root->key = temp->key; //与前驱交换key数值
//继续递归调用，删除掉交换值后的节点，变成度为0、1的节点删除问题。
root->Lchild = deleteNodeTree(root->Lchild, temp->key);
}
}
return root;
}
int main()
{
g_Node* root = NULL;
for (int i = 0; i < MAX_NODE; i++) //创建二叉树
{
root = insert(root, rand() % 100);
}
displayTree_V1(root);
displayTree_V2(root);
int data = rand() % 100;
bool ret = findBinaryTree(root, data);
printf("find:%d, %d\r\n", ret, data);
deleteNodeTree(root, data);
displayTree_V2(root);
clear(root);
return 0;
} 终极的运行效果如下所示：
https://i-blog.csdnimg.cn/direct/e83d4c50a546463ea5d4587b7cd6ac75.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]