精华内容
下载资源
问答
  • c++先序遍历创建二叉树
    2020-03-11 10:59:58
    #include<bits/stdc++.h>
    
    using namespace std;
    
    struct TreeNode{
        struct TreeNode * lchild, *rchild;
        int val;
        TreeNode(int x): val(x), lchild(NULL), rchild(NULL){}
    };
    
    void create(TreeNode* &root){
        char x;
        cin >> x;
        if(x == '#')
            root = NULL;
        else{
            root = new TreeNode(x - '0');
            create(root->lchild);
            create(root->rchild);
        }
    }
    
    void pre(TreeNode* root){
        if(root){
            cout << root->val << " ";
            pre(root->lchild);
            pre(root->rchild);
        }
    }
    
    int main(){
        TreeNode * root;
        create(root);
        cout << "create finish!" << endl;
        pre(root);
        return 0;
    }
    
    更多相关内容
  • C++先序遍历的顺序建立二叉链表,
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • 创建如图所示的二叉树。 先序遍历为:ABDGECF 中序遍历为:DGBEAFC 创建结构体 定义二叉树中每个结点的数据,以及左右孩子。 typedef struct BiNode { ...右的顺序递归遍历二叉树,并打印输出。 //先序遍历 void Pre

    创建如图所示的二叉树。
    先序遍历为: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;
    }
    
    
    展开全文
  • 先序遍历还原二叉树 二、解题报告 1、思路分析    ( 1 ) (1) (1) 利用一个栈,存储深度优先搜索时的访问序列;    ( 2 ) (2) (2) 根据深度来控制栈中元素的个数;    ( 3 ) (3) (3) 迭代计算每个结点的左右...

    一、题目

    1、题目描述

      我们从二叉树的根节点 root开始进行深度优先搜索。在遍历中的每个节点处,我们输出 D条短划线(其中 D是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,则其直接子节点的深度为 D + 1。根节点的深度为 0)。
      如果节点只有一个子节点,那么保证该子节点为左子节点。
      给出遍历输出 S,还原树并返回其根节点 root
      样例输入: "1-401--349---90--88"
      样例输出: [1,401,null,349,88,90]

    2、基础框架

    • C++ 版本给出的基础框架代码如下:
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
    public:
        TreeNode* recoverFromPreorder(string traversal) {
    
        }
    };
    

    3、原题链接

    LeetCode 1028. 从先序遍历还原二叉树

    二、解题报告

    1、思路分析

       ( 1 ) (1) (1) 利用一个栈,存储深度优先搜索时的访问序列;
       ( 2 ) (2) (2) 根据深度来控制栈中元素的个数;
       ( 3 ) (3) (3) 迭代计算每个结点的左右子树;

    2、时间复杂度

       最坏时间复杂度 O ( n ) O(n) O(n)

    3、代码详解

    class Solution {
    public:
        TreeNode* recoverFromPreorder(string traversal) {
            stack<TreeNode*> stk;
            TreeNode *root, *now;
    
            int rootval = 0, sum = 0;
            int n = traversal.size();
    
            for(int i = 0; i < traversal.size(); ++i) {
                if(traversal[i] == '-') {
                    ++sum;                                  // (1)
                }else {
                    while(i != n && traversal[i] != '-') {  // (2)
                        rootval = rootval * 10 + traversal[i] - '0';
                        ++i;
                    }
                    --i;
                    // (sum, rootval)
                    {
                        while(stk.size() > sum) stk.pop();  // (3)
                        now = new TreeNode(rootval);        // (4)
                        if(stk.size() == 0) {
                            root = now;                     // (5)
                        }else {
                            if( stk.top()->left ) {         // (6)
                                stk.top()->right = now;
                            }else {
                                stk.top()->left = now;
                            }
                        }
                        stk.push(now);                      // (7)
                    }
                    sum = 0;
                    rootval = 0;
                }
            }
            return root;
        }
    };
    

       ( 1 ) (1) (1) 统计当前结点有多少个'-',存储在sum中;
       ( 2 ) (2) (2) 计算当前结点实际的值;
       ( 3 ) (3) (3) 根据当前实际需要的深度,将栈中多余结点剔除;
       ( 4 ) (4) (4) 任意一个新出现的结点,都应该需要被新创建的;
       ( 5 ) (5) (5) 如果栈为空,说明当前结点是一个根结点;
       ( 6 ) (6) (6) 栈顶元素为当前结点的父结点,判断是否存在左子树,如果有左子树,则当前结点为右子树根结点;否则,为左子树根结点;
       ( 7 ) (7) (7) 将当前结点入栈;


    三、本题小知识

      栈可以将递归问题转换成迭代求解;


    四、加群须知

      相信看我文章的大多数都是「 大学生 」,能上大学的都是「 精英 」,那么我们自然要「 精益求精 」,如果你还是「 大一 」,那么太好了,你拥有大把时间,当然你可以选择「 刷剧 」,然而,「 学好算法 」,三年后的你自然「 不能同日而语 」
      那么这里,我整理了「 几十个基础算法 」 的分类,点击开启:

    🌌《算法入门指引》🌌

      如果链接被屏蔽,或者有权限问题,可以私聊作者解决。

      大致题集一览:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述



    在这里插入图片描述


      为了让这件事情变得有趣,以及「 照顾初学者 」,目前题目只开放最简单的算法 「 枚举系列 」 (包括:线性枚举、双指针、前缀和、二分枚举、三分枚举),当有 一半成员刷完 「 枚举系列 」 的所有题以后,会开放下个章节,等这套题全部刷完,你还在群里,那么你就会成为「 夜深人静写算法 」专家团 的一员。
      不要小看这个专家团,三年之后,你将会是别人 望尘莫及 的存在。如果要加入,可以联系我,考虑到大家都是学生, 没有「 主要经济来源 」,在你成为神的路上,「 不会索取任何 」
      🔥联系作者,或者扫作者主页二维码加群,加入刷题行列吧🔥


    🔥让天下没有难学的算法🔥

    C语言免费动漫教程,和我一起打卡!
    🌞《光天化日学C语言》🌞

    让你养成九天持续刷题的习惯
    🔥《九日集训》🔥

    入门级C语言真题汇总
    🧡《C语言入门100例》🧡

    组团学习,抱团生长
    🌌《算法零基础100讲》🌌

    几张动图学会一种数据结构
    🌳《画解数据结构》🌳

    竞赛选手金典图文教程
    💜《夜深人静写算法》💜
    展开全文
  • 假设现在有某二叉树先序遍历和中序遍历,我们应该如何建树? 基本思路: 分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列 分别以左子树和右子树为新树进行第一步操作 直至没有子树为止 那么我们...

    在对二叉树进行操作之前,建树是必须要做的。假设现在有某二叉树的先序遍历和中序遍历,我们应该如何建树?

    基本思路:

    1. 分别求得根节点的左子树和右子树的先序遍历序列与中序遍历序列
    2. 分别以左子树和右子树为新树进行第一步操作
    3. 直至没有子树为止

    那么我们这么实现呢?

    根据我们对二叉树遍历的学习,可以知道:

    • 先序遍历序列中的第一个节点为根节点
    • 一个节点的左右子节点分别位于中序遍历序列中该节点的两侧

    举个例子:
    举例

    对于图中二叉树,其先序遍历序列与中序遍历序列如右侧所示,每个序列共6个字母(此二叉树共有6个节点)。

    1. 对于整棵树的先序遍历中第一个节点“A”(根节点),其在中序遍历序列中第4个位置,这就说明A的左子树应有3个节点,右子树应有2个节点。
    2. 对于左子树的先序遍历中第一个节点“B”,其在中序遍历中第2个位置,说明其左子树有1个节点,右子树有1个节点(“左子树”共3个节点)
    3. 对于右子树的第一个节点“C”,其在中序遍历中第2个位置,说明其左子树有一个节点,右子树有0个节点(“右子树”共2个节点)
    4. 递归进行,直至当前处理的“树”没有其他子树(即此节点为叶子节点)为止

    接下来,我们来做最重要的一步:

    讲上述逻辑转化为计算机语言

    (以C++语言,用二叉链表存树为例)

    现有两个序列:

    • 先序遍历序列:preorderList
    • 中序遍历序列:inorderList

    用于标记序列长度的四个变量:

    • 先序遍历序列的第一个字母的位置:preBegin
    • 先序遍历序列的最后一个字母的位置:preEnd
    • 中序遍历序列的第一个字母的位置:inBegin
    • 中序遍历序列的最后一个字母的位置:inEnd

    设当前处理的节点在中序遍历中的位置为index
    则其左子树节点个数为index-inBegin
    所以可以得到:

    • 左子树先序遍历序列区间为[preBegin+1, preBegin+index-inBegin],中序遍历序列区间为[inBegin, index -1]
    • 右子树先序遍历序列区间为[preBegin+index-inBegin+1, preEnd],中序遍历序列区间为[index+1, inEnd]

    结束条件:“当前节点为叶子节点”
    如果当前节点为叶子节点,即preBegin == preEnd时需要返回一个“node”;preBegin > preEnd时返回NULL,同样可以说明已经到了叶子节点,这里我们选择后者(叶子节点的类型依然为node,需要将其对子节点的指针设为NULL)。


    节点类型:

    struct node{
    	char data;
    	node *lchild;
    	node *rchild;
    };
    

    核心:buildTree函数

    node *buildTree(int preBegin, int preEnd, int inBegin, int inEnd, string preorderList, string inorderList){
    	if (preBegin > preEnd){
    		return NULL;
    	}
    	
    	node *Node = new node;
    	int index = 0;
    	
    	Node -> data = preorderList[preBegin];
    	/*通过遍历中序遍历序列的方式寻得index*/
    	for (int i = inBegin; i < inEnd+1; i++){
    		if (preorderList[preBegin] == inorderList[i]){
    			index = i;
    			break;
    		}
    	}
    	
    	/*分别对左右子树进行递归操作*/
    	Node -> lchild = buildTree(preBegin+1, preBegin+index-inBegin, inBegin, index-1, preorderList, inorderList);
    	Node -> rchild = buildTree(preBegin+index-inBegin+1, preEnd, index+1, inEnd, preorderList, inorderList);
    
    	return Node;
    }
    

    附完整代码:

    #include <iostream>
    #include <string>
    using namespace std;
    
    struct node{
    	char data;
    	node *lchild;
    	node *rchild;
    };
    
    node *buildTree(int preBegin, int preEnd, int inBegin, int inEnd, string preorderList, string inorderList){
    	if (preBegin > preEnd){
    		return NULL;
    	}
    	
    	node *Node = new node;
    	int index = 0;
    	
    	Node -> data = preorderList[preBegin];
    	for (int i = inBegin; i < inEnd+1; i++){
    		if (preorderList[preBegin] == inorderList[i]){
    			index = i;
    			break;
    		}
    	}
    	
    	Node -> lchild = buildTree(preBegin+1, preBegin+index-inBegin, inBegin, index-1, preorderList, inorderList);
    	Node -> rchild = buildTree(preBegin+index-inBegin+1, preEnd, index+1, inEnd, preorderList, inorderList);
    
    	return Node;
    }
    
    int main (){
    	string preorderList;
    	string inorderList;
    	int preBegin, preEnd, inBegin, inEnd;
    	node *root = new node;	
    	
    	cin >> preorderList;
    	cin >> inorderList;
    	
    	preBegin = 0;
    	inBegin = 0;
    	preEnd = preorderList.length() - 1;
    	inEnd = inorderList.length() - 1;
    	
    	root = buildTree(preBegin, preEnd, inBegin, inEnd, preorderList, inorderList);
    	
    	return 0;
    }
    
    展开全文
  • 以扩展的先序遍历建立二叉树,根结点的地址通过函数值返回。例如输入AB#DF##G##C##,建立二叉树如下图,二叉树.png输出该二叉树先序遍历序列ABDFGC。#include <stdio.h> #include <stdlib.h> typedef ...
  • 输入数组,数组中为树先序遍历结果,空节点值为-1 Node* createTree(vector<int> nums, int &pos) { int n = nums.size(); if (pos >= n || nums[pos] == -1) return NULL; Node *root = (Node *)...
  • 这是建立的树 #include <stdio.h> #include <iostream> #include <stack> #include <queue> #include <malloc.h> using namespace std; #define MAXSIZE 100 typedef struct ...
  • 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
  • 二叉树中已知中序遍历和前序遍历(后序遍历),求后序遍历(前序遍历)(C++
  • 本文实例讲述了C++基于先序、中序遍历结果重建二叉树的方法。分享给大家供大家参考,具体如下: 题目: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含...
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • 前几天写了1020 Tree Traversals (25 分)-PAT甲级这个题目,明白了如何由二叉树的后序遍历和中序遍历得到先序遍历和层次遍历。受这道题启发,思考了一下如何由二叉树先序遍历和中序遍历得到后序遍历和层次遍历。...
  • 关于createTree(BiTNode* &T)的解释: 如果不加引用的话,我们只能改变T指针所指数据的内容, 给指针加引用,相当于指针的指针,这样就可以在函数之中改变指针的指向(即指针本身)。
  • 先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当...
  • //【BiTNode 二叉树结点】【BiTree 二叉树】 BiTree CreatBiTree(string preStr, string inStr) { //根据先序遍历序列和中序遍历序列构造二叉树 BiTree temp = new BiTNode; temp->data = *(preStr.cbegin()); ...
  • 这里其实有一个规律,如果根节点是a[1]的话,那么其左右孩子分别是a[2],a[3],由先序的递归创建可知,当总根节点创建完毕后,就让其左孩子a[2]为根节点,那么他的左右孩子分别是a[4],a[5];按照这样的规律往下走,你...
  • <code>void createBiTree(BiTree &...//递归先序遍历二叉树 cout << endl; return 0; }</code></pre> 为什么我输入‘#’会进入死循环,一直输出"Enter the number " 呢。</p>
  • 利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的双亲结点。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点。最后再输出创建完成的二叉树中的...
  • 水了三题一摸一样的题目,好快乐 题目描述 利用先序递归遍历算法创建二叉树并输出该二叉树中指定结点的度。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符“#”时表示该结点不需要创建,否则创建该结点...
  • C++实现非递归二叉树先序遍历

    千次阅读 2020-04-24 12:27:54
    该方法是通过“栈”实现非递归二叉树遍历的算法。 初学数据结构本人感受就是,对于栈的创建和树的创建(类)相当于一个模板,以后如果用到的话,基本...以下是非递归二叉树先序遍历的代码: #include <iostr...
  • 如何用代码实现先序遍历二叉树(C语言或C++) 想必有很多小伙伴和我一样,最开始的时候在网上或者是书上看了一系列有关于二叉树的遍历原理以及递归、非递归的实现方法,但是奈何书中也只是给出了伪代码之类的,并...
  • 先序顺序和中序顺序输入二叉树的2个遍历序列,采用二叉链表建立二叉树并用后序遍历顺序输出该二叉树的后序遍历序列。 Input 输入数据有多组,对于每组测试数据 第一行输入二叉树先序序列,第二行为中序序列...
  • 参考:二叉树先序遍历 先序遍历,简而言之就是:根、左、右。 按照先序遍历的访问顺序,肯定会把最左边那条路全部遍历完——终止条件是访问到了最左下角的空节点,再往回走。 //T是指向二叉树顶端节点的...
  • 定义树的结构 //定义树的结构 typedef struct BiNode { char data; //结点数据 ...先序遍历创建二叉树 void InCreateTree(BiTree &T) { char ch; cin >> ch; //判断是否为# if (ch !=.
  • 1.二叉树的常用性质 &lt;1&gt;.在二叉树的第i层上最多有2 i-1 个节点 。(i&gt;=1) &lt;2&gt;.二叉树中如果深度为k(有k层),那么最多有2k-1个节点。(k&gt;=1) &lt;3&gt;.若...
  • 先序遍历、中序遍历、后序遍历(递归),层次遍历 代码: #include <iostream> using namespace std; #define MAXSIZE 10 //二叉树节点 typedef struct biNode{ char data; biNode* lchild; biNode* ...
  • 二叉树先序遍历

    2012-11-07 14:51:38
    c语言中关于二叉树先序遍历,链表的创建
  • 学过数据结构的应该都知道,根据先序遍历和中序遍历可以唯一确定一颗二叉树二叉树是递归定义的数据结构,所以一般的操作都是递归完成的,所以建树的过程也不例外,先来看这样两道题 题目一 :...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,304
精华内容 3,721
关键字:

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

c++ 订阅
友情链接: ImageRead.rar