精华内容
下载资源
问答
  • 用先序遍历创建二叉树
    2022-05-21 23:57:17

    题目描述

    利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树的层次遍历序列。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系,这会最终决定创建的二叉树的形态。

    输入

    输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串(用于创建对应的二叉树)。

    输出

    每个用例用一行出该用例对应的二叉树的层次遍历序列。

    样例输入

    A##
    ABC####
    AB##C##
    ABCD###EF##G##H##
    A##B##
    

    样例输出

    A
    ABC
    ABC
    ABHCEDFG
    A

    用数组的下标为1的位置存储二叉树的根节点,其左孩子位于下标2*i的位置上,右孩子位于下标2*i+1的位置上。这棵二叉树在数组中的存储完全就是按照层序遍历的顺序存储的。

    #include<bits/stdc++.h>
    #define ll long long
    //#define int ll
    #define pii pair<int,int>
    #define mem(a,b) memset(a,b,sizeof(a))
    #define endl '\n'
    #define N 100005
    const int inf=0x3f3f3f3f;
    const double pi=acos(-1.0);
    using namespace std;
    char a[N];
    int n=0;
    void creat(int i)
    {
    	char c;
        cin>>c;
    	n++;
    	if(c!='#')
    	{
    		a[i]=c;
    		creat(2*i);
    		creat(2*i+1);
    	}
    }
    signed main()
    {	
    	creat(1);
    	for(int i=0;i<n;i++)
    		if(isupper(a[i])) cout<<a[i]; 
    	return 0;
    }
    
    

    更多相关内容
  • 在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构 总结先根遍历得到的非递归算法思想如下: 1)入栈,主要是先头结点入栈,然后visit此结点 2)...
  • // // 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

    展开全文
  • 先序遍历为:ABDGECF 中序遍历为:DGBEAFC 创建结构体 定义二叉树中每个结点的数据,以及左右孩子。 typedef struct BiNode { char data; //结点数据 struct BiNode *lchild, *rchild; //左右子树指针 } BiNode...

    创建如图所示的二叉树。
    先序遍历为:ABDGECF
    中序遍历为:DGBEAFC

    创建结构体

    定义二叉树中每个结点的数据,以及左右孩子。

    typedef struct BiNode {
        char data;                      //结点数据
        struct BiNode *lchild, *rchild; //左右子树指针
    } BiNode, *BiTree;
    

    先序遍历

    按照根->左->右的顺序递归遍历二叉树,并打印输出。

    //先序遍历
    void PreOrder(BiTree T) {
        if (T != NULL) {
            cout << T->data << '\t'; //首先访问根结点
            PreOrder(T->lchild);     //再访问左子树
            PreOrder(T->rchild);     //再访问右子树
        }
    }
    

    中序遍历

    按照左->根->右的顺序递归遍历二叉树,并打印输出。

    //中序遍历  左   根   右
    void InOrder(BiTree T) {
        if (T != NULL) {
            InOrder(T->lchild);      //先访问左子树
            cout << T->data << '\t'; //再访问根结点
            InOrder(T->rchild);      //再访问右子树
        }
    }
    

    先序遍历+中序遍历创建二叉树

    传入参数:

    • 当前结点的引用(表示需要将对指针修改带回)
    • 先序遍历的数组
    • 中序遍历的数组
    • 数组长度
    void BuildTree(BiTree &T, char *pre, char *in, int n) {
        // T:二叉树的指针 pre:先序遍历 in:中序遍历 n:二叉树的结点个数
        if (n == 0) {
            return;
        }
        //根结点
        char root = pre[0];
        //创建结点,让当前指针指向该结点
        T = new BiNode();
        T->data = root;
        //左子树个数
        int left = 0;
        for (int i = 0; i < n; i++) {
            if (in[i] != root) {
                left++;
            } else {
                break;
            }
        }
        //右子树个数
        int right = n - left - 1;
        //递归创建左子树
        BuildTree(T->lchild, pre + 1, in, left);
        //递归创建右子树
        BuildTree(T->rchild, pre + left + 1, in + left + 1, right);
    }
    

    结果预览:

    完整代码

    #include <iostream>
    using namespace std;
    
    //定义树的结构
    typedef struct BiNode {
        char data;                      //结点数据
        struct BiNode *lchild, *rchild; //左右子树指针
    } BiNode, *BiTree;
    
    //先序遍历  根  左  右
    void PreOrder(BiTree T) {
        if (T != NULL) {
            cout << T->data << '\t'; //首先访问根结点
            PreOrder(T->lchild);     //再访问左子树
            PreOrder(T->rchild);     //再访问右子树
        }
    }
    
    //中序遍历  左   根   右
    void InOrder(BiTree T) {
        if (T != NULL) {
            InOrder(T->lchild);      //先访问左子树
            cout << T->data << '\t'; //再访问根结点
            InOrder(T->rchild);      //再访问右子树
        }
    }
    
    //先序遍历+中序遍历创建二叉树
    void BuildTree(BiTree &T, char *pre, char *in, int n) {
        // T:二叉树的指针 pre:先序遍历 in:中序遍历 n:二叉树的结点个数
        if (n == 0) {
            return;
        }
        //根结点
        char root = pre[0];
        //创建结点,让当前指针指向该结点
        T = new BiNode();
        T->data = root;
        //左子树个数
        int left = 0;
        for (int i = 0; i < n; i++) {
            if (in[i] != root) {
                left++;
            } else {
                break;
            }
        }
        //右子树个数
        int right = n - left - 1;
        //递归创建左子树
        BuildTree(T->lchild, pre + 1, in, left);
        //递归创建右子树
        BuildTree(T->rchild, pre + left + 1, in + left + 1, right);
    }
    
    //由前序遍历和中序遍历创建二叉树
    int main(int argc, char const *argv[]) {
        BiTree T;
        char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};
        char in[] = {'D', 'B', 'E', 'A', 'C', 'F'};
        BuildTree(T, pre, in, 6);
        cout << "先序遍历:" << endl;
        PreOrder(T);
        cout << endl;
        cout << "中序遍历:" << endl;
        InOrder(T);
        return 0;
    }
    
    
    展开全文
  • 题目: 代码: #include<iostream> using namespace std; typedef struct BinaryTree { char data; struct BinaryTree* left; struct BinaryTree* right; }BT; void BinaryTreeCreate(BT*&... el.

    题目:

     

    代码:

    #include<iostream>
    using namespace std;
    typedef struct BinaryTree
    {
    	char data;
    	struct BinaryTree* left;
    	struct BinaryTree* right;
    }BT;
    void BinaryTreeCreate(BT*& ps)
    {
    	char a;
    	cin >> a;
    	if (a == '#')
    		ps = NULL;
    	else
    	{
    		ps = (BT*)malloc(sizeof(BT));
    		ps->data = a;
    		BinaryTreeCreate(ps->left);
    		BinaryTreeCreate(ps->right);
    	}
    }
    int BinaryTreeDepth(BT* ps)
    {
    	if (ps == NULL)
    		return 0;
    	else
    	{
    		int leftDepth = BinaryTreeDepth(ps->left);//左子树的深度
    		int rightDepth = BinaryTreeDepth(ps->right);//右子树的深度
    		return leftDepth>rightDepth ? leftDepth + 1 : rightDepth + 1;
    		//运用三目运算符,如果左子树深度更大则最大深度为左子树+1,否则相反
    	}
    }
    int main()
    {
    	BT* tree;
    	BinaryTreeCreate(tree);
    	printf("%d", BinaryTreeDepth(tree));
    	return 0;
    }

    展开全文
  • 先序遍历创建二叉树并遍历输出

    千次阅读 2019-07-07 11:13:24
    //先序遍历创建二叉树 void create(Node &bt) { BTelemtype ch; scanf(" %c", &ch); if (ch ==’#’)//‘#’代表为空 { bt = NULL; } else { bt = (Node)malloc(sizeof(BT));//申请结点空间 if (!bt) {...
  • 中序和先序遍历恢复二叉树python(年度更新系列) 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7] 这种问题的思路直接分三步走: 1.通过先序遍历找出根节点: rival = ...
  • 关于createTree(BiTNode* &T)的解释: 如果不加引用的话,我们只能改变T指针所指数据的内容, 给指针加引用,相当于指针的指针,这样就可以在函数之中改变指针的指向(即指针本身)。
  • 利用先序递归遍历算法创建二叉树并判断该二叉树是否为完全二叉树。完全二叉树只能是同深度的满二叉树缺少最后一层倒数连续个叶子结点。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象...
  • 388,先序遍历构造二叉树

    千次阅读 2020-09-23 23:53:25
    返回与给定先序遍历相匹配的二叉搜索树的根结点。 示例: 输入:[8,5,1,7,10,12] 输出:[8,5,10,1,7,null,12] 问题分析 我们知道先序遍历的顺序是:根节点→左子树→右子树。二叉搜索树的特点是当前...
  • 分析二叉树遍历的性质 有上述性质,可以分享
  • 【24行】之前看到众多巨佬数组写二叉树,...//在数组下标为1的位置上创建二叉树的根节点 for(int i=0;i;i++)//遍历存储二叉树的这个数组,如果a[i]存储了二叉树的结点,那么直接输出a[i] { if(a[i]>='A'&&a[i]) cout
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的中序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的中序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 987: 输出用先序遍历创建的二叉树是否为完全二叉树的判定结果 题目描述 利用先序递归遍历算法创建二叉树并判断该二叉树是否为完全二叉树。完全二叉树只能是同深度的满二叉树缺少最后一层倒数连续个叶子结点。先序...
  • 利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 利用先序遍历输入法建立二叉树

    千次阅读 2022-02-10 13:38:56
    .利用先序遍历输入法建立二叉树
  • 利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的...
  • 关于二叉树的概念:百度百科给的定义是:二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有...
  • 根据C语言数据结构第六版课本算法5.3 ...{ //算法5.3 按先序遍历输入二叉树中的节点的值 //构造二叉链表表示的二叉树T TElemType ch; scanf("%c",&ch); if(ch=="#") T==NULL;//空树 else { T=(BiTree)m
  • 利用先序递归遍历算法创建二叉树并计算该二叉树的深度。 先序递归遍历建立二叉树的方法为: 按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据 决定是否产生该结点从而实现创建该二叉树的二叉...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的...
  • 利用先序递归遍历算法创建二叉树并计算该二叉树的宽度。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表...
  • 以扩展的先序遍历建立二叉树,根结点的地址通过函数值返回。例如输入AB#DF##G##C##,建立二叉树如下图,二叉树.png输出该二叉树先序遍历序列ABDFGC。#include <stdio.h> #include <stdlib.h> typedef ...
  • 关于非递归方法对二叉树进行操作的原理已经有很多介绍,不再赘述,只...非递归先序遍历二叉树使用栈模拟递归。 #include<stdio.h> #include<stdlib.h> typedef char TreeData typedef struct BTreeN
  • 由于完全二叉树的定义,所以我们只要遍历每层的每个节点判断除了倒数一二层的节点外是否还有缺少左右节点的子节点,若有则不是完全二叉树。 附代码: #include <iostream> #include <queue> #include...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,408
精华内容 7,763
关键字:

用先序遍历创建二叉树