devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树的详细实现(C++)_二叉树c++实现

作者：繁依Fanyi0 | 2024-03-16 01:04:25

赞

踩

二叉树c++实现

关于二叉树的概念，已经在树的基本概念中详细描述，这里不做过多赘述。本文将对二叉树进行详细实现，采用 C++ 语言。

二叉树结点类型定义

template <typename T>
struct BinTreeNode
{
    T data;                                                                                                        //结点中存储的数据
    BinTreeNode<T> *leftChild, *rightChild;                                                                        //左子树和右子树
    BinTreeNode() : leftChild(NULL), rightChild(NULL) {}                                                           //无参构造函数
    BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

二叉树的类定义

下面是二叉树的一些常用的方法，各个方法具体实现在后面将会给出。

//二叉树的类声明
template <typename T>
class BinaryTree
{
public:
    //构造函数
    BinaryTree() : root(NULL) {}
    //指定结束标志的构造函数
    BinaryTree(T value) : root(NULL), RefValue(value) {}
    //析构函数
    ~BinaryTree();
    //拷贝构造函数，拷贝二叉树(前序遍历的应用)
    BinaryTree(BinaryTree<T> &s);

    //使用广义表创建二叉树，以'#'字符代表结束
    void CreateBinTree();
    //前序遍历创建二叉树(前序遍历的应用)，用#表示空结点
    void CreateBinTree_PreOrder();
    //使用先序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Pre_In(const char *pre, const char *in);
    //使用后序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Post_In(const char *post, const char *in);

    //先序遍历（递归）
    void PreOrder();
    //中序遍历(递归)
    void InOrder();
    //后序遍历（递归）
    void PostOrder();
    //先序遍历(非递归1)
    void PreOrder_NoRecurve1();
    //先序遍历(非递归2)
    void PreOrder_NoRecurve2();
    //中序遍历(非递归)
    void InOrder_NoRecurve();
    //后序遍历(非递归)
    void PostOrder_NoRecurve();
    //层次遍历(非递归)
    void LevelOrder();

    //获取二叉树的根节点
    BinTreeNode<T> *getRoot();
    //获取current结点的父节点
    BinTreeNode<T> *Parent(BinTreeNode<T> *current);
    //获取current结点的左结点
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *current);
    //获取current结点的右结点
    BinTreeNode<T> *RightChild(BinTreeNode<T> *current);

    //销毁函数
    void Destroy();
    //判断两颗二叉树是否相等(前序遍历的应用)
    bool operator==(BinaryTree<T> &s);
    //计算二叉树的结点的个数(后序遍历的应用)
    int Size();
    //计算二叉树的高度（后序遍历的应用）
    int Height();
    //判断二叉树是否为空
    bool Empty();
    //以广义表的形式输出二叉树(前序遍历的应用)
    void PrintBinTree();
    //翻转二叉树
    void InvertTree();

private:
    BinTreeNode<T> *root; //根节点
    T RefValue;           //数据输入停止的标志，需要一个构造函数
};

  • 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

二叉树的详细实现

二叉树的创建

1. 使用广义表创建二叉树

比如从广义表： A(B(D,E(G,)),C(,F))# 建立起来的二叉树如下：

二叉树的详细实现-图1

该算法的基本思路：

  1. 若是字母（假定以字母作为结点的值），则表示是结点的值，为它建立一个新的结点，并把该结点作为左子女（当 k=1）或右子女（当 k=2）链接到其父结点上。

  2. 若是左括号 (，则表明子表的开始，将 k 置为 1；若遇到的是右括号 )，则表明子表结束。

  3. 遇到的是逗号 ,，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将 k 置为 2。如此处理每一个字符，直到读入结束符 # 为止。

在算法中使用了一个栈 s，在进入子表之前将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。

//使用广义表创建二叉树函数,这里以"字符"创建二叉树,以'#'字符代表结束
void CreateBinTree(BinTreeNode<T> *&BT)
{
    stack<BinTreeNode<T> *> s;
    BT = NULL;
    BinTreeNode<T> *p = NULL; //p用来记住当前创建的节点，
    BinTreeNode<T> *t = NULL; //t用来记住栈顶的元素
    int k = 0;                //k是处理左、右子树的标记
    T ch;
    cin >> ch;

    while (ch != RefValue)
    {
        switch (ch)
        {
            case '(': //对(做处理
                s.push(p);
                k = 1;
                break;

            case ')': //对)做处理
                s.pop();
                break;

            case ',': //对,做处理
                k = 2;
                break;

            default:
                p = new BinTreeNode<T>(ch); //构造一个结点
                if (BT == NULL)             //如果头节点是空
                {
                    BT = p;
                }
                else if (k == 1) //链入*t的左孩子
                {
                    t = s.top();
                    t->leftChild = p;
                }
                else if(k == 2) //链入*t的右孩子
                {
                    t = s.top();
                    t->rightChild = p;
                }
        }
        cin >> ch;
    }
}

