数据结构之二叉树（c++）_c++二叉树

​

数据结构之二叉树

目录：
1：二叉树概念
2：插入操作
3：删除操作
4：查找操作
5：4种遍历操作
6：清除操作
7：完整代码

二叉树概念：
二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两个互不相交的、分别称为根结点左子树和右子树的二叉树组成。
如下图中，图一是一个正确的二叉树，图二则不是二叉树，因为C结点有3个孩子。
​​​

二叉树的特点：
1.每个结点最多有两个子树，所以二叉树中不存在度大于2的结点。
2.左子树和右子树是有顺序的，次序不能颠倒。即使树中只有一颗子树，也要区分是左子树还是右子树。

二叉树的五种形态：
1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树，又有右子树。

特殊二叉树

满二叉树：
在一棵二叉树中，所有的分支结点都有左子树和右子树，并且所有的叶子结点都在同一层上，这样的二叉树称为满二叉树。如下图所示：

满二叉树有特点：
1.叶子结点只能出现在最下一层，出现在其他层就不能达到平衡，也就不是满二叉树了。
2.非叶子结点的度一定是2，如果有不是2的，那么此树就不是二叉树了。
3.在同样深度的二叉树中，满二叉树的结点个数最多，叶子结点最多。

完全二叉树：
对于一棵具有n个结点的二叉树按照层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵树称为完全二叉树。如下图所示：

注意：
如果没有结点6、结点7，而结点8、结点9仍存在，即结点3无孩子，那么这棵树就不是完全二叉树。
如果没有结点8，而结点9仍存在，即结点4只有右孩子，那么这棵树就不是完全二叉树。

完全二叉树特点：
1.叶子结点只能出现在最下两层。
2.最下一层的叶子结点一定集中在左侧连续位置。
3.倒数第二层，如果有叶子结点，一定都集中在右侧连续位置。
4.如果结点度为1，那么只能有左孩子。
5.同样结点数的二叉树，完全二叉树的深度最小。

​二叉树性质：
1.在二叉树的第i层上最多有2i-1个结点(i≥1)。
2.深度为k的二叉树最多有2k-1个结点(k≥1)。
3.对于任何一个二叉树，如果其叶子结点数为n0，度数为2的结点数为n2，那么n0=n2+1，也就是叶子结点数为度为2的结点数加1。
4.具有n个结点的完全二叉树深度为(log2n)+1。
5.对具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对二叉树的所有结点从1开始编号，则对于任意的序号为i的结点有:
A. 如果i>1，那么序号为i的结点的双亲结点序号为i/2;
B. 如果i=1，那么序号为i的结点为根节点，无双亲结点;
C. 如果2i<=n，那么序号为i的结点的左孩子结点序号为2i;
D. 如果2i>n，那么序号为i的结点无左孩子;
E. 如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1;
F. 如果2i+1>n，那么序号为i的结点无右孩子。
二叉树存储结构
在这，我们使用二叉链表的方式来构建一颗二叉树，如图所示

为了可以处理不同的数据类型，我们采用模板来进行编写
以下为二叉树的数据域，我们给出代码来描述

//数据域
template <class T>
struct Data
{
public:
    std::string number; //编号
    T value;            //值

public:
    Data(const std::string &Num, const T &Val) : number(Num), value(Val) {}
};
1
2
3
4
5
6
7
8
9
10
11

下面是树的节点表示

//节点
template <class T>
class Node
{
private:
    Data<T> data; //数据
    Node *left;   //左孩子指针
    Node *right;  //右孩子指针

public:
    Node(const std::string &Num, const T &Val, Node<T> *Left = nullptr, Node<T> *Right = nullptr)
        : data(Num, Val), left(Left), right(Right) {}
    //返回数据项,便于修改返回引用
    Data<T> &getData()
    {
        return (this->data);
    }
    //返回左孩子指针
    Node<T> *getLeft()
    {
        return (this->left);
    }
    //返回右孩子指针
    Node<T> *getRight()
    {
        return (this->right);
    }
    //设置左节点
    void setLeft(Node<T> *Left)
    {
        this->left = Left;
    }
    //设置右节点
    void setRight(Node<T> *Right)
    {
        this->right = Right;
    }
};
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

为了方便管理我们的树，我们给他进行一个封装

