精华内容
下载资源
问答
  • 前序遍历创建二叉树
    2022-06-06 17:18:43

    前序遍历的方式创建二叉树

    1. 树结点
    typedef struct treeNode* BT;
    struct treeNode {
    	int val;
    	treeNode* left;
    	treeNode* right;
    };
    
    1. 创建二叉树
    BT createTree() {
    	int data = 0;
    	BT root;
    	cin >> data;
    	if (data == -1) {
    		return nullptr;
    	}
    	root = new treeNode;
    	root->val = data;
    	root->left = createTree();
    	root->right = createTree();
    	return root;
    }
    
    1. 创建二叉树的另一种写法
    void createTree(BT& root) {//以引用的方式传递指针
    //不直接BT root传递的原因是 这里函数没有返回值,所以需要对参数进行地址传递,才能将传入的结点与创建的树连接起来
    	cout << "请输入数据" << endl;
    	int data = 0;
    	cin >> data;
    	if (data == -1) {
    		root=nullptr;//val为-1,则无需创建结点
    		return;
    	}
    	else {
    		root = new treeNode;
    		root->val = data;
    		createTree(root->left);
    		createTree(root->right);
    	}
    }
    
    1. 前序遍历
    void preOrder(BT root) {
    	if (root) {
    		cout << root->val << " ";
    		preOrder(root->left);
    		preOrder(root->right);
    	}
    }
    
    
    1. 中序遍历
    void inOrder(BT root) {
    	if (root) {
    		inOrder(root->left);
    		cout << root->val << " ";
    		inOrder(root->right);
    	}
    }
    
    1. 主函数
      int main() {
      BT root;
      //root = createTree();
      createTree();//两种创建树的函数可以写到一个文件里,发生函数重载
      cout << “前序遍历” << endl;
      preOrder(root);
      cout << endl;
      cout << “中序遍历” << endl;
      inOrder(root);
      return 0;
      }
    2. 实例
      2 ,3,6,-1,-1,4,-1,-1,1,5,-1,-1,2,-1,-1
      层序遍历的结果是2,3,1,6,4,5,2
    更多相关内容
  • 前序遍历创建二叉树

    千次阅读 2021-04-20 15:43:07
    最近学到二叉树,在递归创建二叉树时遇到了点问题,记录一下 二叉树的存储结构: /****** 二叉树 ********/ typedef struct BiTree{ char data; //数据段 struct BiTree * lchild; struct BiTree * rchild; }...

    最近学到二叉树,在递归创建二叉树时遇到了点问题,记录一下

    二叉树的存储结构:

    /****** 二叉树 ********/
    typedef struct BiTree{
        char data;       //数据段
        struct BiTree * lchild;	
        struct BiTree * rchild;
    }BiTree;
    

    书上面是每次递归调用的时候读取一个字符作为输入,我改了一下,通过一个字符串去创建。

    第一个版本:

    void ProOrderInputTree(char * input, BiTree * T)
    {
        if(*input == 0)
            return;
        if(*input == '#')
        {
            T = NULL;//扩展标志
        }
        else
        {
            T = (BiTree*)malloc(sizeof(BiTree));
            T->data = *input;
            ProOrderInputTree(input + 1, T->lchild);  
            ProOrderInputTree(input + 2, T->rchild);   
        }
    }
    

    思路很简单,把字符串第一个字符作为根的数据,第二个作为左孩子的数据,第三个作为右孩子的数据。
    但想一想之后发现不行,创建左子树返回后,input是从栈拿出来的,指向的位置不会变。而左子树的子孙个数是不一定的。

    于是我想到设置一个全局变量,指向当前结点的数据,它不是函数内的局部变量,不会进栈:

    char* c;
    void ProOrderInputTree(char * input, BiTree * T)
    {
    	c = input;
        if(*c== 0)
            return;
        if(*c== '#')
        {
        	c++;
            T = NULL;
        }
        else
        {
            T = (BiTree*)malloc(sizeof(BiTree));
            T->data = *c;
            c++;
            ProOrderInputTree(c, T->lchild);  
            ProOrderInputTree(c, T->rchild);   
        }
    }
    

    修改后发现还是不行,调试的时候发现,每次递归完后,T的左右孩子指向了无法访问的内存,这就很疑惑,每次传入的都是指针,为什么还是无法改变呢?

    在网上找了一圈,终于理解了,简单来说,当使用malloc创建内存时,函数参数T的值改变了,导致它的双亲无法找到它了。(经典的值传递无法改变变量的问题,只不过这次的‘值’是地址而已)

    知道原因就简单了,通过二级指针传递:

    char * c;
    void ProOrderInputTree(char * input, BiTree ** T)
    {
        c = input;
        if(*c == 0)
            return;
        if(*c == '#')
        {
            c++;
            *T = NULL;
        }
        else
        {
            (*T) = (BiTree*)malloc(sizeof(BiTree));
            (*T)->data = *c;
            c++;
            ProOrderInputTree(c, &(*T)->lchild); 
            ProOrderInputTree(c, &(*T)->rchild); 
        }
    }
    

    这样就可以实现了

    展开全文
  • 利用前序遍历构建二叉树(C语言)

    千次阅读 2021-10-28 18:24:29
    #include<stdio.h> #include<stdlib.h> struct TreeNode{ ...struct TreeNode *create_by_pre(struct TreeNode *T){/*利用前序遍历构建二叉树*/ char ch; printf("ch="); scanf("%c",&a.
    #include<stdio.h>
    #include<stdlib.h>
    struct TreeNode{
        char data;
        struct TreeNode *left;
        struct TreeNode *right;
    };
    struct TreeNode *create_by_pre(struct TreeNode *T){/*利用前序遍历构建二叉树*/
        char ch;
        printf("ch=");
        scanf("%c",&ch);
        getchar();
        if(ch=='#'){
            T=NULL;
        }else{
            T=(struct TreeNode *)malloc(sizeof(struct TreeNode));
            T->data=ch;
            T->left=create_by_pre(T->left);
            T->right=create_by_pre(T->right);
        }
        return T;
    }
    void preOrder(struct TreeNode *T){
        if(T!=NULL){
            printf("\t%c",T->data);
            preOrder(T->left);
            preOrder(T->right);
        }
    }
    void inOrder(struct TreeNode *T){
        if(T!=NULL){
            inOrder(T->left);
            printf("\t%c",T->data);
            inOrder(T->right);
        }
    }
    void postOrder(struct TreeNode *T){
        if(T!=NULL){
            postOrder(T->left);
            postOrder(T->right);
            printf("\t%c",T->data);
        }
    }
    int main(){
        struct TreeNode *T;
        T=NULL;
        T=create_by_pre(T);
        printf("前序遍历:");
        preOrder(T);
        printf("\n中序遍历:");
        inOrder(T);
        printf("\n后序遍历:");
        postOrder(T);
        return 0;
    }
    

     

     

    展开全文
  • 根据前序遍历和中序遍历创建二叉树 题目要求如下: 给定某一个二叉树前序遍历和中序遍历,要求据此创建一颗符合这样遍历顺序的二叉树前序遍历和中序遍历的概念以及特性: 前序遍历:先遍历节点本身,再遍历其...

    根据前序遍历和中序遍历创建二叉树

    题目要求如下:
    给定某一个二叉树的前序遍历和中序遍历,要求据此创建一颗符合这样遍历顺序的二叉树。

    在这里插入图片描述

    前序遍历和中序遍历的概念以及特性:

    • 前序遍历:先遍历节点本身,再遍历其左孩子,最后遍历其右孩子。
    • 中序遍历:先遍历其左孩子,再遍历节点本身,最后遍历其右孩子。
      我们根据这样的概念可以得出其特性:
    • 一棵树的前序遍历的第一个节点一定是这棵树的根节点
    • 一棵树的中序遍历中,在根节点前面遍历的节点构成根节点的左子树;在根节点后面遍历的节点构成根节点的右子树。

    由这样的两个特性,我们可以先由一棵树的前序遍历来获得这棵树的根节点,然后通过根节点与其中序遍历来分别得到其左右子树的节点数目。
    然后再根据左右子树的节点数目信息,我们可以从原先的根节点的前序遍历和中序遍历中截取出左右子树的前序遍历和中序遍历,之后这显然可以构成一个递归拆分问题,我们再将问题拆分成求解左右子树的根节点,将左右子树的根节点创建到根节点的左右孩子上,然后以此类推递归求解,最终可以构建出整颗二叉树。
    c语言的代码实现:

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 10000
      struct TreeNode {
          int val;
          struct TreeNode *left;
          struct TreeNode *right;
      };
    struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
     if(preorderSize==0||inorderSize==0) return NULL;
     if(preorder==NULL||inorder==NULL) return NULL;
     struct TreeNode *t=(struct TreeNode*)calloc(1,sizeof(struct TreeNode));
     //memset(t,0,sizeof(struct TreeNode));
     int root=preorder[0];
     int left_num=0,right_num=0,i=0,j=0,k=0;
     while(inorder[i]!=root)
     {
     	left_num++;
     	i++;
      } 
      right_num=preorderSize-1-left_num;
      t->val=root;
      t->left=buildTree(preorder+1,left_num,inorder,left_num);
      t->right=buildTree(preorder+1+left_num,right_num,inorder+1+left_num,right_num);
      return t;
    
    }
    LevelOrder(struct TreeNode *t)
    {
    	if(t==NULL) return 0;
    	struct TreeNode *queue[MAXSIZE];
    	struct TreeNode *temp=NULL;
    	int rear=0,front=0;
    	queue[rear++]=t;
    	while(rear!=front)
    	{
    		temp=queue[front];
    		printf("%d ",temp->val);
    		if(temp->left!=NULL)
    		{
    			queue[rear++]=temp->left;
    		}
    		if(temp->right!=NULL)
    		{
    			queue[rear++]=temp->right;
    		}
    		front++;
    	}
    }
    main()
    {
    	int size=5;
    	int preorder[5]={3,9,20,15,7};
    	int inorder[5]={9,3,15,20,7};
    	struct TreeNode *t=buildTree(preorder,size,inorder,size);
    
    	LevelOrder(t);
    }
    
    展开全文
  • 前序遍历+中序遍历重建二叉树

    千次阅读 多人点赞 2021-12-01 16:33:18
    考研数据结构:重建二叉树,本文实现利用前序遍历+中序遍历重建二叉树并给出具体实现的代码,题目来源:剑指 Offer 07. 重建二叉树
  • 根据一棵树的前序遍历与中序遍历构造二叉树思路代码二.根据一棵树的中序遍历与后序遍历构造二叉树思路代码 一.根据一棵树的前序遍历与中序遍历构造二叉树 输入某二叉树前序遍历和中序遍历的结果,请构建该二叉树并...
  • 利用二叉树前序遍历方法创建一棵二叉树(前序建立二叉树是输入的序列是:AB#D##C#E## ),然后对该二叉树进行前序遍历(非递归),并输出遍历结果 #include <stdio.h> #include <stdlib.h> typedef ...
  • 二叉树的遍历 我们知道知道 前序遍历 + 中序遍历 --------------- 可以确定唯一一棵二叉树 后序遍历 + 中序遍历 --------------- 可以确定唯一一颗二叉树 ...根据前序遍历和中序遍历重建二叉树 ...
  • 根据前序遍历和中序遍历建立二叉树 1. 递归法: 先序遍历:根节点→左子树→右子树。 中序遍历:左子树→根节点→右子树。 后续遍历:左子树→右子树→根节点。 根据前序遍历和中序遍历建立二叉树,根据以上性质可知...
  • 【数据结构刷题java】根据前序遍历和中序遍历构造二叉树 [题目链接](105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) (leetcode-cn.com)) 前序遍历的第一个都是根节点,所以从中序遍历中找到该根节点,根...
  • 给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 示例 1 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] ...
  • 1.前序遍历和中序遍历是如何决定二叉树前序遍历->根节点-左子树-右子树 中序遍历->左子树-根节点-右子树 通过前序遍历的每个子树的起始节点可以得到它的根结点, 在得到根结点之后带入中序遍历中可以分割出...
  • 二叉树的遍历分为前序遍历,中序遍历和后序遍历三种遍历方法。前序遍历的顺序为当前节点->左子节点->右子节点的顺序,中序遍历的顺序为左子节点->当前节点->右子节点的顺序,后序遍历的顺序是左子节点-&...
  • 前序遍历和中序遍历还原二叉树

    千次阅读 多人点赞 2021-12-11 15:17:11
    1.由前序遍历和中序遍历还原二叉树 对应letecode链接: 105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) (leetcode-cn.com) 题目描述: 给定一棵树的前序遍历preorder 与中序遍历inorder。请构造...
  • char* pre为前序遍历的顺序 char* in为中序遍历的顺序 首先建立一个指针p,用循环在in中找到根节点 left为左子树个数=p-in(指针差值) right为右子树个数(n-left-1) 之后递归调用该函数构建左右子树 代码: /** ...
  • 解题思路:前序遍历是根-》左-》右,那么第一个数一定是根节点,这里1就是根节点。中序遍历左-》根-》右,那么1拿到中序遍历就可以分割左、右子树,中序遍历左子树:4,3,2,6,5,8,7,右子树:10,9
  • 根据中序遍历与前序遍历确定二叉树 对于一棵树而言,前序遍历的形式为: [根节点,[左子树的前序遍历],[右子树的前序遍历]]。 中序遍历形式为: [[左子树的中序遍历],根节点,[右子树的中序遍历]] 因此,只要我们...
  • Java实现根据前序遍历构建二叉树(前序遍历、中序遍历、后序遍历),Java关于ACM的代码真的好少,想参考如何用java实现二叉树googl前言Java关于ACM的代码真的好少,想参考如何用java实现二叉树google了一上午都没找到...
  • 前序创建遍历二叉树

    千次阅读 2018-12-06 15:45:43
    题目: 利用二叉树的前序遍历来创建和遍历一个二叉树。 #include"stdio.h" #include"string.h" typedef struct NODE{ ...//创建一个二叉树(用前序遍历) /*在这个创建函数中...
  • 1,根据前序和中序恢复二叉树 2,打印二叉树的右视图 代码部分 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 求二叉树的右视图 * @param ...
  • 前序建立二叉树 3.三种遍历操作。 class BiTree /*这是一个最基本的二叉树类,所有的操作都在这个类里实现*/ { public: BiTree()/*默认构造函数,对根节点进行初始化操作*/ { root = new BiTreeNode(-1,nullptr,...
  • 我们考虑一种简单的情况,...我们可以再根据前序遍历和中序遍历还原这个二叉树,其原理为: 前序遍历总是按照根节点-左子树-右子树的顺序遍历,中序遍历总是按照左子树-根节点-右子树的顺序遍历,因此在初始状态下...
  • 已知前序遍历和中序遍历求二叉树

    千次阅读 多人点赞 2018-09-17 18:28:15
    输入某二叉树前序遍历和中序遍历的结果,请输出后序遍历序列。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},重建二叉树并返回...
  • 根据前序遍历和中序遍历构建二叉树 通过前序遍历和中序遍历 可以确定二叉树 (中+后也可以 ,但前+后不行)从而构建二叉树 通过前序遍历和中序遍历确定二叉树 Tip:以1为结点的前序遍历是 1 2 4 5 3 6 7 8 中序:4 2...
  • C实现前序遍历二叉树

    2019-08-05 23:22:50
    1. 实验目的 (1)掌握二叉树的逻辑结构; (2)掌握二叉树的二叉链表存储结构;... 定义二叉树的数据类型——二叉树结点结构体BiNode,在BiNode基础上实现题目要求的建立二叉链表、前序遍历等基...
  • 前序遍历创建二叉树。输入一字符串序列,空格表示子树为空,然后自动创建二叉树;前序遍历二叉,中序遍历二叉树
  • 关于通过前序遍历与中序遍历来创建二叉树,相信大家都用手工的方法推出来过,所以这里的算法思想就略过了。 二.源代码 BiTreeNode CreateBt(ElementType A[],ElementType B[],int PreL,int PreR,int InL,int InR) { ...
  • 文章目录 题目描述 题目分析及实现思路 根据前序遍历序列建立二叉树 题目实现完整代码 题目描述 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序...
  • 输入某二叉树前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,452
精华内容 12,580
关键字:

前序遍历创建二叉树