/*算法过程逐步分解，第一列是每次输入的字符，第二列是当前步骤p或k的值，第三列S表示栈中的元素，左边是栈顶：
A   p = A   S: 
(   k=1     S: A
B   p = B   A->left = B
(   k=1     S: B A
D   p = D   B->left = D
,   k=2
E   p = E   B->right = E
(   k=1     S: E B A
G   p = G   E->left = G
,   k=2
)           S: B A
)           S: A
,   k=2
C   p = C   A->right = C
(   k=1     S: C A
,   k=2
F   p = F   C->right = F
)           S: A
)           S:
#   end
*/

  • 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
2. 利用已知的二叉树的前序遍历创建

必须对应二又树结点前序遍历的顺序，并约定以输入序列中不可能出现的值作为空结点的值以结束递归，此值通过构造函数存放在 RefValue 中。例如用 # 表示正整数序列空结点。

二叉树的详细实现-图2

该二叉树前序遍历所得到的前序序列为：ABC##DE#G##F###。

构建该二叉树的算法基本思想是：

每读入一个值，就为它建立结点。该结点作为根结点，其地址通过函数的引用型参数 subTree 直接链接到作为实际参数的指针中。然后，分别对根的左、右子树递归地建立子树，直到读入# 建立空子树递归结束。