//二叉树结构
template <class T>
class BinaryTree
{
private:
    Node<T> *root; //根节点
    size_t size;   //二叉树的大小

public:
    BinaryTree();
    ~BinaryTree();
1
2
3
4
5
6
7
8
9
10
11
12

下面我们给出一些关于二叉树的一些操作

//查找节点
    Node<T> *findNode(const std::string &Number);
    //插入节点
    void insertNode(const Node<T> &node, const std::string &Number);
    //头部插入节点
    void push_front(const Node<T> &node);
    //删除节点
    void deleteNode(const std::string &Number);
    //清除所有节点
    void clear();
    //返回当前二叉树的大小
    size_t count();
    //判断当前二叉树是否为空
    bool empty();
    //前序遍历
    void perorder();
    //中序遍历
    void inorder();
    //后序遍历
    void postorder();
    //层次遍历
    void level();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

下面为这些操作所要用到的辅助函数

 //找父节点
    Node<T> *findParent(Node<T> *Root, const std::string &Number);
    //获取数据
    Node<T> &getData();
    //返回父节点
    Node<T> *getParent(const std::string &Number);
    //查找
    Node<T> *find(Node<T> *Root, const std::string &Number);
    //构造节点
    Node<T> *create(const Node<T> &node);
    //前序
    void perorderTraverse(Node<T> *root);
    //中序
    void inorderTraverse(Node<T> *root);
    //后序
    void postorderTraverse(Node<T> *root);
    //查找最后一个节点位置
    Node<T> *findLast(Node<T> *root);
    //删除根节点
    void deleRoot();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

判断树是否为空

这个操作比较简单，我们只需要判断根节点的指针是否为空或者判断当前树的大小是否为0即可

//判断当前二叉树是否为空BinaryTree<T>::
template <typename T>
bool BinaryTree<T>::empty()
{
    return (this->size == 0 && !this->root);
}
1
2
3
4
5
6

插入操作

第一种插入方式：

我们先介绍一种较为简单的插入节点的方式，即把新的节点直接插入到根节点的左子树上面或右子树上面,在这里小编采用将新的节点插入到左子树下面，
此时的插入有三种情况需要我们考虑：
1：树为空树（没有任何节点）
2：根节点的左子树为空
3：根节点的左子树不为空
第一种情况，我们很好解决，只需要把根节点指针指向新节点即可，如图所示：

第二种情况也比较好解决，我们只需要将根节点的左子树指针指向我们的新节点即可，如图所示：

第三种情况的解决方案：即先让新节点的左子树指针或者右子树指针先指向根节点左子树上的节点，然后让根节点的左子树指针指向新节点，如图所示：

接下来我们来看代码实现：

template <typename T>
void BinaryTree<T>::push_front(const Node<T> &node)
{
    //构造节点
    Node<T> *pNew = create(node);
    //当前树中是否存在节点
    if (this->root == nullptr)
    {
        //该节点成为新的节点
        this->root = pNew;
        //树的大小加一
        ++this->size;
        return;
    }
    //该节点设置成根节点
    pNew->setLeft(this->root);
    //更新根节点
    this->root = pNew;
    //树的大小加一
    ++this->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第二种插入方式：
把新节点插入到目标节点上面，这种插入方式需要知道目标节点的父节点的位置，需要遍历这课树，下面请看查找父节点的代码实现，

//返回父节点
template <typename T>
Node<T> *BinaryTree<T>::getParent(const std::string &Number)
{
    Node<T> *temp = this->root;
    //判断该数据是否在根结点上
    if (temp->getData().number == Number)
    {
        //根节点没有父节点，返回nullptr
        return nullptr;
    }
    //继续往树的下面查找
    return (this->findParent(temp, Number));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//找父节点
template <typename T>
Node<T> *BinaryTree<T>::findParent(Node<T> *Root, const std::string &Number)
{
    if (!Root)
    {
        return nullptr;
    }
    Node<T> *temp = Root;
    //对比该节点的左子树数据
    if (temp->getLeft() != nullptr && temp->getLeft()->getData().number == Number)
    {
        return temp;
    }
    //对比该节点的右子树数据
    else if (temp->getRight() != nullptr && temp->getRight()->getData().number == Number)
    {
        return temp;
    }
    //继续往下查找
    return findParent(temp->getLeft(), Number);
    return findParent(temp->getRight(), Number);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

找到父节点后，我们将新的节点插入到目标节点的父节点的左子树上面，

//插入节点
template <typename T>
void BinaryTree<T>::insertNode(const Node<T> &node, const std::string &Number)
{
    //获取父节点
    Node<T> *parent = this->getParent(Number);
    //构造节点
    Node<T> *nodePtr = this->create(node);
    if (!this->findNode(Number))
    {
        std::cout << "插入位置不存在" << std::endl;
        return;
    }
    //没有父节点，说明他是根节点
    if (!parent)
    {
        //将节点插入到根节点的左子树上面
        (nodePtr)->setLeft(this->root->getLeft());
        this->root->setLeft(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }
    //左子树是否为空
    if (!parent->getLeft())
    {
        //插入到父节点的左子树上
        parent->setLeft(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }
    //右子树是否为空
    else if (!parent->getRight())
    {
        //插入到父节点的右子树上
        parent->setRight(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }

    //插入到parent的左子树上面
    (nodePtr)->setLeft(parent->getLeft());

    parent->setLeft(nodePtr);
    //树的大小加一
    ++this->size;
}
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

树的删除操作

树的删除分为5种情况：
1：删除节点无左右子树，
2：删除节点有左子树无右子树，
3：删除节点有右子树无左子树
4：删除节点有左子树同时也有右子树
5：删除节点为根节点





在这里4和5这两种情况解决起来比较复杂，
4解决方案：我们将删除节点的左子树与删除节点的父节点的左子树或者右子树进行链接，然后把删除节点的右子树链接到末尾节点（无左右子树的节点）的左子树上面，如图所示：

5解决方案：把末尾节点（无左右子树的节点）放在原根节点的位置上面，
然后让根节点指针指向该节点，如图所示：

下面我们来看代码实现：

//删除节点
template <typename T>
void BinaryTree<T>::deleteNode(const std::string &Number)
{
    if (this->empty())
    {
        return;
    }
    //查找删除节点位置
    Node<T> *node = this->findNode(Number);
    if (!node)
    {
        //找不到节点返回空
        return;
    }
    Node<T> *parent = this->getParent(node->getData().number); //找寻删除节点的父节点
    //当删除节点为根节点时
    if (!parent)
    {
        this->deleRoot();
    }
    //判断删除节点的左右子树是否为空
    else if (!node->getLeft() && !node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //将左子树置为空
            parent->setLeft(nullptr);
        }
        else
        {
            //将右子树置为空
            parent->setRight(nullptr);
        }
        //释放节点
        delete node;
    }
    //删除节点的左右子树都不空
    else if(node->getLeft() && node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的左子树链接到父节点的左子树上
            parent->setLeft(node->getLeft());
            //把删除节点的右子树链接到末尾节点的左子树上
            Node<T> *last = this->findLast(this->root);
            last->setLeft(node->getRight());
        }
        else
        {
            //把删除节点的左子树链接到父节点的右子树上
            parent->setRight(node->getLeft());
            //把删除节点的右子树链接到末尾节点的左子树上
            Node<T> *last = this->findLast(this->root);
            last->setLeft(node->getRight());
        }
        //释放节点
        delete node;
    }
     //判断删除节点的左子树是否为空
    else if (node->getLeft())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的左子树链接到父节点的左子树上
            parent->setLeft(node->getLeft());
        }
        else
        {
            //把删除节点的左子树链接到父节点的右子树上
            parent->setRight(node->getLeft());
        }
        //释放节点
        delete node;
    }
    //判断删除节点的右子树是否为空
    else if (node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的右子树链接到父节点的左子树上
            parent->setLeft(node->getRight());
        }
        else
        {
            //把删除节点的右子树链接到父节点的右子树上
            parent->setRight(node->getRight());
        }
        //释放节点
        delete node;
    }
    --this->size;
}
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

//删除根节点
template <typename T>
void BinaryTree<T>::deleRoot()
{
    Node<T> *temp = this->root;                                //临时存储根节点
    Node<T> *last = this->findLast(this->root);                //找寻末尾节点
    Node<T> *parent = this->getParent(last->getData().number); //找寻末尾节点的父节点

    //链接根节点的左右子树
    last->setLeft(temp->getLeft());
    last->setRight(temp->getRight());
    //切断父节点与末尾节点之间的联系
    //判断末尾节点在父节点的左子树上还是右子树上
    if (!parent->getLeft() && parent->getLeft()->getData().number == last->getData().number)
    {
        //将左子树置为空
        parent->setLeft(nullptr);
    }
    else
    {
        //将右子树置为空
        parent->setRight(nullptr);
    }

    //删除根节点
    delete temp;
    //更新根节点
    this->root = last;
    if (this->root->getLeft() == this->root)
    {
        this->root->setLeft(nullptr);
    }
    else if (this->root->getRight() == this->root)
    {
        this->root->setRight(nullptr);
    }
}
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

查找操作

此操作实现非常简单，只需要遍历树，然后找到与之匹配的节点即可，代码实现如下所示：

//查找节点
template <typename T>
Node<T> *BinaryTree<T>::findNode(const std::string &Number)
{
    Node<T> *temp = this->root;
    return (find(temp, Number));
}

1
2
3
4
5
6
7
8

//查找
template <typename T>
Node<T> *BinaryTree<T>::find(Node<T> *Root, const std::string &Number)
{
    if (!Root)
    {
        return nullptr;
    }
    Node<T> *temp = Root;
    //匹配数据
    if (Number == temp->getData().number)
    {
        return temp;
    }
    //继续查找左右子树
    return find(temp->getLeft(), Number);
    return find(temp->getRight(), Number);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

树的遍历

1：前序遍历（根->左->右）
2：中序遍历（左->根->右）
3：后序遍历（左->右->根）
4：层次遍历
前序遍历（根->左->右）
即先访问树的根节点，后左子树节点，最后右子树节点，代码实现如下所示：

//前序遍历
template <typename T>
void BinaryTree<T>::perorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->perorderTraverse(temp);
}
1
2
3
4
5
6
7
8
9
10
11
12

//前序
template <typename T>
void BinaryTree<T>::perorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
    this->perorderTraverse(root->getLeft());
    this->perorderTraverse(root->getRight());
}
1
2
3
4
5
6
7
8
9
10
11
12
13

中序遍历（左->根->右）
即先访问树的左子树节点，后根节点，最后右子树节点，代码实现如下所示：

//中序遍历
template <typename T>
void BinaryTree<T>::inorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->inorderTraverse(temp);
}
1
2
3
4
5
6
7
8
9
10
11
12

