C++ 构建并复制二叉树

简介: C++ 构建并复制二叉树

使用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);         //  输出复制的二叉树


}

结果

二叉树1.png

学习更多编程知识,请关注我的公众号:

代码的路

相关文章
|
5月前
|
存储 算法 测试技术
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
数据结构学习记录——树习题-Complete Binary Search Tree(题目描述、输入输出示例、数据结构的选择、核心算法、计算左子树的规模)
77 1
|
5月前
|
存储 数据库 索引
B树和B+树的插入、删除图文详解
B树和B+树的插入、删除图文详解
68 0
|
5月前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
6月前
KD树的构建(递归
KD树的构建(递归
100 0
|
12月前
|
JSON 前端开发 Java
Java实现树的格式化打印以及返回前端json树
Java实现树的格式化打印以及返回前端json树
69 0
|
C语言 C++
【哈夫曼树】基本概念、构建过程及C++代码
【哈夫曼树】基本概念、构建过程及C++代码
249 0
|
存储 C++ 容器
使用C++编写一个图的深度和广度优先遍历的代码
使用C++编写一个图的深度和广度优先遍历的代码
110 0
|
前端开发
前端学习案例1-二叉搜索树删除两个节点的情况1
前端学习案例1-二叉搜索树删除两个节点的情况1
71 0
前端学习案例1-二叉搜索树删除两个节点的情况1
|
前端开发
前端学习案例2-二叉搜索树删除两个节点的情况2
前端学习案例2-二叉搜索树删除两个节点的情况2
63 0
前端学习案例2-二叉搜索树删除两个节点的情况2