C++ 复制二叉树

痛定思痛。 2023-10-08 11:31 26阅读 0赞

[原文链接][Link 1]

使用C++构建一个二叉树并复制、输出。

**程序：**

#include <stdio.h>
    #include <stdlib.h>
    //#include <cstdio>
    #include <vector>
    #include<iostream>
    #include <stack> 
    #include<cstdlib>
    
    #include <string>
    using namespace std;
    
    
    
    struct TreeNode          // 定义二叉树
    {
        int val;                       // 当前节点值用val表示
        struct TreeNode *left;     // 指向左子树的指针用left表示
        struct TreeNode *right;    // 指向右子树的指针用right表示
        TreeNode(int x) :val(x), left(NULL), right(NULL) { } // 初始化当前结点值为x，左右子树为空
    };
    
    
    //创建树
    TreeNode* insert(TreeNode* tree, int value)
    {
        
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); // 创建一个节点
        node->val = value;      // 初始化节点                            // malloc函数可以分配长度
        node->left = NULL;
        node->right = NULL;
    
        TreeNode* temp = tree;      // 从树根开始
        while (temp != NULL)
        {
            if (value < temp->val)  // 小于根节点就进左子树
            {
                if (temp->left == NULL)
                {
                    temp->left = node;  // 新插入的数为temp的左子树
                    return tree;
                }
                else           // 下一轮判断
                    temp = temp->left;
            }
            else           // 否则进右子树
            {    
    
                if (temp->right == NULL)
                {
                    temp->right = node;  // 新插入的数为temp的右子树
                    return tree;
                }
                else           // 下一轮判断
                    temp = temp->right;
            }
        }
        return tree;
    }
     
    //  ************* 输出图形二叉树 *************
    void output_impl(TreeNode* n, bool left, string const& indent)
    {
        if (n->right)
        {
            output_impl(n->right, false, indent + (left ? "|     " : "      "));
        }
        cout << indent;
        cout << (left ? '\\' : '/');
        cout << "-----";
        cout << n->val << endl;
        if (n->left)
        {
            output_impl(n->left, true, indent + (left ? "      " : "|     "));
        }
    }
    void output(TreeNode* root)
    {
        if (root->right)
        {
            output_impl(root->right, false, "");
        }
        cout << root->val << endl;
        if (root->left)
        {
            output_impl(root->left, true, "");
        }
        system("pause");
    }
    //  ******************************************
    
    
    
    void CopyBiTree(TreeNode* root, TreeNode* newroot) //  复制二叉树
    {
        if (root == nullptr)
            return;
        else
        {
            newroot->val = root->val;
            if (root->left != nullptr)
                newroot->left = new TreeNode(0);
            if (root->right != nullptr)
                newroot->right = new TreeNode(0);
    
            CopyBiTree(root->left, newroot->left);
            CopyBiTree(root->right, newroot->right);
        }
        //output(newroot);
    }
    
    
    // ====================测试代码====================
    int main()
    {
        TreeNode* tree =new TreeNode(10);       // 树的根节点
        TreeNode* treeresult;
    
        treeresult = insert(tree, 6);         // 输入n个数并创建这个树
        treeresult = insert(tree, 4);
        treeresult = insert(tree, 8);
        treeresult = insert(tree, 14);
        treeresult = insert(tree, 12);
        treeresult = insert(tree, 16);
    
        TreeNode* mirroot = new TreeNode(10);
        CopyBiTree(treeresult, mirroot); //  复制二叉树
        output(treeresult);         //  输出原二叉树
        output(mirroot);         //  输出复制的二叉树
    
    
    }

## 结果： ##

![20200104165715977.png][]

**学习更多编程知识，请关注我的公众号：**

[代码的路][Link 2]

![a67899eb2b384887a01d1e0f0f81cf67.jpeg][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=Mzg2Mjc3MDAwMA==&mid=2247483790&idx=1&sn=83159774eef4a5050abb0136ce5598a9&chksm=ce0387b1f9740ea702e44d5c6d867b33b24e8678112df00993ffb04c9e057681d9db5fbd6b88&token=412073603&lang=zh_CN#rd
[20200104165715977.png]: https://img-blog.csdnimg.cn/20200104165715977.png
[Link 2]: https://mp.weixin.qq.com/s?__biz=Mzg2Mjc3MDAwMA==&mid=2247483703&idx=1&sn=cf99bc33b9f0c281b3b0ae940ff71185&chksm=ce038708f9740e1e9aa19e720596a309156c5c153feb387473e5e8cb21fbde4a4814157769e8&token=1833633778&lang=zh_CN#rd
[a67899eb2b384887a01d1e0f0f81cf67.jpeg]: https://img-blog.csdnimg.cn/a67899eb2b384887a01d1e0f0f81cf67.jpeg