//中序
template <typename T>
void BinaryTree<T>::inorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    this->inorderTraverse(root->getLeft());
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
    this->inorderTraverse(root->getRight());
}
1
2
3
4
5
6
7
8
9
10
11
12
13

后序遍历（左->右->根）
即先访问树的左子树节点，后右子树节点，最后根节点，代码实现如下所示：

//后序遍历
template <typename T>
void BinaryTree<T>::postorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->postorderTraverse(temp);
}
1
2
3
4
5
6
7
8
9
10
11
12

//后序
template <typename T>
void BinaryTree<T>::postorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    this->postorderTraverse(root->getLeft());
    this->postorderTraverse(root->getRight());
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

层次遍历

//层次遍历
template <typename T>
void BinaryTree<T>::level()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    std::queue<Node<T> *> que;
    //入队
    que.push(temp);

    while (!que.empty())
    {
        //获取队头元素
        Node<T> *data = que.front();
        std::cout << "节点编号：" << data->getData().number << " 节点值：" << data->getData().value << std::endl;
        //出队
        que.pop();
        //左子树不空
        if (data->getLeft())
            que.push(data->getLeft()); //入队
        //右子树不空
        if (data->getRight())
            que.push(data->getRight()); //入队
    }
}
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

清空所有节点

我们的删除方式为按层删除，即先删除第一层节点，后删除第二层节点，以此类推，代码实现如下所示：

