精华内容
下载资源
问答
  • 复制一棵二叉树
    万次阅读
    2016-10-30 18:58:07
    /**********
    【题目】编写复制一棵二叉树的递归算法。
    二叉链表类型定义:
    typedef char TElemType; // 设二叉树的元素为char类型
    typedef struct BiTNode {
      TElemType data;
      struct BiTNode  *lchild, *rchild;
    } BiTNode, *BiTree;
    **********/
    void CopyBiTree(BiTree T, BiTree &TT)
    /* 递归复制二叉树T得到TT */
    {
        if(T==NULL)
           return;
        else{
           TT=(BiTree)malloc(sizeof(BiTNode));
           TT->data=T->data;
           CopyBiTree(T->lchild,TT->lchild);
           CopyBiTree(T->rchild,TT->rchild);
           }
        
        
           
    }
    更多相关内容
  • 编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的...
  • 复制一棵二叉树

    2014-01-09 19:33:43
    复制一棵二叉树的C++程序。
  • // 设二叉树的元素为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);

    }

    }

    }

    展开全文
  • //printf ("正在建立个新二叉树,请输入结点的值:"); scanf ( "%d" , & x ) ; if ( x == 0 ) return NULL ; else { t = ( BTNode * ) malloc ( sizeof ( BTNode ) ) ; t -...

    好像有点问题。。。但是用测试代码测试 find_ancestors 函数时候,结果没有问题啊?为啥回到main里之后就弄不出来了。。。?

    #include <stdio.h>
    #include <malloc.h>
    
    typedef struct BTNode
    {
        int data;
        struct BTNode *left, *right;
    }BTNode;
    
    BTNode *creat_tree()
    {
        BTNode *t = NULL;
        int x;
        //printf ("正在建立一个新二叉树,请输入结点的值:");
        scanf ("%d", &x);
        if (x == 0)   return NULL;
        else
        {
            t = (BTNode *) malloc (sizeof(BTNode));
            t -> data = x;
            t -> left = creat_tree();
            t -> right = creat_tree();
        }
        return t;
    }
    
    //找某个结点的祖先结点方法:对二叉树进行【中】序遍历,当扫描到该结点时,栈中的结点都是祖先结点
    //为方便测试,假设各个结点值均不相同
    
    int find_ancestors(BTNode *bt, int x, BTNode *stack[]) //原本 【int x】 应为【BTNode *p】
    {   
        int top = -1;
        if (bt != NULL)
        {   
            BTNode *q = bt;        //q为工作指针,用于中序遍历
            while(q != NULL || top != -1)
            {   
                while (q!=NULL && q->data != x)
                {
                    stack[++top] = q;
                    q=q->left;
                }
                if (q->data == x)
                    return top;
                else
                {
                     if (top != -1)
                    {
                        q = stack[top--];
                        q = q->right;
                    }
                }
               
                
            }
            
        }   
        return top;
    }
    
    
    int main()
    {
        BTNode *tree = creat_tree();
        int px=0, qx=0;
        printf("请输入待操作的结点p的结点值:");
        scanf("%d", &px);
        printf("请输入待操作的结点q的结点值:");
        scanf("%d", &qx);
        
        BTNode *stack1[100];    int top1;
        BTNode *stack2[100];    int top2;
        
        top1 = find_ancestors(tree, px, stack1);
        top2 = find_ancestors(tree, qx, stack2);
        
        
        for (int i = top1; i>=0; --i)
        {   
            printf("%d", stack1[i]->data);
            for (int j = top2; j>=0; --j)
            {
                printf("%d", stack2[j]->data);
                if (stack1[i]->data == stack2[j]->data)
                    printf("%d", stack1[i]->data);
                    break;
            }
        }
        return 0;
    }
    
    
    //用于测试 find_ancestors函数是否正确,可删掉
    /*
    int main()
    {
        BTNode *tree = creat_tree();
        BTNode *stack[100];
        int x=0;
        printf("请输入待操作的结点的值:");
        scanf("%d", &x);
        int top = find_ancestors(tree, x, stack);
        
        for (int i=0; i<=top; ++i)
            printf("%d\n", stack[i]->data);
    
        return 0;
    }
    
    */
    
    展开全文
  • 设计个递归算法由二叉树BT复制产生另一棵二叉树BT1(假设二叉树采用二叉链存储结构) 源代码如下: #include <iostream> using namespace std; //二叉树的结构 typedef struct BTNode { char data; ...

    设计一个递归算法由二叉树BT复制产生另一棵二叉树BT1(假设二叉树采用二叉链存储结构)

    源代码如下:

    #include <iostream>
    using namespace std;
    
    //二叉树的结构
    typedef struct BTNode {
    	char data;
    	struct BTNode *left;
    	struct BTNode *right;
    }BTNode;
    
    //由二叉树BT复制产生另一棵二叉树BT1
    void copyBTree(BTNode*BT, BTNode*&BT1) {
    	if (BT==NULL) {
    		BT1 = NULL;
    	}else{
    		BT1 = (BTNode*)malloc(sizeof(BTNode));
    		BT1->data = BT->data;
    		copyBTree(BT->left, BT1->left);
    		copyBTree(BT->right, BT1->right);
    	}
    
    
    }
    
    
    //根据先序序列和中序序列递归创建二叉树
    BTNode * BTCreate(char a[], char b[], int n) {
    	int k;
    	if (n == 0) {
    		return NULL;
    	}
    	int root = a[0];
    	BTNode *BT = (BTNode *)malloc(sizeof(BTNode));
    	BT->data = root;   //树根的值可以确定了
    
    	for (k = 0; k < n; k++) {                  //在b中查找b[k]=root的根节点
    		if (b[k] == root) {
    			break;
    		}
    	}
    	BT->left = BTCreate(a + 1, b, k);               //递归创建左子树
    	BT->right = BTCreate(a + k + 1, b + k + 1, n - k - 1);        //递归创建右子树
    	return BT;
    }
    
    void PreOrder(BTNode *BTNode)
    {
    	if (BTNode == NULL)
    		return;
    	cout << BTNode->data << " ";
    
    	PreOrder(BTNode->left); //递归调用,先序遍历左子树 
    	PreOrder(BTNode->right); //递归调用,先序遍历右子树 
    
    }
    
    
    
    int main() {
    	int n = 0;
    	cout << "请输入序列个数" << endl;
    	cin >> n;
    
    	char *a = new char[n];
    	cout << "请输入先序序列" << endl;
    	for (int i = 0; i < n; i++) {
    		cin >> a[i];
    	}
    
    	char *b = new char[n];
    	cout << "请输入中序序列" << endl;
    	for (int i = 0; i < n; i++) {
    		cin >> b[i];
    	}
    
    	BTNode *BT = NULL;
    	BT = BTCreate(a, b, n);        //创建成功
    	PreOrder(BT);                    //检验是否创建成功
    	cout << endl;
    	BTNode *BT1 = NULL;
    	
    	copyBTree(BT, BT1);
    	
    	PreOrder(BT1);           //检验是否复制成功
    	cout << endl;
    
    
    	system("pause");
    	return 0;
    }

    输出为:

    请输入序列个数
    8
    请输入先序序列
    a b d g c e f h
    请输入中序序列
    d g b a e c h f
    a b d g c e f h
    a b d g c e f h
    请按任意键继续. . .

     

     

    展开全文
  • 复制二叉树

    2020-08-26 07:59:25
    复制一棵二叉树的非递归算法 */ #include <iostream> #include <deque> #include <malloc.h> using namespace std; typedef struct BTNode { int data; struct BTNode *left, *right; }*BiTree;...
  • 本程序提供了二叉树的各种操作:各种遍历,复制,求高度,判断是否为一棵完全二叉树以及计算用二叉树存储的表达式
  • 文章目录思路Java 实现 思路 Java 对象满足深拷贝,直接赋值不就行了,为什么要复制呢? 确实,Java 的对象赋值满足深拷贝,类似 C 中的地址赋值,那这样直接 a=b 不...如何复制二叉树呢? 其实就是写遍遍历而已 ...
  • 如何复制一棵二叉树

    2012-05-23 14:05:00
    1)如果树非空,则复制该根节点,同时,把这两个节点分别进入QueueFormer,QueueCopy (2)让pFormer指向QueueFormer的对头,pCopy指向QueueCopy的队头。 (3)pFormer的左右孩子,若非空,则复制其data,同时...
  • 复制一二叉树,先复制其根结点,再复制左子树,最后复制右子树,从而复制完成; 实现代码: # -*- coding:utf-8 -*- class BiTNode(): def __init__(self): self.data = None self.lchild = Non...
  • 判断两棵二叉树是否相似 简介:判断二叉树是否相似的方法就是:T1,T2都是空树,或者二叉树只有个根结点,,或者T1与T2的子树是相似的 算法思想:递归的思想就是判断把每个结点看成“根结点”进行操作即可 ...
  • 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 != ...
  • 遍历二叉树的非递归算法用到个栈,而复制的话用到两个栈,个存被复制二叉树个存复制到的二叉树。新的二叉树永远跟着已经存在的二叉树的节奏走,已经存在的那颗二叉树找左结点,新的二叉树也找左结点,已经...
  • 实现:二叉树复制、计算二叉树的深度、计算二叉树的结点。
  • 二叉树复制

    千次阅读 2016-08-05 19:30:43
    复制二叉树在二叉树的使用上常常需要备份原来的二叉树。如何复制直接看代码/********************************************************* - Copyright (C): 2016 - File name : copytree.c - Author : - Zhaoxinan -...
  • 用递归算法复制二叉树

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

    千次阅读 2019-05-23 18:32:14
    一棵二叉链表表示的二叉树中,复制一二叉树(利用java编程语言) 我的求解方法: 首先创建个泛型的数组,目的是为了存放二叉树(新复制)的标明空子树的先根序列,数组的长度为原来需要复制二叉树的长度...
  • 二叉树采用二叉链表存储,试写出复制一棵二叉树的算法。 话不多说上代码: #include #include typedef struct BiTnode {  int data;  struct BiTnode* Lchild,*Rchild; }BiTnode,*...
  • "如何复制二叉树"(python)

    千次阅读 2019-03-16 18:59:22
    题目描述:给定个二叉树根节点,复制该树,返回新建树的根节点。 分析与解答:用给定的二叉树的根节点root来构造新的二叉树的方法为:首先创建新的结点dupTree,然后根据root结点来构造dupTree结点,最后分别用root...
  • python实现复制二叉树

    2020-12-15 00:49:12
    python实现复制二叉树google笔试题题目描述:给定个二叉树根结点,复制该树,返回新建树的根结点 。分析与解答:用给定的二叉树的根结点 root来构造新的二叉树的方法为:首先创建新的结点 dupTree,然后根据 root 结点...
  • /* 邵发, 1309班, */ ...练习2:编写复制一棵二叉树 (不用递归) */ #include // 定义节点 struct Node { int value; Node* left, *right; }; // 练习1:交换左右孩子节点 void SwapChild
  • //算法5.4 复制二叉树 #include <iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode { char data; //结点数据域 struct BiNode *lchild, *rchild; //左右孩子指针 } ...
  • 平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。...
  • NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树 描述 给定一棵二叉树,已知其中的节点没有重复值,请判断该二叉树是否为搜索二叉树和完全二叉树。 示例1 输入: {2,1,3} 复制 返回值: [true,true] import java....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,270
精华内容 20,108
关键字:

复制一棵二叉树