精华内容
下载资源
问答
  • 复制二叉树的算法
    2018-09-03 22:07:21

    算法思想步骤(整体的代码会和二叉树先序遍历算法相似)

    若二叉树不空,首先复制根节点,类似于先序遍历访问根节点的语句

    递归复制左子树

    递归复制右子树

    void CopyTree(BiTree T,BiTree NewT)
    {
        if(T==NULL)
        {
            NewT = NULL;
        }
        else
        {
            BiTree NewT = BiTree malloc(sizeof(BiNode));
            NewT->data = T->data;
            CopyTree(T->lchild,NewT->lchild);
            CopyTree(T->lchild,NewT->lchild);
        }
    }

    欢迎留言交流,若有错误或者疑问,欢迎指出

    更多相关内容
  • 1.二叉树的结构定义 typedef char Elemtype; //二叉树的结构定义 typedef struct csNode { Elemtype data; struct csNode*lchild; struct csNode*rchild; } Csnode,*tree; 2.二叉树的建立 //二叉树的建立 ...

    1.二叉树的结构定义

    typedef char Elemtype;
    //二叉树的结构定义
     typedef struct csNode
     {
     	Elemtype data;
     	struct csNode*lchild;
     	struct csNode*rchild;
      } Csnode,*tree;
    

    2.二叉树的建立

    //二叉树的建立
    void CreatTree(tree &T)//引用传参 
    {
    	char ch;
    	cin>>ch;
    	if(ch=='#')	
    		T=NULL;
    	else
    	{
    		T=new Csnode;
    		if(!T)
    			return;
    		(T)->data=ch;
    		printf("请输入%c的左子树: ",ch);
    		CreatTree((T)->lchild);
    		printf("请输入%c的右子树: ",ch);
    		 CreatTree((T)->rchild);
    	}
     } 
    

    3.复制二叉树

     //复制二叉树
     /*****如果是空树,递归结束
     		else,申请新节点空间复制根节点,
    		 递归复制左子树
    		 递归复制右子树*/
    int Copy(tree T,tree&NewT)
    {
    	if(T==NULL)
    	{
    		NewT=NULL; 
    		return 0;
    	}
    	else
    	{
    		NewT=new Csnode;
    		NewT->data=T->data;
    		Copy(T->lchild,NewT->lchild);
    		Copy(T->rchild,NewT->rchild);
    	}
     } 
    

    4.前序遍历算法

     //前序遍历算法
     void PreCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	cout<<T->data<<" ";
     	PreCreat(T->lchild);
     	PreCreat(T->rchild);
     }
    

    5.中序遍历算法

     //中序遍历算法
     void MidCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	MidCreat(T->lchild);
     	cout<<T->data<<" ";
     	MidCreat(T->rchild);
     }
    

    6.后序遍历算法

     //后序遍历算法
     void RearCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	RearCreat(T->lchild);
     	RearCreat(T->rchild);
     	cout<<T->data<<" ";
     }
    

    7.计算二叉树的深度

     //计算二叉树的深度
    int depth(tree T)
    {
    	int m,n;
    	if(T==NULL)
    		return 0;
    	else
    	{
    		m=depth(T->lchild);
    		n=depth(T->rchild);
    		if(m>n)
    			return (m+1);
    		else
    			return (n+1);
    	}
    	
     } 
    

    8.计算二叉树中的结点总数

     //计算二叉树中的结点总数
     //如果是空树,返回0,
     //else,节点个数=左子树结点个数加右子树节点个数+1;
     int NodeCnt(tree T)
     {
     	if(T==NULL)
     		return 0;
     	else
     		return NodeCnt(T->lchild)+NodeCnt(T->lchild)+1;	
      } 
    

    9.计算叶子节点的个数

    //计算叶子节点的个数
    /*****如果为空树,则叶子节点为0
    ******else, 叶子节点个数=左子树叶子结点个数加右子树叶子节点个数;*/ 
    int leafCnt(tree T)
    {
    	if(T==NULL)
     		return 0;
     	if(T->lchild==NULL&&T->rchild==NULL)
     		return 1;
     	else
     		return NodeCnt(T->lchild)+NodeCnt(T->lchild);	
     } 
    

    10.测试案例

    #include<iostream>
    using namespace std;
    typedef char Elemtype;
    //二叉树的结构定义
     typedef struct csNode
     {
     	Elemtype data;
     	struct csNode*lchild;
     	struct csNode*rchild;
      } Csnode,*tree;
    //二叉树的建立
    void CreatTree(tree &T)//引用传参 
    {
    	char ch;
    	cin>>ch;
    	if(ch=='#')	
    		T=NULL;
    	else
    	{
    		T=new Csnode;
    		if(!T)
    			return;
    		(T)->data=ch;
    		printf("请输入%c的左子树: ",ch);
    		CreatTree((T)->lchild);
    		printf("请输入%c的右子树: ",ch);
    		 CreatTree((T)->rchild);
    	}
     } 
     //复制二叉树
     /*****如果是空树,递归结束
     		else,申请新节点空间复制根节点,
    		 递归复制左子树
    		 递归复制右子树*/
    int Copy(tree T,tree&NewT)
    {
    	if(T==NULL)
    	{
    		NewT=NULL; 
    		return 0;
    	}
    	else
    	{
    		NewT=new Csnode;
    		NewT->data=T->data;
    		Copy(T->lchild,NewT->lchild);
    		Copy(T->rchild,NewT->rchild);
    	}
     } 
     //前序遍历算法
     void PreCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	cout<<T->data<<" ";
     	PreCreat(T->lchild);
     	PreCreat(T->rchild);
     }
     //中序遍历算法
     void MidCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	MidCreat(T->lchild);
     	cout<<T->data<<" ";
     	MidCreat(T->rchild);
     }
     //后序遍历算法
     void RearCreat(tree T)  
     {
     	if(T==NULL)
     		return ;
     	RearCreat(T->lchild);
     	RearCreat(T->rchild);
     	cout<<T->data<<" ";
     }
    
     //计算二叉树的深度
    int depth(tree T)
    {
    	int m,n;
    	if(T==NULL)
    		return 0;
    	else
    	{
    		m=depth(T->lchild);
    		n=depth(T->rchild);
    		if(m>n)
    			return (m+1);
    		else
    			return (n+1);
    	}
    	
     } 
     //计算二叉树中的结点总数
     //如果是空树,返回0,
     //else,节点个数=左子树结点个数加右子树节点个数+1;
     int NodeCnt(tree T)
     {
     	if(T==NULL)
     		return 0;
     	else
     		return NodeCnt(T->lchild)+NodeCnt(T->lchild)+1;	
      } 
    //计算叶子节点的个数
    /*****如果为空树,则叶子节点为0
    ******else, 叶子节点个数=左子树叶子结点个数加右子树叶子节点个数;*/ 
    int leafCnt(tree T)
    {
    	if(T==NULL)
     		return 0;
     	if(T->lchild==NULL&&T->rchild==NULL)
     		return 1;
     	else
     		return NodeCnt(T->lchild)+NodeCnt(T->lchild);	
     } 
     
    int main()
    {
    	printf("请输入第一个节点的数据:\n");
    	tree T;
    	CreatTree(T);
    	cout<<"前序遍历:"; 
    	PreCreat(T); 
    	cout<<"\n中序遍历:";
    	MidCreat(T) ;
    	cout<<"\n后序遍历:";
    	RearCreat(T) ;
    	cout<<"\n该二叉树的深度为:"<<depth(T)<<endl; 
    	cout<<"\n该二叉树的结点个数为:"<<NodeCnt(T)<<endl; 
    	cout<<"\n该二叉树的叶子结点个数为:"<<leafCnt(T)<<endl; 
    	cout<<"复制二叉树:"<<endl;
    	tree NewT;
    	Copy(T,NewT);
    	cout<<"复制后二叉树的前序遍历:"; 
    	PreCreat(NewT); 
    	cout<<"\n复制后二叉树的中序遍历:";
    	MidCreat(NewT) ;
    	cout<<"\n复制后二叉树的后序遍历:";
    	RearCreat(NewT) ;
     } 
    

    测试结果
    在这里插入图片描述

    展开全文
  • // 设二叉树的元素为char类型typedef struct BiTNode {TElemType data;BiTNode *lchild, *rchild;} BiTNode, *BiTree;可用队列类型Queue的相关定义:typedef BiTree QElemType; // 设队列元素为二叉树的指针类型...

    二叉链表类型定义:

    typedef char TElemType; // 设二叉树的元素为char类型

    typedef struct BiTNode {

    TElemType data;

    BiTNode *lchild, *rchild;

    } BiTNode, *BiTree;可用队列类型Queue的相关定义:

    typedef BiTree QElemType; // 设队列元素为二叉树的指针类型

    Status InitQueue(Queue &Q);

    Status EnQueue(Queue &Q, QElemType e);

    Status DeQueue(Queue &Q, QElemType &e);

    Status GetHead(Queue Q, QElemType &e);

    Status QueueEmpty(Queue Q);实现函数如下:

    void CopyBiTree(BiTree T, BiTree &TT)

    /* 基于层次遍历的非递归复制二叉链表 */

    {

    BiTree p1,p2;

    Queue Q1,Q2;

    if(!T){

    TT = NULL;

    return ;

    }

    TT = (BiTree)malloc(sizeof(BiTNode));

    InitQueue(Q1);

    InitQueue(Q2);

    EnQueue(Q1,T);

    EnQueue(Q2,TT);

    while(!QueueEmpty(Q1)){

    DeQueue(Q1,p1);

    DeQueue(Q2,p2);

    p2 -> data = p1 -> data;

    if(p1 ->lchild){//复制左子树

    EnQueue(Q1,p1 -> lchild);

    p2 -> lchild = (BiTree)malloc(sizeof(BiTNode));

    if(!p2 -> lchild){

    exit(OVERFLOW);

    }

    EnQueue(Q2,p2 -> lchild);

    }

    if(p1 ->rchild){//复制右子树

    EnQueue(Q1,p1 -> rchild);

    p2 -> rchild = (BiTree)malloc(sizeof(BiTNode));

    if(!p2 -> rchild){

    exit(OVERFLOW);

    }

    EnQueue(Q2,p2 -> rchild);

    }

    }

    }

    展开全文
  • 用递归算法复制二叉树

    千次阅读 多人点赞 2019-04-16 20:58:27
    最近做了一个简单的小问题如何复制一棵二叉树,自己在网上看了一些技术大佬写的总感觉写的有些复杂,所以自己尝试了一下。以想到关于二叉树算法问题,我觉得我们就应该去思考用递归的思想去试一下。所以经过思考...

    来自一位大一的小萌新博主
    最近做了一个简单的小问题如何复制一棵二叉树,自己在网上看了一些技术大佬写的总感觉写的有些复杂,所以自己尝试了一下。以想到关于二叉树的算法问题,我觉得我们就应该去思考用递归的思想去试一下。所以经过思考终于写出了最简洁的代码。
    二叉树的数据类型

    typedef struct  CSNode
    {
        char data;
    	struct CSNode *LeftTree;
    	struct CSNode *RightTree;
    }CSNode, *CSTree;
    

    复制二叉树的递归算法
    算法思路:就是用递归的思想去把每个节点复制出来。

    void Copy(CSTree T,CSTree &P)
    {
        if(T==NULL)
            return;
        else
        {
            P=(CSTree)malloc(sizeof(CSNode));
             P->data=T->data;
             P->LeftTree=T->LeftTree;
             P->RightTree=T->RightTree;
           Copy(T->LeftTree,P->LeftTree);
           Copy(T->RightTree,P->RightTree);
        }
    }
    

    以上内容是小萌新的第一篇博客写得不好请多多包含。
    喜欢的可以点个赞

    展开全文
  • 复制代码 代码如下:#!/usr/bin/env python#-*- coding:utf8 -*- class TreeNode(object): def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right class...
  • 复制二叉树

    千次阅读 2020-08-01 18:35:39
    //算法5.4 复制二叉树 #include <iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode { char data; //结点数据域 struct BiNode *lchild, *rchild; //左右孩子指针 } ...
  • 遍历二叉树的非递归算法用到一个栈,而复制的话用到两个栈,一个存被复制二叉树,一个存复制到的二叉树。新的二叉树永远跟着已经存在的二叉树的节奏走,已经存在的那颗二叉树找左结点,新的二叉树也找左结点,已经...
  • 文章目录思路Java 实现 思路 Java 对象满足深拷贝,直接赋值不就行了,为什么要复制呢? 确实,Java 的对象赋值满足深拷贝,类似 C 中的地址赋值,那这样直接 a=b 不...如何复制二叉树呢? 其实就是写一遍遍历而已 ...
  • 编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的...
  • 复制一颗二叉树,先复制其根结点,再复制左子树,最后复制右子树,从而复制完成; 实现代码: # -*- coding:utf-8 -*- class BiTNode(): def __init__(self): self.data = None self.lchild = Non...
  • 文章目录递归遍历前序遍历中序遍历后序遍历非递归遍历前序遍历中序遍历后序遍历层序遍历常见应用二叉树的最大深度最小深度复制二叉树二叉树节点个数二叉树叶子节点个数二叉树中第K层节点的个数销毁二叉树反转二叉树...
  • 二叉树的java算法

    2015-06-02 14:19:55
    这是二叉树的java算法,基本思路是通过二叉树的遍历,完成的java语法的算法编程
  • 主要介绍了二叉树前序遍历的非递归算法,需要的朋友可以参考下
  • 常见算法为:前/中/后序遍历二叉树(递归、非递归)及建立二叉链表、建立二叉树、层次遍历、复制二叉树、计算二叉树深度、统计二叉树节点等 1) #include <iostream> #include <cstdlib> using ...
  • C++ 复制二叉树

    千次阅读 2020-01-04 16:56:37
    } // ****************************************** void CopyBiTree(TreeNode* root, TreeNode* newroot) // 复制二叉树 { if (root == nullptr) return; else { newroot->val = root->val; if (root->left != ...
  • 二叉树算法时间复杂度

    千次阅读 2019-09-23 19:15:23
    二叉搜索树,平衡二叉树,红黑树的算法效率 操作二叉查找树平衡二叉树红黑树 查找 O(n) O(logn) Olog(n) 插入 O(n) O(logn) Olog(n) 删除 O(n) O(logn) Olog(n) Olog(n)怎么...
  • 复制一棵二叉树

    2014-01-09 19:33:43
    复制一棵二叉树的C++程序。
  • 文章目录先序遍历的顺序建立二叉链表复制二叉树计算二叉树的深度统计二叉树中结点的个数计算二叉树叶子结点数 先序遍历的顺序建立二叉链表 【算法步骤】 ①扫描字符序列,读入字符ch ②如果ch是一个“#”字符,则...
  • 复制一棵二叉树的递归算法

    万次阅读 2016-10-30 18:58:07
    【题目】编写复制一棵二叉树的递归算法。 二叉链表类型定义: typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode {  TElemType data;  struct BiTNode *lchild, *rchild; } ...
  • 二叉树采用二叉链表存储,试写出复制一棵二叉树算法。 话不多说上代码: #include #include typedef struct BiTnode {  int data;  struct BiTnode* Lchild,*Rchild; }BiTnode,*...
  • 实现:二叉树复制、计算二叉树的深度、计算二叉树的结点。
  • 重建二叉树算法题Java实现题目描述问题分析代码及讲解总结 题目描述 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序...
  • 通过C语言中的递归调用实现了二叉树中常用的前序遍历算法、中序遍历算法、后续遍历算法、求叶子结点算法、复制二叉树算法
  • 所有函数用到的树节点定义均如下: typedef struct node { char data; struct node *lchild;...二叉树的递归遍历 前序递归遍历 void preorder(NODE *root) { if(root != ...
  • 二叉树复制

    千次阅读 2019-01-11 20:07:17
    二叉树的建立相似 代码入下:  #include&lt;bits/stdc++.h&gt; #pragma execution_character_set("utf-8") using namespace std; typedef struct BiTNode{ char data; struct BiTNode *...
  • 本文实例讲述了JavaScript数据结构之二叉树的删除算法。分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点。如果删除没有子节点的节点就非常简单,如果节点只有一个子节点...
  • 设计一个递归算法二叉树BT复制产生另一棵二叉树BT1(假设二叉树采用二叉链存储结构) 源代码如下: #include <iostream> using namespace std; //二叉树的结构 typedef struct BTNode { char data; ...
  • } } 复制二叉树: void Copy(Tree *t,Tree *newt){ if(t=NULL){ newt=NULL;return; } if(!(newt=(TreeNode*)mallco(sizeof(TreeNode)))) return;//申请新结点空间; newt->data=t->data;//复制结点; Copy(t->...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 40,945
精华内容 16,378
关键字:

复制二叉树的算法