//清除所有节点
template <typename T>
void BinaryTree<T>::clear()
{
    std::queue<Node<T> *> que;
    //入队
    que.push(this->root);

    while (!que.empty())
    {
        //获取队头元素
        Node<T> *data = que.front();
        //出队
        que.pop();
        //左子树不空
        if (data->getLeft())
            que.push(data->getLeft()); //入队
        //右子树不空
        if (data->getRight())
            que.push(data->getRight()); //入队
        //释放内存
        delete data;
        //树的大小减一
        --this->size;
    }
    //置空根节点，防止空悬指针出现
    this->root = nullptr;
}
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

完整代码

#ifndef BINARY_TREE_
#define BINARY_TREE_

#include <string>
#include <assert.h>
#include <iostream>
#include <queue>

//数据域
template <class T>
struct Data
{
public:
    std::string number; //编号
    T value;            //值

public:
    Data(const std::string &Num, const T &Val) : number(Num), value(Val) {}
};

//节点
template <class T>
class Node
{
private:
    Data<T> data; //数据
    Node *left;   //左孩子指针
    Node *right;  //右孩子指针

public:
    Node(const std::string &Num, const T &Val, Node<T> *Left = nullptr, Node<T> *Right = nullptr)
        : data(Num, Val), left(Left), right(Right) {}
    //返回数据项,便于修改返回引用
    Data<T> &getData()
    {
        return (this->data);
    }
    //返回左孩子指针
    Node<T> *getLeft()
    {
        return (this->left);
    }
    //返回右孩子指针
    Node<T> *getRight()
    {
        return (this->right);
    }
    //设置左节点
    void setLeft(Node<T> *Left)
    {
        this->left = Left;
    }
    //设置右节点
    void setRight(Node<T> *Right)
    {
        this->right = Right;
    }
};

