精华内容
下载资源
问答
  • 2019-07-07 11:13:24

    /*
    文件名:1_1_3_2.cpp
    作者:汤善康
    日期:2019年7月7日
    */

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>

    typedef int Status;
    typedef char BTelemtype;
    typedef struct BInode
    {
    BTelemtype data;
    struct BInode *lchild, *rchild;
    }BT, *Node;
    //先序遍历创建二叉树
    void create(Node &bt)
    {
    BTelemtype ch;
    scanf(" %c", &ch);
    if (ch ==’#’)//‘#’代表为空
    {
    bt = NULL;
    }
    else
    {
    bt = (Node)malloc(sizeof(BT));//申请结点空间
    if (!bt)
    {
    printf(“overlow”);
    }
    else
    {
    bt->data = ch;
    create(bt->lchild);//递归调用函数创建左子树结点
    create(bt->rchild);//递归调用函数创建右子树结点
    }
    }

    }
    //访问输出结点
    void visit(Node &L)
    {
    printf("%6c", L->data);
    }
    //先序遍历输出
    void PreOrder(Node &L)
    {
    if (L==NULL)//该结点为空
    return;
    else
    {
    visit(L);//访问打印该节点
    PreOrder(L->lchild);//对结点的左子树结点递归调用函数
    PreOrder(L->rchild);//对结点的右子树结点递归调用函数

    }
    

    }
    //中序遍历输出
    void InOrder(Node &L)
    {
    if (L == NULL)
    {
    return;
    }
    else
    {
    InOrder(L->lchild);
    visit(L);
    InOrder(L->rchild);

    }
    

    }
    //后序遍历输出二叉树
    void PostOrder(Node &L)
    {
    if (L == NULL)
    return;
    else
    {
    PostOrder(L->lchild);
    PostOrder(L->rchild);
    visit(L);
    }
    }
    int main()
    {
    Node L;

    int a;//欲选择的程序序号
    printf("******************\n");
    printf("1.先序遍历创建二叉树\n");
    printf("2.先序遍历输出二叉树\n");
    printf("3.中序遍历输出二叉树\n");
    printf("4.后序遍历输出二叉树\n");
    printf("*****************\n");
    while (1)
    {
    	printf("请输入要选择的程序序号:\n");
    	scanf("%d", &a);
    	switch (a)
    	{
    	case 1:
    	
    		printf("请按先序遍历输入:\n");
    		create(L);
    		break;
    	case 2:
    		printf("先序遍历输出结果为:\n");
    		PreOrder(L);
    		printf("\n");
    		break;
    	case 3:
    		printf("中序遍历输出结果为:\n");
    		InOrder(L);
    		printf("\n");
    		break;
    	case 4:
    		printf("后序遍历输出结果为:\n");
    		PostOrder(L);
    		printf("\n");
    		break;
    	}
    }
    

    }

    更多相关内容
  • // // binary_tree.cpp // BinaryTreeApp // // Created by ljpc on 2018/5/3. ...// #include "binary_tree.h" ...// 利用先序遍历创建二叉树 // 参数:先序遍历字符串s,字符串初始下标i=0,字符串.
    ​
    //
    //  binary_tree.cpp
    //  BinaryTreeApp
    //
    //  Created by ljpc on 2018/5/3.
    //  Copyright © 2018年 ljpc. All rights reserved.
    //
    
    #include "binary_tree.h"
    
    
    BiTreeNode* CreatBiTree(char* s, int &i, int len)
    // 利用先序遍历创建二叉树
    // 参数:先序遍历字符串s,字符串初始下标i=0,字符串长度len。
    // 返回:二叉树
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        BiTreeNode* T;
        if(s[i]=='#'&&i<=len)
        {
            i++;
            T=NULL;
        }
        else
        {
            T = (BiTreeNode*)malloc(sizeof(BiTreeNode));
            T->data=s[i++];
            T->left = CreatBiTree(s, i, len);
            T->right = CreatBiTree(s, i, len);
        }
        return T;
        /********** End **********/
    }
    void InOrder(BiTreeNode* root)
    // 二叉树的中序遍历
    // 参数:二叉树根节点root
    // 输出:中间没有空格,末尾不换行。
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        if(root!=NULL)
        {
            InOrder(root->left);
            printf("%c",root->data);
            InOrder(root->right);
        } 
        /********** End **********/
    
    }
    
    ​

    任务描述

    本关任务:利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。

    相关知识

    为了完成本关任务,你需要掌握:1.二叉树的前序遍历,2.如何创建一颗二叉树,3.二叉树的中序遍历。

    二叉树的前序遍历

    前序遍历preorder traversal是指按照先根节点,再左节点,最后右节点的次序访问二叉树中所有的节点,使得每个节点被访问且仅被访问一次。

    例:图1表示一个二叉树,前序遍历的顺序如节点上面数字所示,结果为ABCDEF

    如何创建一颗二叉树

    本关基于二叉链表存储定义了树节点数据结构:

     
    
    1. struct BiTreeNode {
    2. char data; // 树节点元素
    3. BiTreeNode* left; // 左子树指针
    4. BiTreeNode* right; // 右子树指针
    5. };

    利用先序遍历创建二叉树,我们需要知道先序遍历的叶子节点,通过增加符合#表示叶子节点的子节点,则图1的先序遍历为:ABC##D##EF###

    • 根据先序遍历的过程,首先创建根节点,然后使用递归的方法创建左子树节点,直到遇到符号#,表示到了叶子节点,回溯父节点并创建右子树节点。
    • 伪代码如下:
       
        
      1. BiTreeNode* CreatBiTree(char* s, int &i, int len)
      2. {
      3. root = new BiTreeNode(s[i++]); //创建根节点
      4. root->left = CreatBiTree(s, i, len); //递归创建左子树
      5. root->right = CreatBiTree(s, i, len); //递归创建右子树
      6. return root;
      7. }

    二叉树的中序遍历

    中序遍历inorder traversal是指按照先左节点,再根节点,最后右节点的次序访问二叉树中所有的节点,使得每个节点被访问且仅被访问一次。
    例:图2表示一个二叉树,中序遍历的顺序如节点上面数字所示,结果为CBDAFE

    编程要求

    本关的编程任务是补全右侧代码片段CreatBiTreeInOrderBeginEnd中间的代码,具体要求如下:

    • CreatBiTree中,利用先序遍历创建二叉树,并返回二叉树根节点指针。
    • InOrder中,完成二叉树的中序遍历,并输出遍历结果,中间没有空格,末尾不换行。

    测试说明

    平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

    以下是平台的测试样例:

    测试输入:ABC##D##EF###
    预期输出:CBDAFE

    测试输入:ABCD###E#F##G##
    预期输出:DCBEFAG

    展开全文
  • 在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)...
  • 以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下
  • 下面小编就为大家带来一篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 利用先序遍历输入法建立二叉树

    千次阅读 2022-02-10 13:38:56
    .利用先序遍历输入法建立二叉树

    题目:假设二叉树结点的数据为字符,即

    struct TreeNode { 

        char Data;

        struct TreeNode * Left;

        struct TreeNode * Right;

    };

    如果对该二叉树遍历打印并且以#代表空树,那么可以得到一个字符串,例如下面的二叉树:(注:设二叉树的结点数据不能为字符#)

    先序遍历结果为:ABC##DE##F###

    编写程序,输入一个类似于上面先序遍历结果的字符串,根据此字符串建立二叉树。(算法可参考教材126页)验证该二叉树是否正确。

    1.叉树/二叉排序树结构体:

    struct TreeNode{
    	int Data;
    	struct TreeNode*Left;
    	struct TreeNode*Right;
    };

    2.创建一颗空树:

    Struct TreeNode*T;
    T=NULL;

    3.关于树节点的计算,高度的计算等请看我的另一篇文章(二叉树的实现1):

    https://mp.csdn.net/mp_blog/creation/editor/122858841

    4.利用先序遍历输入法建立二叉树:

    struct TreeNode* Creat() {//在函数中不能进行传参
    	struct TreeNode*T;
    	printf("输入一个字符:\n");
    	char  ch;
    	scanf("%c",&ch);//一个一个字符的边输入边插入法
    	getchar(); //消掉在scanf函数中自带的换行符
    
    
    	if(ch=='#'){
    		T=NULL;//如果输入的为‘#’,则代表该结点为空
    	}else {
    		T=malloc(sizeof(struct TreeNode));//否则创建一个结点
    		T->Data=ch;//将输入的内容先存入根结点中
    		T->Left=Creat();//再调用本身函数将再次输入的结点存入左子树中
    		T->Right=Creat();//最后存入右子树中
    	}
    return T;	//返回插入内容后的树
    }

    实验源代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    struct TreeNode{
    	char Data;
    	struct TreeNode*Left;
    	struct TreeNode*Right;
    };
    //按先序遍历的顺序建立二叉树 
    struct TreeNode* Creat() {
    	struct TreeNode*T;
    	printf("输入一个字符:\n");
    	char ch;
    	scanf("%c",&ch);
    	getchar(); 
    
    
    	if(ch=='#'){
    		T=NULL;
    	}else {
    		T=malloc(sizeof(struct TreeNode));
    		T->Data=ch;
    		T->Left=Creat();
    		T->Right=Creat();
    	}
    return T;	
    }
    //先序遍历 
    void Preorder(struct TreeNode*T){
    	if(T!=NULL){
     		printf("%c",T->Data);
     		Preorder(T->Left);
     		Preorder(T->Right);
     	}
     	if(T==NULL)
    	 printf("#"); 
    }
    //中序遍历 
    void Inorder(struct TreeNode*T){
    	if(T!=NULL){
    	 	Inorder(T->Left);
     		printf("%c",T->Data);
     		Inorder(T->Right);
     	}
     	if(T==NULL)
    	 printf("#"); 
    }
    //后序遍历 
    void Postorder(struct TreeNode*T){
    	if(T!=NULL){
     		Postorder(T->Left);
     		Postorder(T->Right);
     		printf("%c",T->Data);
     	}
    	if(T==NULL)
    	 printf("#"); 
    }
    void Print(struct TreeNode*T){
         printf("先序遍历为:");
    	Preorder(T);
    	printf("\n"); 
    	
    	printf("中序遍历为:");
    	Inorder(T);
    	printf("\n");
    	
    	printf("后序遍历为:");
    	Postorder(T);
    	printf("\n"); 
    }
    int  main(){
    	struct TreeNode*T;
    
        T=Creat();
        
        Print(T);
        return 0;
    }

    实验结果:

     完结撒花!!!!!!!!!!!!!!!!!!!!!!!!!!!

    展开全文
  • 以扩展的先序遍历建立二叉树,根结点的地址通过函数值返回。例如输入AB#DF##G##C##,建立二叉树如下图,二叉树.png输出该二叉树的先序遍历序列ABDFGC。#include <stdio.h> #include <stdlib.h> typedef ...

    以扩展的先序遍历建立二叉树,根结点的地址通过函数值返回。

    例如

    输入AB#DF##G##C##,建立二叉树如下图,

    二叉树.png

    输出该二叉树的先序遍历序列ABDFGC。

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct BiTNode {
        ElementType data;
        struct BiTNode* lchild;
        struct BiTNode* rchild;
    }BiTNode, * BiTree;
    
    BiTree CreatBinTree();
    void  preorder(BiTree T);
    
    int main()
    {
        BiTree T = CreatBinTree();
        preorder(T);
        return 0;
    }
    void  preorder(BiTree T)
    {
        if (T)
        {
            printf("%c", T->data);
            preorder(T->lchild);
            preorder(T->rchild);
        }
    }
    BiTree CreatBinTree()
    {
        char ch; BiTree T;
        scanf("%c", &ch);
        if (ch == '#')//如果当前字符为#时说明当前节点为空,return NULL
            return NULL;
        T =(BiTree*)malloc(sizeof(BiTree));
        T->data = ch;
        T->lchild =CreatBinTree();//调用函数建立左孩子
        T->rchild =CreatBinTree();//调用函数建立右孩子
        return T;
    }
    展开全文
  • 假设现在有某二叉树先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列 分别以左子树和右子树为新树进行第一步操作 直至没有子树为止 那么我们...
  • 关于二叉树的概念:百度百科给的定义是:二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有...
  • 【06】先序遍历建立二叉树,并进行三种遍历

    千次阅读 多人点赞 2020-05-21 16:36:30
    printf("输入二叉树的先序遍历结点,建立二叉树。(子树为空时输入@)\n"); T=CreateBtree_DLR(T); printf("\n先序遍历的结果:\n"); PreOrder(T); printf("\n中序遍历的结果:\n"); InOrder(T); printf("\n...
  • import java.util.Scanner;public class LastBinaryTree {/*** 此题输入一组数据,便输出一个结果,都放在while循环里面,否则如果等while.../*** 根据前序遍历和中序遍历重建二叉树子树* @param preOrder 前序遍...
  • 输入格式:n,接下来二三行分别给出长度为n的先序遍历顺序和中序遍历顺序 7 4 1 3 2 6 5 7 1 2 3 4 5 6 7 下面是建树代码 tree Xtree(int a[],int b[],int l)//先序+中序 { if(!l) return NULL; tree t; int...
  • C++先序遍历的顺序建立二叉链表,
  • 题目: 根据先序遍历和中序遍历建立二叉树的二叉链表 并输出后序序列 思路: 根据先序序列确定根节点 在中序序列中找到根节点,将中序序列分成两段,前半段为根节点的左子树的中序序列,后半段为右子树的中序序列 ...
  • 思路:通过先序遍历建立链式二叉树 思路是对的,但是在实现的过程中,出现了一些问题。 错误代码: //结构体 typedef struct BTNode { char data; struct BTNode *pLchild; struct BTNode *pRchild; }BTNODE, *...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 一、已知先序遍历顺序,构建二叉树。(链式存储) 二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立二叉树。 前提知识: ...
  • 中序和先序遍历恢复二叉树python(年度更新系列) 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 这种问题的思路直接分三步走: 1.通过先序遍历找出根节点: rival = ...
  • 输入为:二叉树先序遍历结果(用&代表空指针的遍历结果) 例如:①输入a&&则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入12&&3&&则返回的指针指向的二叉树应该就是,根节点(1),左子树只有一...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 根据C语言数据结构第六版课本算法5.3 ...{ //算法5.3 按先序遍历输入二叉树中的节点的值 //构造二叉链表表示的二叉树T TElemType ch; scanf("%c",&ch); if(ch=="#") T==NULL;//空树 else { T=(BiTree)m
  • 这是建立的树 #include <stdio.h> #include <iostream> #include <stack> #include <queue> #include <malloc.h> using namespace std; #define MAXSIZE 100 typedef struct ...
  • title: 根据先序遍历和中序遍历建立二叉树 date: 2019-07-23 22:37:34 tags: 数据结构 问题 已知一棵二叉树的先序遍历以及中序遍历,重建二叉树。二叉树的每一个节点有三个属性,左子节点,右子节点,以及...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • } Status CreateBiTree_1(BiTree *T,char ch[]) //先序遍历创建节点,递归(自动输入) { static int i=-1; //静态变量 i++; if(ch[i]=='#') *T=NULL; else if(ch[i]!='\0') { *T=(BiTNode *)malloc(sizeof(BiTNode))...
  • 先序序列创建二叉树 tree creat(){ //前序序列创建二叉树 tree t; int ch; scanf("%d",&amp;ch); if(ch==0) { t=NULL;} else{ t=(tree)malloc(sizeof(node)); t-&gt;data=ch; t-&...
  • 分析二叉树遍历的性质 有上述性质,可以分享
  • 先序遍历为:ABDGECF 中序遍历为:DGBEAFC 创建结构体 定义二叉树中每个结点的数据,以及左右孩子。 typedef struct BiNode { char data; //结点数据 struct BiNode *lchild, *rchild; //左右子树指针 } BiNode...
  • 题目: 代码: #include<iostream> using namespace std; typedef struct BinaryTree { char data; struct BinaryTree* left; struct BinaryTree* right; }BT; void BinaryTreeCreate(BT*&... el.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,706
精华内容 11,082
关键字:

先序遍历创建二叉树