创建二叉树(利用已知的二叉树的前序遍历创建)用'#'表示空结点
void CreateBinTree_PreOrder(BinTreeNode<T> *&subTree)
{
    T item;
    if (cin >> item)
    {
        if (item != RefValue)
        {
            subTree = new BinTreeNode<T>(item); //构造结点
            if (subTree == NULL)
            {
                cout << "空间分配错误！" << endl;
                exit(1);
            }
            CreateBinTree_PreOrder(subTree->leftChild);  //递归创建左子树
            CreateBinTree_PreOrder(subTree->rightChild); //递归创建右子树
        }
        else
        {
            subTree = NULL;
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
3. 根据已知的前序遍历和中序遍历创建二叉树

根据前序遍历，先找到这棵树的根节点，也就是数组中第一个结点的位置，创建根节点。

然后在中序遍历中找到根的值所在的下标，切出左右子树的前序和中序。

注意：如果前序遍历的数组长度为 0，说明是一棵空树。

举例：

如果最终的二叉树如下：

二叉树的详细实现-图3

给出的前序遍历和中序遍历如下：

前序遍历：A B C D E
中序遍历：C D B A E

  • 1
  • 2

首先可以确定 A 是这棵树的根节点，然后根据中序遍历切出 A 的左右子树，得到 BCD 属于 A 的左子树，E 属于 A 的右子树，如下图：

二叉树的详细实现-图4

接着以 B 为根节点，在中序遍历中再次切出 B 的左右子树，得到 CD 为 B 的左子树，右子树为空。

二叉树的详细实现-图5

再以 C 为根节点，结合中序遍历，得到 D 为 C 的右子树，左子树为空。

二叉树的详细实现-图6

其代码实现如下：

//使用先序遍历和中序遍历创建二叉树
void CreateBinTreeBy_Pre_In(BinTreeNode<T> *&cur, const char *pre, const char *in, int n)
{
    if (n <= 0)
    {
        cur = NULL;
        return;
    }
    int k = 0;
    while (pre[0] != in[k]) //再中序中找到pre[0]的值
    {
        k++;
    }
    cur = new BinTreeNode<T>(in[k]); //创建结点
    CreateBinTreeBy_Pre_In(cur->leftChild, pre + 1, in, k);
    CreateBinTreeBy_Pre_In(cur->rightChild, pre + k + 1, in + k + 1, n - k - 1);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
4. 使用已知的后序遍历和中序遍历创建二叉树

根据后序遍历，先找到这棵树的根节点的值，也就是数组中最后一个节点（数组长度 -1）的位置，由此创建根节点。

然后在中序遍历中找到根的值所在的下标，切出左右子树的后续和中序。

注意：如果后序遍历的数组长度为 0，说明是一棵空树。

举例：

还是给出上面例子的二叉树的后序遍历和中序遍历：

中序遍历：C D B A E
后续遍历：D C B E A

  • 1
  • 2

由后序遍历可以确定 A 是这棵树的根节点，然后根据中序遍历切出 A 的左右子树，得到 CDB 属于 A 的左子树，E 属于 A 的右子树，如下图：

二叉树的详细实现-图7

接着以 B 为根节点，在中序遍历中再次切出 B 的左右子树，得到 CD 为 B 的左子树，右子树为空。

二叉树的详细实现-图8

再以 C 为根节点，结合中序遍历，得到 D 为 C 的右子树，左子树为空。

二叉树的详细实现-图9

其代码实现如下：

//使用后序遍历和中序遍历创建二叉树
void CreateBinTreeBy_Post_In(BinTreeNode<T> *&cur, const char *post, const char *in, int n)
{
    if (n == 0)
    {
        cur = NULL;
        return;
    }

    char r = *(post + n - 1);    //根结点值
    cur = new BinTreeNode<T>(r); //构造当前结点

    int k = 0;
    const char *p = in;
    while (*p != r)
    {
        k++;
        p++;
    }
    CreateBinTreeBy_Post_In(cur->leftChild, post, in, k);
    CreateBinTreeBy_Post_In(cur->rightChild, post + k, p + 1, n - k - 1);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

二叉树的递归遍历

1. 先序遍历

二叉树的先序遍历顺序为：根结点 -> 左孩子结点 -> 右孩子结点

//二叉树的先序遍历
void PreOrder(BinTreeNode<T> *&subTree)
{
    if (subTree != NULL)
    {
        cout << subTree->data << " ";
        PreOrder(subTree->leftChild);
        PreOrder(subTree->rightChild);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
2. 中序遍历

二叉树的中序遍历顺序为：左孩子结点 -> 根结点 -> 右孩子结点

//二叉树的中序遍历
void InOrder(BinTreeNode<T> *&subTree)
{
    if (subTree != NULL)
    {
        InOrder(subTree->leftChild);
        cout << subTree->data << " ";
        InOrder(subTree->rightChild);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
3. 后序遍历

二叉树的后序遍历顺序为：左孩子结点 -> 右孩子结点 -> 根节点

//二叉树的后序遍历
void PostOrder(BinTreeNode<T> *&subTree)
{
    if (subTree != NULL)
    {
        PostOrder(subTree->leftChild);
        PostOrder(subTree->rightChild);
        cout << subTree->data << " ";
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

二叉树的非递归遍历

1. 前序遍历

为了把一个递归过程改为非递归过程，一般需要利用一个工作栈，记录遍历时的回退路径。

二叉树的详细实现-图10

利用栈实现前序遍历的过程。每次访问一个结点后，在向左子树遍历下去之前，利用这个栈记录该结点的右子女（如果有的话）结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续其右子树的前序遍历。

//二叉树的先序遍历(非递归1)
void PreOrder_NoRecurve1(BinTreeNode<T> *p)
{
    stack<BinTreeNode<T> *> S;
    S.push(NULL); //最先push一个NULL，到最后一个结点没有左右子树时，栈里只有一个NULL了，令指针p指向这个NULL，再判断就会结束循环
    while (p != NULL)
    {
        cout << p->data << " ";
        if (p->rightChild != NULL) //预留右子树指针在栈中
        {
            S.push(p->rightChild);
        }

        if (p->leftChild != NULL) //进左子树
        {
            p = p->leftChild;
        }
        else //左子树为空
        {
            p = S.top();
            S.pop();
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

另一种前序遍历的方法。为了保证先左子树后右子树的顺序，在进栈时是先进右子女结点地址，后进左子女结点地址，出栈时正好相反。

//二叉树的先序遍历（非递归2）
void PreOrder_NoRecurve2(BinTreeNode<T> *p)
{
    stack<BinTreeNode<T> *> S;
    BinTreeNode<T> *t;
    S.push(p);         //根节点进栈
    while (!S.empty()) //当栈不为空
    {
        t = S.top(); //p先记住栈顶元素，然后栈顶出栈
        S.pop();
        cout << t->data << " ";    //访问元素
        if (t->rightChild != NULL) //右孩子不为空，右孩子近栈
        {
            S.push(t->rightChild);
        }
        if (t->leftChild != NULL) //左孩子不为空，左孩子进栈
        {
            S.push(t->leftChild);
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
2. 中序遍历

需要使用一个栈，以记录遍历过程中回退的路径。在一棵子树中首先访问的是中序下的第一个结点，它位于从根开始沿leftChild链走到最左下角的结点，该结点的leftChild指针为NULL。访问它的数据之后，再遍历该结点的右子树。此右子树又是二叉树，重复执行上面的过程，直到该子树遍历完。如下图：

二叉树的详细实现-图11

如果某结点的右子树遍历完或右子树为空，说明以这个结点为根的二叉树遍历完，此时从栈中退出更上层的结点并访问它，再向它的右子树遍历下去。

//二叉树的中序遍历(非递归)
void InOrder_NoRecurve(BinTreeNode<T> *p)
{
    stack<BinTreeNode<T> *> S;
    do
    {
        while (p != NULL)
        {
            S.push(p);
            p = p->leftChild;
        }
        if (!S.empty())
        {
            p = S.top();
            S.pop();
            cout << p->data << " ";
            p = p->rightChild;
        }
    } while (p != NULL || !S.empty());
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
3. 后序遍历

该思想是：

第 1 步：如果栈顶元素非空且左节点存在，将其压入栈中，如果栈顶元素存在左节点，将其左节点压栈，重复该过程。直到左结点不存在则进入第 2 步。

第 2 步：判断上一次出栈节点是否是当前栈顶结点的右节点（就是右叶子结点，如：G、F结点），或者当前栈顶结点不存在右结点(如：G，F，A结点)，将当前节点输出，并出栈。否则将当前栈顶结点右孩子节点压栈，再进入第 1 步。

二叉树的详细实现-图12

//二叉树的后序遍历(非递归)
void PostOrder_NoRecurve(BinTreeNode<T> *p)
{
    if (root == NULL)
        return;
    stack<BinTreeNode<T> *> s;
    s.push(p);
    BinTreeNode<T> *lastPop = NULL;
    while (!s.empty())
    {
        while (s.top()->leftChild != NULL)
            s.push(s.top()->leftChild);
        while (!s.empty())
        {
            //右叶子结点 || 没有右结点
            if (lastPop == s.top()->rightChild || s.top()->rightChild == NULL)
            {
                cout << s.top()->data << " ";
                lastPop = s.top();
                s.pop();
            }
            else if (s.top()->rightChild != NULL)
            {
                s.push(s.top()->rightChild);
                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
4. 层次遍历

按层次顺序访问二叉树的处理需要利用一个队列。在访问二又树的某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因此，每当访问一个结点时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样可以实现二又树结点的按层访问。

二叉树的详细实现-图13

//二叉树的层次遍历(非递归遍历)
void LevelOrder(BinTreeNode<T> *p)
{
    queue<BinTreeNode<T> *> Q;
    Q.push(p); //根节点进队
    BinTreeNode<T> *t;
    while (!Q.empty())
    {
        t = Q.front(); //t先记住队头,再将队头出队
        Q.pop();
        cout << t->data << " "; //访问队头元素的数据

        if (t->leftChild != NULL)
        {
            Q.push(t->leftChild);
        }

        if (t->rightChild != NULL)
        {
            Q.push(t->rightChild);
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

二叉树结点的个数

//计算二叉树以subTree为根的结点的个数
int Size(BinTreeNode<T> *subTree) const
{
    if (subTree == NULL) //递归结束，空树结点个数为0
    {
        return 0;
    }
    return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

二叉树的高度

//计算二叉数以subTree为根的高度
int Height(BinTreeNode<T> *subTree)
{
    if (subTree == NULL) //递归结束，空树高度为0
    {
        return 0;
    }
    int i = Height(subTree->leftChild);
    int j = Height(subTree->rightChild);
    return i < j ? j + 1 : i + 1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

以广义表的形式输出二叉树

//以广义表的形式输出二叉树
void PrintBinTree(BinTreeNode<T> *BT)
{
    if (BT != NULL) //树为空时结束递归
    {
        cout << BT->data;
        if (BT->leftChild != NULL || BT->rightChild != NULL)
        {
            cout << '(';
            if (BT->leftChild != NULL)
            {
                PrintBinTree(BT->leftChild);
            }
            cout << ',';
            if (BT->rightChild != NULL)
            {
                PrintBinTree(BT->rightChild);
            }
            cout << ')';
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

求二叉树某结点的父节点

//从结点subTree开始，搜索结点current的父节点,找到返回父节点的地址，找不到返回NULL
BinTreeNode<T> *Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
{
    if (subTree == NULL)
    {
        return NULL;
    }
    if (subTree->leftChild == current || subTree->rightChild == current) //如果找到，返回父节点subTree
    {
        return subTree;
    }
    BinTreeNode<T> *p;
    if (p = Parent(subTree->leftChild, current) != NULL) //递归在左子树中搜索
    {
        return p;
    }
    else
    {
        return Parent(subTree->rightChild, current); //递归右子树中搜索
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

二叉树的销毁

//二叉树的销毁
void Destroy(BinTreeNode<T> *&subTree)
{
    if (subTree != NULL)
    {
        Destroy(subTree->leftChild);
        Destroy(subTree->rightChild);
        delete subTree;
        subTree = NULL;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

判断两棵二叉树是否相等

//判断两颗二叉树是否相等
bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b)
{
    if (a == NULL && b == NULL) //两者都为空
    {
        return true;
    }
    if (a != NULL && b != NULL && a->data == b->data && equal(a->leftChild, b->leftChild) && equal(a->rightChild, b->rightChild)) //两者都不为空，且两者的结点数据相等，且两者的左右子树的结点都相等
    {
        return true;
    }
    return false;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

二叉树的复制

//复制二叉树，返回一个指针，给出一个以originNode为根复制的二叉树的副本
BinTreeNode<T> *Copy(BinTreeNode<T> *originNode)
{
    if (originNode == NULL)
    {
        return NULL;
    }
    BinTreeNode<T> *temp = new BinTreeNode<T>; //创建根结点
    temp->data = originNode->data;
    temp->leftChild = Copy(originNode->leftChild);
    temp->rightChild = Copy(originNode->rightChild);
    return temp;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

二叉树的翻转

/*二叉树的翻转
给定一颗二叉树
     4
   /   \
  2      7
 / \    / \
1   3  6   9
将二叉树翻转后：
     4
   /   \
  7      2
 / \    / \
9   6  3   1
*/
void InvertTree(BinTreeNode<T> *originNode)
{
	if (originNode == null)
		return null;
    BinTreeNode<T> * tempNode = originNode->leftChild;
    originNode.leftChild = originNode->rightChild;
    originNode.rightChild = tempNode;
    InvertTree(originNode->leftChild);
    InvertTree(originNode->rightChild);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

详细代码实现

#include <iostream>
#include <stack>
#include <queue>
#include <string.h>
using namespace std;

//二叉树结点类型定义
template <typename T>
struct BinTreeNode
{
    T data;                                                                                                        //结点中存储的数据
    BinTreeNode<T> *leftChild, *rightChild;                                                                        //左子树和右子树
    BinTreeNode() : leftChild(NULL), rightChild(NULL) {}                                                           //无参构造函数
    BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数
};

//二叉树的详细实现
template <typename T>
class BinaryTree
{
public:
    //构造函数
    BinaryTree() : root(NULL) {}
    //指定结束标志的构造函数
    BinaryTree(T value) : root(NULL), RefValue(value) {}
    //析构函数
    ~BinaryTree() { Destroy(root); }
    //拷贝构造函数，拷贝二叉树(前序遍历的应用)
    BinaryTree(BinaryTree<T> &s) { root = Copy(s.getRoot()); }

    //使用广义表创建二叉树，以'#'字符代表结束
    void CreateBinTree() { CreateBinTree(root); }
    //前序遍历创建二叉树(前序遍历的应用)，用#表示空结点
    void CreateBinTree_PreOrder() { CreateBinTree_PreOrder(root); }
    //使用先序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Pre_In(const char *pre, const char *in) { CreateBinTreeBy_Pre_In(root, pre, in, strlen(pre)); };
    //使用后序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Post_In(const char *post, const char *in) { CreateBinTreeBy_Post_In(root, post, in, strlen(post)); };

    //先序遍历（递归）
    void PreOrder() { PreOrder(root); }
    //中序遍历(递归)
    void InOrder() { InOrder(root); }
    //后序遍历（递归）
    void PostOrder() { PostOrder(root); }
    //先序遍历(非递归1)
    void PreOrder_NoRecurve1() { PreOrder_NoRecurve1(root); }
    //先序遍历(非递归2)
    void PreOrder_NoRecurve2() { PreOrder_NoRecurve2(root); }
    //中序遍历(非递归)
    void InOrder_NoRecurve() { InOrder_NoRecurve(root); }
    //后序遍历(非递归)
    void PostOrder_NoRecurve() { PostOrder_NoRecurve(root); }
    //层次遍历(非递归)
    void LevelOrder() { LevelOrder(root); }

    //获取二叉树的根节点
    BinTreeNode<T> *getRoot() const { return root; }
    //获取current结点的父节点
    BinTreeNode<T> *Parent(BinTreeNode<T> *current) { return (root == NULL || root == current) ? NULL : Parent(root, current); } //如果没有根节点或current结点就是root结点，就没有父节点
    //获取current结点的左结点
    BinTreeNode<T> *LeftChild(BinTreeNode<T> *current) { return (current != NULL) ? current->leftChild : NULL; }
    //获取current结点的右结点
    BinTreeNode<T> *RightChild(BinTreeNode<T> *current) { return (current != NULL) ? current->rightChild : NULL; }

    //销毁函数
    void Destroy() { Destroy(root); };
    //判断两颗二叉树是否相等(前序遍历的应用)
    bool operator==(BinaryTree<T> &s) { return (equal(this->getRoot(), s.getRoot())); }
    //计算二叉树的结点的个数(后序遍历的应用)
    int Size() { return Size(root); }
    //计算二叉树的高度（后序遍历的应用）
    int Height() { return Height(root); }
    //判断二叉树是否为空
    bool Empty() { return (root == NULL) ? true : false; }
    //以广义表的形式输出二叉树(前序遍历的应用)
    void PrintBinTree() { PrintBinTree(root); }
    //翻转二叉树
    void InvertTree() { InvertTree(root); }

protected:
    //使用广义表创建二叉树函数,这里以'字符'创建二叉树,以'#'字符代表结束
    void CreateBinTree(BinTreeNode<T> *&BT)
    {
        stack<BinTreeNode<T> *> s;
        BT = NULL;
        BinTreeNode<T> *p, *t; //p用来记住当前创建的节点，t用来记住栈顶的元素
        int k;                 //k是处理左、右子树的标记
        T ch;
        cin >> ch;

        while (ch != RefValue)
        {
            switch (ch)
            {
            case '(': //对(做处理
                s.push(p);
                k = 1;
                break;

            case ')': //对)做处理
                s.pop();
                break;

            case ',': //对,做处理
                k = 2;
                break;

            default:
                p = new BinTreeNode<T>(ch); //构造一个结点
                if (BT == NULL)             //如果头节点是空
                {
                    BT = p;
                }
                else if (k == 1) //链入*t的左孩子
                {
                    t = s.top();
                    t->leftChild = p;
                }
                else //链入*t的右孩子
                {
                    t = s.top();
                    t->rightChild = p;
                }
            }
            cin >> ch;
        }
    }
    //创建二叉树(利用已知的二叉树的前序遍历创建)用'#'表示空结点
    void CreateBinTree_PreOrder(BinTreeNode<T> *&subTree)
    {
        T item;
        if (cin >> item)
        {
            if (item != RefValue)
            {
                subTree = new BinTreeNode<T>(item); //构造结点
                if (subTree == NULL)
                {
                    cout << "空间分配错误！" << endl;
                    exit(1);
                }
                CreateBinTree_PreOrder(subTree->leftChild);  //递归创建左子树
                CreateBinTree_PreOrder(subTree->rightChild); //递归创建右子树
            }
            else
            {
                subTree = NULL;
            }
        }
    }
    //使用先序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Pre_In(BinTreeNode<T> *&cur, const char *pre, const char *in, int n)
    {
        if (n <= 0)
        {
            cur = NULL;
            return;
        }
        int k = 0;
        while (pre[0] != in[k]) //再中序中找到pre[0]的值
        {
            k++;
        }
        cur = new BinTreeNode<T>(in[k]); //创建结点
        CreateBinTreeBy_Pre_In(cur->leftChild, pre + 1, in, k);
        CreateBinTreeBy_Pre_In(cur->rightChild, pre + k + 1, in + k + 1, n - k - 1);
    }
    //使用后序遍历和中序遍历创建二叉树
    void CreateBinTreeBy_Post_In(BinTreeNode<T> *&cur, const char *post, const char *in, int n)
    {
        if (n == 0)
        {
            cur = NULL;
            return;
        }

        char r = *(post + n - 1);    //根结点值
        cur = new BinTreeNode<T>(r); //构造当前结点

        int k = 0;
        const char *p = in;
        while (*p != r)
        {
            k++;
            p++;
        }
        CreateBinTreeBy_Post_In(cur->leftChild, post, in, k);
        CreateBinTreeBy_Post_In(cur->rightChild, post + k, p + 1, n - k - 1);
    }
    //二叉树的先序遍历(递归)
    void PreOrder(BinTreeNode<T> *&subTree)
    {
        if (subTree != NULL)
        {
            cout << subTree->data << " ";
            PreOrder(subTree->leftChild);
            PreOrder(subTree->rightChild);
        }
    }
    //二叉树的中序遍历(递归)
    void InOrder(BinTreeNode<T> *&subTree)
    {
        if (subTree != NULL)
        {
            InOrder(subTree->leftChild);
            cout << subTree->data << " ";
            InOrder(subTree->rightChild);
        }
    }
    //二叉树的后序遍历(递归)
    void PostOrder(BinTreeNode<T> *&subTree)
    {
        if (subTree != NULL)
        {
            PostOrder(subTree->leftChild);
            PostOrder(subTree->rightChild);
            cout << subTree->data << " ";
        }
    }
    //二叉树先序遍历(非递归1)
    void PreOrder_NoRecurve1(BinTreeNode<T> *p)
    {
        stack<BinTreeNode<T> *> S;
        S.push(NULL); //最先push一个NULL，到最后一个结点没有左右子树时，栈里只有一个NULL了，令指针p指向这个NULL，再判断就会结束循环
        while (p != NULL)
        {
            cout << p->data << " ";
            if (p->rightChild != NULL) //预留右子树指针在栈中
            {
                S.push(p->rightChild);
            }

            if (p->leftChild != NULL) //进左子树
            {
                p = p->leftChild;
            }
            else //左子树为空
            {
                p = S.top();
                S.pop();
            }
        }
    }
    //二叉树先序遍历(非递归2)
    void PreOrder_NoRecurve2(BinTreeNode<T> *p)
    {
        stack<BinTreeNode<T> *> S;
        BinTreeNode<T> *t;
        S.push(p);         //根节点进栈
        while (!S.empty()) //当栈不为空
        {
            t = S.top(); //p先记住栈顶元素，然后栈顶出栈
            S.pop();
            cout << t->data << " ";    //访问元素
            if (t->rightChild != NULL) //右孩子不为空，右孩子近栈
            {
                S.push(t->rightChild);
            }
            if (t->leftChild != NULL) //左孩子不为空，左孩子进栈
            {
                S.push(t->leftChild);
            }
        }
    }
    //二叉树的中序遍历(非递归)
    void InOrder_NoRecurve(BinTreeNode<T> *p)
    {
        stack<BinTreeNode<T> *> S;
        do
        {
            while (p != NULL)
            {
                S.push(p);
                p = p->leftChild;
            }
            if (!S.empty())
            {
                p = S.top();
                S.pop();
                cout << p->data << " ";
                p = p->rightChild;
            }
        } while (p != NULL || !S.empty());
    }
    //二叉树的后序遍历(非递归)
    void PostOrder_NoRecurve(BinTreeNode<T> *p)
    {
        if (root == NULL)
            return;
        stack<BinTreeNode<T> *> s;
        s.push(p);
        BinTreeNode<T> *lastPop = NULL;
        while (!s.empty())
        {
            while (s.top()->leftChild != NULL)
                s.push(s.top()->leftChild);
            while (!s.empty())
            {
                //右叶子结点 || 没有右结点
                if (lastPop == s.top()->rightChild || s.top()->rightChild == NULL)
                {
                    cout << s.top()->data << " ";
                    lastPop = s.top();
                    s.pop();
                }
                else if (s.top()->rightChild != NULL)
                {
                    s.push(s.top()->rightChild);
                    break;
                }
            }
        }
    }
    //二叉树的层次遍历(非递归遍历)
    void LevelOrder(BinTreeNode<T> *p)
    {
        queue<BinTreeNode<T> *> Q;
        Q.push(p); //根节点进队
        BinTreeNode<T> *t;
        while (!Q.empty())
        {
            t = Q.front(); //t先记住队头,再将队头出队
            Q.pop();
            cout << t->data << " "; //访问队头元素的数据

            if (t->leftChild != NULL)
            {
                Q.push(t->leftChild);
            }

            if (t->rightChild != NULL)
            {
                Q.push(t->rightChild);
            }
        }
    }
    //从结点subTree开始，搜索结点current的父节点,找到返回父节点的地址，找不到返回NULL
    BinTreeNode<T> *Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current)
    {
        if (subTree == NULL)
        {
            return NULL;
        }
        if (subTree->leftChild == current || subTree->rightChild == current) //如果找到，返回父节点subTree
        {
            return subTree;
        }
        BinTreeNode<T> *p;
        if (p = Parent(subTree->leftChild, current) != NULL) //递归在左子树中搜索
        {
            return p;
        }
        else
        {
            return Parent(subTree->rightChild, current); //递归右子树中搜索
        }
    }
    //二叉树的销毁
    void Destroy(BinTreeNode<T> *&subTree)
    {
        if (subTree != NULL)
        {
            Destroy(subTree->leftChild);
            Destroy(subTree->rightChild);
            delete subTree;
            subTree = NULL;
        }
    }
    //复制二叉树，返回一个指针，给出一个以originNode为根复制的二叉树的副本
    BinTreeNode<T> *Copy(BinTreeNode<T> *originNode)
    {
        if (originNode == NULL)
        {
            return NULL;
        }
        BinTreeNode<T> *temp = new BinTreeNode<T>; //创建根结点
        temp->data = originNode->data;
        temp->leftChild = Copy(originNode->leftChild);
        temp->rightChild = Copy(originNode->rightChild);
        return temp;
    }
    //判断两颗二叉树是否相等
    bool equal(BinTreeNode<T> *a, BinTreeNode<T> *b)
    {
        if (a == NULL && b == NULL) //两者都为空
        {
            return true;
        }
        if (a != NULL && b != NULL && a->data == b->data && equal(a->leftChild, b->leftChild) && equal(a->rightChild, b->rightChild)) //两者都不为空，且两者的结点数据相等，且两者的左右子树的结点都相等
        {
            return true;
        }
        return false;
    }
    //计算二叉树以subTree为根的结点的个数
    int Size(BinTreeNode<T> *subTree) const
    {
        if (subTree == NULL) //递归结束，空树结点个数为0
        {
            return 0;
        }
        return 1 + Size(subTree->leftChild) + Size(subTree->rightChild);
    }
    //计算二叉数以subTree为根的高度
    int Height(BinTreeNode<T> *subTree)
    {
        if (subTree == NULL) //递归结束，空树高度为0
        {
            return 0;
        }
        int i = Height(subTree->leftChild);
        int j = Height(subTree->rightChild);
        return i < j ? j + 1 : i + 1;
    }
    //以广义表的形式输出二叉树
    void PrintBinTree(BinTreeNode<T> *BT)
    {
        if (BT != NULL) //树为空时结束递归
        {
            cout << BT->data;
            if (BT->leftChild != NULL || BT->rightChild != NULL)
            {
                cout << '(';
                if (BT->leftChild != NULL)
                {
                    PrintBinTree(BT->leftChild);
                }
                cout << ',';
                if (BT->rightChild != NULL)
                {
                    PrintBinTree(BT->rightChild);
                }
                cout << ')';
            }
        }
    }
    //翻转二叉树
    void InvertTree(BinTreeNode<T> *originNode)
    {
        if (originNode == NULL)
            return;
        BinTreeNode<T> *tempNode = originNode->leftChild;
        originNode->leftChild = originNode->rightChild;
        originNode->rightChild = tempNode;
        InvertTree(originNode->leftChild);
        InvertTree(originNode->rightChild);
    }

private:
    BinTreeNode<T> *root; //根节点
    T RefValue;           //数据输入停止的标志，需要一个构造函数
};

int main()
{
    //构造二叉树时指定二叉树的结束标志为 #
    BinaryTree<char> tree('#');

    //通过广义表创建二叉树
    // tree.CreateBinTree(); //input: A(B(D,E(G,)),C(,F))#
    // tree.PrintBinTree();  //print: A(B(D,E(G,)),C(,F))
    // cout << endl;

    //通过前序遍历创建二叉树
    // tree.CreateBinTree_PreOrder(); // input: ABD##EG###C#F##
    // tree.PrintBinTree();           // print: A(B(D,E(G,)),C(,F))

    //使用前序遍历和中序遍历创建二叉树
    // tree.CreateBinTreeBy_Pre_In("ABDEGCF", "DBGEACF");
    // tree.PrintBinTree(); // print: A(B(D,E(G,)),C(,F))
    // cout << endl;

    //使用后序遍历和中序遍历创建二叉树
    // tree.CreateBinTreeBy_Post_In("DGEBFCA", "DBGEACF");
    // tree.PrintBinTree(); // print: A(B(D,E(G,)),C(,F))
    // cout << endl;

    //二叉树的先序遍历(递归)
    // tree.PreOrder(); // print: A B D E G C F
    // cout << endl;

    //二叉树的中序遍历(递归)
    // tree.InOrder(); // print: D B G E A C F
    // cout << endl;

    //二叉树的后序遍历(递归)
    // tree.PostOrder(); // print: D G E B F C A
    // cout << endl;

    //二叉树先序遍历(非递归1)
    // tree.PreOrder_NoRecurve1(); // print: A B D E G C F

    //二叉树先序遍历(非递归2)
    // tree.PreOrder_NoRecurve2(); // print: A B D E G C F

    //中序遍历(非递归)
    // tree.InOrder_NoRecurve(); // print: D B G E A C F

    //二叉树的后序遍历(非递归)
    // tree.PostOrder_NoRecurve(); // print: D G E B F C A

    //二叉树的层次遍历(非递归)
    // tree.LevelOrder(); // print: A B C D E F G

    //二叉树的Size
    // cout << tree.Size() << endl; // print: 7

    //二叉树的销毁
    // tree.Destroy();
    // cout << tree.Size() << endl; // print: 0
    //二叉树是否为空
    // cout << tree.Empty() << endl; // print: 1

    //二叉树的高度
    // cout << tree.Height() << endl; // print: 4

    //拷贝二叉树
    // BinaryTree<char> tree2 = tree;
    // tree2.PrintBinTree(); // print: A(B(D,E(G,)),C(,F))

    //判断两颗二叉树是否相等
    // cout << (tree2 == tree) << endl; // print: 1

    //翻转二叉树
    // tree2.InvertTree();
    // tree2.PrintBinTree(); //print: A(C(F,),B(E(,G),D))

    return 0;
}

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/245909
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号