//二叉树结构
template <class T>
class BinaryTree
{
private:
    Node<T> *root; //根节点
    size_t size;   //二叉树的大小

public:
    BinaryTree();
    ~BinaryTree();

private:
    //找父节点
    Node<T> *findParent(Node<T> *Root, const std::string &Number);
    //获取数据
    Node<T> &getData();
    //返回父节点
    Node<T> *getParent(const std::string &Number);
    //查找
    Node<T> *find(Node<T> *Root, const std::string &Number);
    //构造节点
    Node<T> *create(const Node<T> &node);
    //前序
    void perorderTraverse(Node<T> *root);
    //中序
    void inorderTraverse(Node<T> *root);
    //后序
    void postorderTraverse(Node<T> *root);
    //查找最后一个节点位置
    Node<T> *findLast(Node<T> *root);
    //删除根节点
    void deleRoot();

public:
    //查找节点
    Node<T> *findNode(const std::string &Number);
    //插入节点
    void insertNode(const Node<T> &node, const std::string &Number);
    //头部插入节点
    void push_front(const Node<T> &node);
    //删除节点
    void deleteNode(const std::string &Number);
    //清除所有节点
    void clear();
    //返回当前二叉树的大小
    size_t count();
    //判断当前二叉树是否为空
    bool empty();
    //前序遍历
    void perorder();
    //中序遍历
    void inorder();
    //后序遍历
    void postorder();
    //层次遍历
    void level();
};

template <typename T>
BinaryTree<T>::BinaryTree()
    : size(0), root(nullptr)
{
}

template <typename T>
BinaryTree<T>::~BinaryTree()
{
    //根节点不空
    if (this->root)
    {
        //清除所有数据
        this->clear();
    }
}

//获取数据
template <typename T>
Node<T> &BinaryTree<T>::getData()
{
    return (this->root);
}

//找父节点
template <typename T>
Node<T> *BinaryTree<T>::findParent(Node<T> *Root, const std::string &Number)
{
    if (!Root)
    {
        return nullptr;
    }
    Node<T> *temp = Root;
    //对比该节点的左子树数据
    if (temp->getLeft() != nullptr && temp->getLeft()->getData().number == Number)
    {
        return temp;
    }
    //对比该节点的右子树数据
    else if (temp->getRight() != nullptr && temp->getRight()->getData().number == Number)
    {
        return temp;
    }
    //继续往下查找
    Node<T>* result=nullptr;
    if(result=findParent(temp->getLeft(), Number))
    	return result;
    return findParent(temp->getRight(), Number);
}

//返回父节点
template <typename T>
Node<T> *BinaryTree<T>::getParent(const std::string &Number)
{
    Node<T> *temp = this->root;
    //判断该数据是否在根结点上
    if (temp->getData().number == Number)
    {
        //根节点没有父节点，返回nullptr
        return nullptr;
    }
    //继续往树的下面查找
    return (this->findParent(temp, Number));
}

