实现二叉查找树C++_二叉搜索树c++

实现二叉查找树

\qquad 本文主要实现二叉查找树，实现二叉查找树的构建、查找和删除功能。

分析

1. 构建和查找功能按照二叉查找树的性质即可。
2. 删除时需要判断是1.类情况还是2.类情况，当是2.类情况时，需要找到待删除节点，判断是否具有左右子节点，找到大于待删除节点最小节点，节点互换后删除后找到的节点，最后还要挂载删除节点的左右节点。

FindBinaryTree 构建树数据结构

class FindBinaryTree 
{
public:
    FindBinaryTree(int val)
    {
        this->NodeLeft = NULL;
        this->NodeRight = NULL;
        this->val = val;
    };

    FindBinaryTree *NodeLeft; // 树左节点
    FindBinaryTree *NodeRight; // 树右节点
    int val; // 节点值
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

CreateFindBinaryTree(int val) 创建二叉查找树函数

FindBinaryTree* BinaryTreeNode = NULL;
void CreateFindBinaryTree(int val) // 创建二叉查找树
{
    if (BinaryTreeNode == NULL) // 当树的头节点为空时
    {
        FindBinaryTree* Node = new FindBinaryTree(val); 
        BinaryTreeNode = Node; // 新建树节点
    }
    else
    { 
        FindBinaryTree* FindTreeNode = BinaryTreeNode; // 节点需要移动因此将树节点保存到中间变量
        while (FindTreeNode != NULL)
        {
            if (val < FindTreeNode->val && FindTreeNode->NodeLeft != NULL)
                FindTreeNode = FindTreeNode->NodeLeft; // 当前值小于树节点的值，且左节点不为空，中间变量向左节点移动
            else if (val < FindTreeNode->val && FindTreeNode->NodeLeft == NULL)
            {
                FindBinaryTree* LinkTreeNode = new FindBinaryTree(val);
                FindTreeNode->NodeLeft = LinkTreeNode; // 当前值小于树节点的值，左节点为空，新建节点挂载在树节点的左侧
                break;
            }
            else if (val > FindTreeNode->val && FindTreeNode->NodeRight != NULL)
                FindTreeNode = FindTreeNode->NodeRight; // 当前值大于树节点的值，右节点不为空，中间变量向右节点移动
            else if (val > FindTreeNode->val && FindTreeNode->NodeRight == NULL)
            {
                FindBinaryTree* LinkTreeNode = new FindBinaryTree(val);
                FindTreeNode->NodeRight = LinkTreeNode; // 当前值大于树节点的值，右节点为空，新建节点挂载在树的右侧
                break;
            }
            else if (val == FindTreeNode->val)
                break; // 防止陷入死循环
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

FindNode(int val) 查找结点函数

bool FindNode(int val)
{
    FindBinaryTree* FindTreeNode = BinaryTreeNode;
    bool AnsBool = false;
    while (FindTreeNode != NULL)
    {
        if (val > FindTreeNode->val && FindTreeNode->NodeRight == NULL)
        {
            break;
        }
        else if (val > FindTreeNode->val && FindTreeNode->NodeRight != NULL)
        {
            FindTreeNode = FindTreeNode->NodeRight;
        }
        else if (val < FindTreeNode->val && FindTreeNode->NodeLeft == NULL)
        {
            break;
        }
        else if (val < FindTreeNode->val && FindTreeNode->NodeLeft != NULL)
        {
            FindTreeNode = FindTreeNode->NodeLeft;
        }
        else if (val == FindTreeNode->val)
        {
            AnsBool = true;
            break;
        }
    }
    return AnsBool;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

DeleteTreeNode(int val) 删除树节点函数

void DeleteTreeNode(int val)
{
    FindBinaryTree* FindTreeNode = BinaryTreeNode; // 节点中间变量
    FindBinaryTree *SaveTreeNode = NULL, *ParentTreeNode = NULL; // 保存树节点之后的节点 中间变量的父节点 
    
    while (FindTreeNode != NULL) // 中间变量不为空 
    { 
        if (val > FindTreeNode->val) 
        {
            ParentTreeNode = FindTreeNode; // 保存中间变量父节点 
            FindTreeNode = FindTreeNode->NodeRight; // 中间变量向右移动 
        }
        else if(val < FindTreeNode->val)
        {
            ParentTreeNode = FindTreeNode;
            FindTreeNode = FindTreeNode->NodeLeft; // 中间变量向左移动 
        }
        else
        {
            break; // 找到该节点 
        }
    }

    if (FindTreeNode == NULL) // 树中没有该元素或者树为空 
        return; // 返回 

    if (FindTreeNode->NodeLeft != NULL && FindTreeNode->NodeRight != NULL) // 找到的节点有左右节点 
    {// 若该判断条件为否，找到的节点为叶子节点、只有左节点或只有右节点，只要记录父节点和当前节点即可 
        FindBinaryTree* ParentTreeNode_ = FindTreeNode; // 保存父节点和当前节点 
        FindBinaryTree* FindTreeNode_ = FindTreeNode->NodeRight; // 这个函数块当删除节点为2.类情况，需要找到节点值大于当前节点值的最小节点，要找的节点在当前节点右子节点的最左节点或者就是当前节点的右子节点 
        while (FindTreeNode_->NodeLeft != NULL)  // 当前节点的左子树不为空 
        {
            ParentTreeNode_ = FindTreeNode_; // 继续移动 
            FindTreeNode_ = FindTreeNode_->NodeLeft;
        }
        FindTreeNode->val = FindTreeNode_->val; // 赋值到上个函数块找到的节点 

        FindTreeNode = FindTreeNode_; // 中间变量重新赋值 
        ParentTreeNode = ParentTreeNode_; // 中间变量父节点重新赋值 
    }
    // 以上完成待删除节点和待删除节点的父节点 
    if (FindTreeNode->NodeRight != NULL)  // 判断是否有左右子树 
    {
        SaveTreeNode = FindTreeNode->NodeRight; // 若有，则保存
    }
    else if (FindTreeNode->NodeLeft != NULL)
    {
        SaveTreeNode = FindTreeNode->NodeLeft;
    }
    
    if (ParentTreeNode == NULL) // 连接待删除结点和待删除节点的左右子树，完成节点删除 
    {
        BinaryTreeNode = SaveTreeNode;
    }
    else if (ParentTreeNode->NodeLeft == FindTreeNode)
    {
        ParentTreeNode->NodeLeft = SaveTreeNode;
    }
    else if (ParentTreeNode->NodeRight == FindTreeNode)
    {
        ParentTreeNode->NodeRight = SaveTreeNode;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

希望大家多提程序优化和编程规范的意见 ！！！