//查找
template <typename T>
Node<T> *BinaryTree<T>::find(Node<T> *Root, const std::string &Number)
{
    if (!Root)
    {
        return nullptr;
    }
    Node<T> *temp = Root;
    //匹配数据
    if (Number == temp->getData().number)
    {
        return temp;
    }
    //继续查找左右子树
    return find(temp->getLeft(), Number);
    return find(temp->getRight(), Number);
}

//查找节点
template <typename T>
Node<T> *BinaryTree<T>::findNode(const std::string &Number)
{
    Node<T> *temp = this->root;
    return (find(temp, Number));
}

//构造节点
template <typename T>
Node<T> *BinaryTree<T>::create(const Node<T> &node)
{
    auto pNew = new Node<T>(node);
    //节点内存是否分配成功
    assert(pNew);
    return pNew;
}

//插入节点
template <typename T>
void BinaryTree<T>::insertNode(const Node<T> &node, const std::string &Number)
{
    //获取父节点
    Node<T> *parent = this->getParent(Number);
    //构造节点
    Node<T> *nodePtr = this->create(node);
    if (!this->findNode(Number))
    {
        std::cout << "插入位置不存在" << std::endl;
        return;
    }
    //没有父节点，说明他是根节点
    if (!parent)
    {
        //将节点插入到根节点的左子树上面
        (nodePtr)->setLeft(this->root->getLeft());
        this->root->setLeft(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }
    //左子树是否为空
    if (!parent->getLeft())
    {
        //插入到父节点的左子树上
        parent->setLeft(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }
    //右子树是否为空
    else if (!parent->getRight())
    {
        //插入到父节点的右子树上
        parent->setRight(nodePtr);
        //树的大小加一
        ++this->size;
        return;
    }

    //插入到parent的左子树上面
    (nodePtr)->setLeft(parent->getLeft());

    parent->setLeft(nodePtr);
    //树的大小加一
    ++this->size;
}

//头部插入节点
template <typename T>
void BinaryTree<T>::push_front(const Node<T> &node)
{
    //构造节点
    Node<T> *pNew = create(node);
    //当前树中是否存在节点
    if (this->root == nullptr)
    {
        //该节点成为新的节点
        this->root = pNew;
        //树的大小加一
        ++this->size;
        return;
    }
    //该节点设置成根节点
    pNew->setLeft(this->root);
    //更新根节点
    this->root = pNew;
    //树的大小加一
    ++this->size;
}

//查找左右子树节点都为空的节点
template <typename T>
Node<T> *BinaryTree<T>::findLast(Node<T> *root)
{
    if (!root)
    {
        return nullptr;
    }
    if (!root->getLeft() && !root->getRight())
    {
        return root;
    }
    //继续向下查找
    return findLast(root->getLeft());
    return findLast(root->getRight());
}

//删除根节点
template <typename T>
void BinaryTree<T>::deleRoot()
{
    Node<T> *temp = this->root;                                //临时存储根节点
    Node<T> *last = this->findLast(this->root);                //找寻末尾节点
    Node<T> *parent = this->getParent(last->getData().number); //找寻末尾节点的父节点

    //链接根节点的左右子树
    last->setLeft(temp->getLeft());
    last->setRight(temp->getRight());
    //切断父节点与末尾节点之间的联系
    //判断末尾节点在父节点的左子树上还是右子树上
    if (!parent->getLeft() && parent->getLeft()->getData().number == last->getData().number)
    {
        //将左子树置为空
        parent->setLeft(nullptr);
    }
    else
    {
        //将右子树置为空
        parent->setRight(nullptr);
    }

    //删除根节点
    delete temp;
    //更新根节点
    this->root = last;
    if (this->root->getLeft() == this->root)
    {
        this->root->setLeft(nullptr);
    }
    else if (this->root->getRight() == this->root)
    {
        this->root->setRight(nullptr);
    }
}

//删除节点
template <typename T>
void BinaryTree<T>::deleteNode(const std::string &Number)
{
    if (this->empty())
    {
        return;
    }
    //查找删除节点位置
    Node<T> *node = this->findNode(Number);
    if (!node)
    {
        //找不到节点返回空
        return;
    }
    Node<T> *parent = this->getParent(node->getData().number); //找寻删除节点的父节点
    //当删除节点为根节点时
    if (!parent)
    {
        this->deleRoot();
    }
    //判断删除节点的左右子树是否为空
    else if (!node->getLeft() && !node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //将左子树置为空
            parent->setLeft(nullptr);
        }
        else
        {
            //将右子树置为空
            parent->setRight(nullptr);
        }
        //释放节点
        delete node;
    }
    //删除节点的左右子树都不空
    else if(node->getLeft() && node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的左子树链接到父节点的左子树上
            parent->setLeft(node->getLeft());
            //把删除节点的右子树链接到末尾节点的左子树上
            Node<T> *last = this->findLast(this->root);
            last->setLeft(node->getRight());
        }
        else
        {
            //把删除节点的左子树链接到父节点的右子树上
            parent->setRight(node->getLeft());
            //把删除节点的右子树链接到末尾节点的左子树上
            Node<T> *last = this->findLast(this->root);
            last->setLeft(node->getRight());
        }
        //释放节点
        delete node;
    }
     //判断删除节点的左子树是否为空
    else if (node->getLeft())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的左子树链接到父节点的左子树上
            parent->setLeft(node->getLeft());
        }
        else
        {
            //把删除节点的左子树链接到父节点的右子树上
            parent->setRight(node->getLeft());
        }
        //释放节点
        delete node;
    }
    //判断删除节点的右子树是否为空
    else if (node->getRight())
    {
        //判断末尾节点在父节点的左子树上还是右子树上
        if (!parent->getLeft() && parent->getLeft()->getData().number == node->getData().number)
        {
            //把删除节点的右子树链接到父节点的左子树上
            parent->setLeft(node->getRight());
        }
        else
        {
            //把删除节点的右子树链接到父节点的右子树上
            parent->setRight(node->getRight());
        }
        //释放节点
        delete node;
    }
    --this->size;
}

//清除所有节点
template <typename T>
void BinaryTree<T>::clear()
{
    std::queue<Node<T> *> que;
    //入队
    que.push(this->root);

    while (!que.empty())
    {
        //获取队头元素
        Node<T> *data = que.front();
        //出队
        que.pop();
        //左子树不空
        if (data->getLeft())
            que.push(data->getLeft()); //入队
        //右子树不空
        if (data->getRight())
            que.push(data->getRight()); //入队
        //释放内存
        delete data;
        //树的大小减一
        --this->size;
    }
    //置空根节点，防止空悬指针出现
    this->root = nullptr;
}

//返回当前二叉树的大小
template <typename T>
size_t BinaryTree<T>::count()
{
    return this->size;
}

//判断当前二叉树是否为空BinaryTree<T>::
template <typename T>
bool BinaryTree<T>::empty()
{
    return (this->size == 0 && !this->root);
}

//前序
template <typename T>
void BinaryTree<T>::perorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
    this->perorderTraverse(root->getLeft());
    this->perorderTraverse(root->getRight());
}

//前序遍历
template <typename T>
void BinaryTree<T>::perorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->perorderTraverse(temp);
}

//中序
template <typename T>
void BinaryTree<T>::inorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    this->inorderTraverse(root->getLeft());
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
    this->inorderTraverse(root->getRight());
}

//中序遍历
template <typename T>
void BinaryTree<T>::inorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->inorderTraverse(temp);
}

//后序
template <typename T>
void BinaryTree<T>::postorderTraverse(Node<T> *root)
{
    if (!root)
    {
        //节点为空返回
        return;
    }
    this->postorderTraverse(root->getLeft());
    this->postorderTraverse(root->getRight());
    std::cout << "节点编号：" << root->getData().number << " 节点值：" << root->getData().value << std::endl;
}

//后序遍历
template <typename T>
void BinaryTree<T>::postorder()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    this->postorderTraverse(temp);
}

//层次遍历
template <typename T>
void BinaryTree<T>::level()
{
    if (this->empty())
    {
        std::cout << "树为空，无效遍历" << std::endl;
        return;
    }
    Node<T> *temp = this->root;
    std::queue<Node<T> *> que;
    //入队
    que.push(temp);

    while (!que.empty())
    {
        //获取队头元素
        Node<T> *data = que.front();
        std::cout << "节点编号：" << data->getData().number << " 节点值：" << data->getData().value << std::endl;
        //出队
        que.pop();
        //左子树不空
        if (data->getLeft())
            que.push(data->getLeft()); //入队
        //右子树不空
        if (data->getRight())
            que.push(data->getRight()); //入队
    }
}

#endif
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601