精华内容
下载资源
问答
  • 建立二叉树
    千次阅读
    2020-05-13 21:35:24

    NOJ-建立二叉树的二叉链表

    实则为二叉树的重建

    在这里插入图片描述

    题目分析

    输入:一颗二叉树的前序序列和中序序列
    输出:一颗二叉树的后序序列。

    解题思路

    典型的二叉树的重建,如何去重建呢?
    二叉树的遍历特点

    1. 前序遍历,即是
      1. 访问根结点
      2. 先序遍历左子树
      3. 先序遍历右子树
    2. 中序遍历
      1. 中序遍历左子树
      2. 访问根结点
      3. 中序遍历右子树

    所以,我们很容易发现
    在前序序列中找到的第一个结点就是整棵树的根结点,
    而我们要在中序序列找到这个结点就必须遍历完整个左子树。
    即:前序序列中找到的根结点,在去中序序列中找到这个结点时
    中序序列中出现该元素的位置的左侧,是它的左子树,右侧是它的右子树
    从这一基本特点,我们就可以通过递归,从根结点开始,逐次深入,直到叶子结点。

    算法执行步骤

    1. 创建根结点及其初始化。
    2. 判断是否遍历完成,如果完成就返回这个根结点。
    3. 设置temp指针记录当前中序序列的首元素的位置。
    4. 在中序序列中查找根结点的值所在的位置,并更新I_start的值。
    5. 用left来记录第4步中,右移的元素个数,即根结点的左子树元素个数。
    6. 递归重建左右子树。
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef struct BiTNode{
        char data;
        struct BiTNode *lchild, *rchild;//左右孩子指针
    } BiTNode, *BiTree;
    void PosOrderTraverse(BiTree T);//后序遍历
    BiTree Rebuild(char *P_start, char *P_last, char *I_start, char *I_last);//二叉树的重建
    BiTree Build(char *Ptree, char *Itree,int len);//
    int main()
    {
        char Ptree[100];
        char Itree[100];
        int len = 0;
        scanf("%s", Ptree);
        scanf("%s", Itree);
        len = strlen(Ptree);
        BiTree T;
        T = Build(Ptree, Itree, len);
        PosOrderTraverse(T);
    }
    void PosOrderTraverse(BiTree T)
    {
        if(T->lchild){
            PosOrderTraverse(T->lchild);
        }
        if(T->rchild){
            PosOrderTraverse(T->rchild);
        }
        if(T){
            printf("%c", T->data);
        }
    }
    BiTree Rebuild(char *P_start, char *P_last, char *I_start, char *I_last)//P代表先序序列,I代表中序序列
    {
        BiTree root;
        root = (BiTree)malloc(sizeof(BiTNode));//创建一个根节点
        root->data = P_start[0];//根节点的值设为前序序列的第一个元素
        root->lchild = NULL;
        root->rchild = NULL;//清空左右子树
        if(P_start==P_last){
            if(I_start==I_last&&*P_start==*P_last)
            {
                return root;//当前序和中序所有元素都被遍历,就返回根节点的值
            }
        }
        char *temp = I_start;//设置一个字符指针去存储当前的中序序列的开始指针
        int left = 0;//前序序列中的元素在中序序列中左边的元素个数
        while((*I_start!=root->data)&&(I_start<I_last))
        {
            I_start++;//在中序序列查找到根结点所在位置
        }
        left = I_start - temp;//左边的元素个数即是目前中序序列start指针减去之前temp所存储的start指针的值
        if(left>0){
            root->lchild = Rebuild(P_start + 1, P_start + left, temp, I_start - 1);//递归建立左子树
        }
        //left>0表明左边还有元素说明此根节点可以建立左子树
        //此时前序序列P应该向后移动一个位置,并且结束位置在P_start+left这是因为左子树一共有left个元素
        //此时中序序列I应从原来的temp遍历到I_start-1,这一段也对应左子树的相应元素。
        if(left<(P_last-P_start)){
            root->rchild = Rebuild(P_start + left + 1, P_last, I_start + 1, I_last);
        }
        //右子树的思路同上
        return root;
    }
    BiTree Build(char *Ptree, char *Itree,int len)
    {
        return Rebuild(Ptree, Ptree + len - 1, Itree, Itree + len - 1);
    }
    

    题外话:最近学习好忙呀,各种考试,图论已经讲了一半了,我还没写图的NOJ,不过得缓一缓,先复习其他科目吧。

    更多相关内容
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • 采用二叉链表存储先序建立二叉树,非递归中序遍历二叉树算法实现
  • 建立二叉树

    2014-07-17 12:12:49
    已知二叉树先序和中序遍历,要求二叉树的顺序,本方法使用c语言编写
  • 大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入
  • (1)输入字符序列,建立二叉链表。 (2)先序、中序、后序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归算法(最好也能实现先序,后序非递归算法)。 (4)求二叉树的高度 。 (5)求二叉树的叶子个数。 ...
  • 建立二叉树的几种方法: 一、已知先序遍历顺序,构建二叉树。(链式存储) 二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立...

    其他二叉树知识!二叉树知识汇总


    目录

    前提知识:

    约定:

    二叉树节点的存储结构:

    创建一个节点:

    建立二叉树的几种方法:

    一、已知先序遍历顺序,构建二叉树。(链式存储)

    二、已知层次遍历顺序,构建二叉树。(链式存储)

    三、已知节点关系,建立二叉树(邻接表存储)

    四、已知先序和中序遍历顺序,建立二叉树。

     


    前提知识:

     

    约定:

    约定二叉树的内容为int类型,并且都>=1,0代表是空节点。我们一般画的二叉树为图一,但是计算机中存储时真实的样子是图二,即需要考虑空节点,不然的话,计算机不知道这个节点已经到头了。

              

    例子中树的先序遍历为:1 2 4 3 5 6

    若是考虑每个节点的两个空节点,则先序遍历为:1 2 4 0 0 0 3 5 0 0 6 0 0

    二叉树节点的存储结构:

    struct Node{
    	int data;
    	Node* leftchild;
    	Node* rightchild; 
    };

    一个存储数据的data,左右两个指针都是节点的指针类型。

    创建一个节点:

    void Create_Node(Node* &t,int x){  //在指针t处生成一个新的节点,内容为x
    	t=new Node;
    	t->data=x;
    	t->leftchild=NULL;
    	t->rightchild=NULL;
    }

    开辟一个新的Node类型空间,并将地址赋值给指针t。(原来t指向NULL,现在指向了我们生成的新节点,这就是创建节点的过程)

    另外新节点*t的左右孩子要指向NULL,这代表节点到此结束,不赋初值会导致一些错误。

    参数的问题:

    Node * &t 这个参数表示传入的是一个Node类型的指针变量,并且是引用传递,因为我们要修改实参的值,所以要用引用传递。

    不懂引用的看这里:https://blog.csdn.net/qq_21989927/article/details/107447970

     

    建立二叉树的几种方法:

     

    一、已知先序遍历顺序,构建二叉树。(链式存储)

    这里的先序遍历顺序,必须是包含空节点的,不然是无法确定二叉树的。

    样图中的数的先序遍历顺序:1 2 4 0 0 0 3 5 0 0 6 0 0

    void Create_Pre(Node* &t){
    	int x; 
    	cin>>x;
    	if (x==0) return;
    	else{
    		Create_Node(t,x);
    		Create_Pre(t->leftchild);
    		Create_Pre(t->rightchild);
    	} 
    }
    

    对于输入的x,若是0,说明是空节点,直接返回return。

    若不是空节点,则调用前提知识中的Create_Node函数,在此处创建一个新节点,接着再递归新节点的左右孩子。

    因为已知的是先序遍历顺序,所以我们是按先访问根,再访问左右孩子的顺序。

     

    二、已知层次遍历顺序,构建二叉树。(链式存储)

    这里又分两种方法:一种是边读入数据边建立二叉树,需要用到队列;另一种是已知的层次遍历顺序在数组中存放好了。

    1.使用队列

    这种方法样例对应的读入是:1 2 3 4 0 5 6 0 0 0 0 0 0  (0是空节点)

    void Create_Level(Node* &t){
    	queue<Node*> q;
    	int x;
    	cin>>x;
    	if (x!=0) {
    		Create_Node(t,x);
    		q.push(t);
    	}
    	while (!q.empty()){
    		Node* s=q.front();
    		cin>>x;
    		if (x!=0){
    			Create_Node(s->leftchild,x);
    			q.push(s->leftchild);
    		}
    		cin>>x;
    		if (x!=0){
    			Create_Node(s->rightchild,x);
    			q.push(s->rightchild);
    		}
    		q.pop();
    	}
    }

    使用队列的方法,首先要入读一个x,判断这棵树是否存在,若是0,说明空树,不为0,创建节点后入队。

    当队列不为空时,队列中每一个元素都需要再读取两个数字(就算是叶子节点也起码也得读两个0)。

    这种方法建立二叉树,执行过程中会发现,每次读取的两个数,对应的都是队首元素的左右孩子,这和给定的层次遍历顺序对应。

    2.使用数组

    给定的层次遍历已经存放在数组中,我们只需要判断一个节点的左右孩子是否存在即可,左孩子为i*2,右孩子为i*2+1。

    注意要从a[1]开始存储,a[0]不用。

    int a[100]={0,1,2,3,4,0,5,6};
    void Create_Tree(Node* &t,int i){
    	if (a[i]==0) return;
    	Create_Node(t,a[i]);
    	if (a[i*2]!=0) Create_Tree(t->leftchild,i*2);
    	if (a[i*2+1]!=0) Create_Tree(t->rightchild,i*2+1);
    }
    

    3.两种方法的区别:

    建造过程的不同:

    利用队列,树是一层一层被构造出来的,对数据的访问也是严格按照层次遍历的顺序执行的;

    利用数组,树的构造过程实际上是先根,再左孩子,再右孩子的。通过跳跃访问数组内容,实现的是先序遍历建立二叉树。

    输入数据的不同:

    如果一棵树如图:

    对于队列的方法,   输入为 1 0 3 5 6 0 0 0 0

    对于数组的方法,数组中:1 0 3 0 0 5 6 0 0 0 0 

    因为对于队列来,如果一个节点为空节点,那么自然不会加入队列,也不会再去访问他。

    而对于数组来说,要严格执行左孩子是*2,右孩子是*2+1的规则,所以空间浪费会很多。

     

    三、已知节点关系,建立二叉树(邻接表存储)

    假设题目输入中,我们只知道 x , y 之间有一条边,但是并不知道 x , y 的父子关系的时候,可以使用邻接表的方法存储树。
    这时候把树看做一个图,建边要建双向边,然后在从根做dfs,确定每个节点的深度,顺便也可以求出每个节点的父亲节点,这样节点之间的父子关系就清楚了。

    例题:
    第一行输入N、root,表示这棵树有N个节点,根为root。
    接下来 N-1 行每行包含两个正整数 x, y,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以构成树)。

    求每个节点的深度和每个节点的父亲节点。

    代码:

    #include<iostream>
    using namespace std;
    
    const int MaxN=500050;
    struct Edge{
    	int v;
    	int next;
    };
    Edge e[MaxN];
    int last[MaxN];
    int n,m,root,tot;
    int deep[MaxN];
    int f[MaxN];  
    
    void build(int x,int y){
    	tot++;
    	e[tot].v=y;
    	e[tot].next=last[x];
    	last[x]=tot;
    }
    
    //编号为x的节点,父亲是fa 
    void dfs(int x,int fa){
    	f[x]=fa;
    	deep[x]=deep[fa]+1;
    	for (int j=last[x]; j!=0; j=e[j].next){
    		int y=e[j].v;
    		if (y!=fa) dfs(y,x);		
    	}
    }
    
    
    int main(){
    	cin>>n>>root;
    	for (int i=1; i<=n-1; i++){
    		int x,y;
    		cin>>x>>y;
    		build(x,y);
    		build(y,x);
    	}
    	dfs(root,0);
    	for (int i=1; i<=n; i++) cout<<deep[i]<<" "; cout<<endl;
    	for (int i=1; i<=n; i++) cout<<f[i]<<" "; cout<<endl;	
    } 

    此种方法不仅适合二叉树,也适合多叉树。

    四、已知先序和中序遍历顺序,建立二叉树。

    LeetCode的题目:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    例如前序遍历 preorder = [3,9,20,15,7]
           中序遍历 inorder = [9,3,15,20,7]
    建立如下二叉树并返回根节点。
        3
       / \
      9  20
          /  \
       15   7

    思路就是递归分治。 对于一个先序遍历序列,第一个一定是根节点,如样例的3。我们只要在中序遍历序列中找到这个3,那么3之前的都是左子树,之后的都是右子树。再依次递归处理即可。
    因为题目说不含重复数字,所以在中序遍历中找根的这个工作可以借助哈希表。
    还要注意,因为我们递归的是中序遍历的序列,所以还要再加一个参数用来记录此序列的先序遍历第一个是谁,也就是根节点是谁。

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        unordered_map<int,int> h;
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int n=inorder.size();
            for (int i=0; i<n; i++) h[inorder[i]]=i; //哈希求位置
            TreeNode* head=build(preorder,inorder,0,n-1,0);//0~n-1 根是0
            return head;
        }
        TreeNode* build(vector<int>& preorder,vector<int>& inorder,int l,int r,int g){
            if (l>r) return NULL;
            TreeNode* t=new TreeNode(preorder[g]); //构造函数
            int j=h[preorder[g]]; //在inorder找pre[g]
            t->left=build(preorder,inorder,l,j-1,g+1);
            t->right=build(preorder,inorder,j+1,r,g+j-l+1);
            return t;
        }
    };

     

    展开全文
  • 根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
  • 主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
  • 【数据结构】建立二叉树、二叉树的推导技巧

    多人点赞 热门讨论 2022-05-04 11:49:40
    逆向思维指的是反向思考问题的能力。而我们的二叉树建立推导过程,就是运用了逆向思维。在得到的二叉树前序、中序、后序遍历的结果后,在根据2种不同的遍历结果,反向推导出二叉树集合。...

    💟作者简介:大家好呀!我是路遥叶子,大家可以叫我叶子哦!❣️    
    📝个人主页:【路遥叶子的博客】
    🏆博主信息:四季轮换叶,一路招摇胜!


            专栏

           【安利Java零基础】

           【数据结构-Java语言描述】

    🐋希望大家多多支持😘一起进步呀!~❤️
    🌈若有帮助,还请【关注点赞收藏】,不行的话我再努力努力呀!💪
    ————————————————
    ⚡版权声明:本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
    🍁想寻找共同成长的小伙伴,请点击【Java全栈开发社区】

    目录

    逆向思维

    🐋建立二叉树的方式

    🐋二叉树的推导

    🌲由先根和中根遍历序列建二叉树

    🌲由后根和中根遍历序列建二叉树

    🌲由标明空子树的先根遍历建立二叉树

    🌲由完全二叉树的顺序存储结构建立二叉链式存储结构

    🐋小试牛刀

    如果文章对您有帮助,就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧!


    前言

    现在我们已经了解到的二叉树的特性及遍历方式,那么你知道如何根据三种不同的遍历方式将二叉树推导进行出来吗?那你又需要用多长的时间呢?今天看完文章1分钟带来玩转二叉树,高效正确建立二叉树。

    逆向思维

    逆向思维指的是反向思考问题的能力。

    这种人思维活跃,想法别致,遇到问题能用常人想不到的方式解决。

    众所周知的“司马光砸缸。”有人落水,常规的思维模式是“救人离水”,而司马光面对紧急险情,运用了逆向思维,果断地用石头把缸砸破,“让水离人”,救了小伙伴性命。

    运用好逆向思维去思考和处理问题,实际上就是以“出奇”去达到“制胜”,让问题变得更简单。

     而我们的二叉树的建立,推导过程,就是运用了逆向思维。在得到的二叉树前序、中序、后序遍历的结果后,在根据2种不同的遍历结果,反向推导出二叉树集合。

    💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

    🐋建立二叉树的方式

    四种方式可以建立二叉树:

    1. 先根和中根遍历序列建二叉树

    2. 后根和中根遍历序列建二叉树

    3. 标明空子树的先根遍历建立二叉树

    4. 完全二叉树的顺序存储结构建立二叉链式存储结构

    🐋二叉树的推导

    🌲由先根和中根遍历序列建二叉树

    🎃1)先根和中根原理

    技巧总结:

    • 通过先序遍历获得根结点(第一个结点)。因为先序遍历总是先遍历第一个结点,也就是根结点。

    • 通过已知的根结点中序遍历可以分别确定左子树右子树的结点元素。因为中序遍历总是在遍历完左子树中所有结点后,放在中间遍历的,遍历完后又继续遍历右子树所有结点。

    🎃2)实例分析步骤:

    •  第一步:由先序遍历得知A结点为根结点,则可拆分中序遍历得A结点的左右子树结点元素

     第二步:根据先序遍历,首先遍历根结点,遍历完之后会去遍历左子树的第一个结点,也就是上图先序遍历A后面的B结点。由此在左子树元素DBGE中可以得出B结点为父结点。依次类推。

    • 先序遍历:根结点—左子树右子树【ABDEGCFH

    左子树:

    • 1)由前序BDEG,中序DBGE得知:B为父结点在中序遍历中位于B的左边元素D为B的左结点,右边元素GE为B的右结点。
    • 2)依次由1步骤进行判断。由前序BDEG,中序DBGE得知:D为下一个结点,且D没有左右结点;E为下一个结点,且E没有左子树,有一个右子树G

    右子树:

    • 1)由前序遍历顺序中CFH,得知C是父结点,FH为左孩子;F是父结点,H为右孩子。

     核心技巧:

    • 根据先序遍历根结点和父结点
    • 根据中序遍历确定左右子树的元素位置

    🎃3)算法实现

    /** 例如:new BiTree("ABDEGCFH","DBGEAFHC",0,0,8);
    * @param preOrder 先序遍历序列
    * @param inOrder  中序遍历序列
    * @param preIndex 在preOrder中开始位置
    * @param inIndex  在inOrder中开始位置
    * @param count 结点数
    */
    public BiTree(String preOrder,String inOrder,int preIndex,int inIndex,int count) {
        if(count > 0) {
            //1 通过先序获得根结点
            char r = preOrder.charAt(preIndex);
            //2 中序中,根结点的位置
            int i = 0 ;
            for(; i < count ; i ++) {
                if(r == inOrder.charAt(i + inIndex)) {
                    break;
                }
            }
            //3 通过中序,截取左子树和右子树
            root = new BiTreeNode(r);
            root.lchild = new BiTree(preOrder,inOrder,preIndex+1, inIndex, i).root;
            root.rchild = new BiTree(preOrder,inOrder,preIndex+1+i,inIndex + i + 1, count-i-1).root;
        }
    }

    💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

    🌲由后根和中根遍历序列建二叉树

    🎃 1)后根和中根原理

     技巧总结:

    • 通过后序遍历获得根结点(最后一个结点)

    • 通过根结点中序遍历确定左子树右子树

    • 与先序、中序遍历建立二叉树,异曲同工。不同的是:根据后序遍历获取根结点。由于后序遍历的顺序,每一个左右根组合,每次根都是最后遍历的,所以我们获取根结点,要从后序遍历的后面往前依次确定根结点。

    🎃2)实例分析步骤:

    已知二叉树,中根遍历序列为:9,3,15,20,7、后根遍历序列为:9,15,7,20,3 重建二叉树?

     💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

    🌲由标明空子树的先根遍历建立二叉树

    🎃 1)概述

    • 仅使用先根遍历序列无法唯一确定一颗二叉树,例如:“AB”,B可以是左孩子,也可以是右孩子。

    • 在先根遍历序列中加入==空树==信息,从而确定结点与双亲、孩子与兄弟间的关系,从而唯一确定一颗二叉树。

    • 表名空子树的先序遍历序列:二叉树中每一个结点都必须有孩子或#

      • 空树:以字符“#”表示

      • 根节点A:以字符串“A##”表示

    🎃 2)实例演示:

    前言:已知以下二叉树 :

    • 现我们知道字符串“AB#C##D##” ,根据字符串建立二叉树

    • 下图树,以字符串“ABDH#K###E##CFI###G#J##”表示

    🎃3)算法

    • 建立二叉链表算法分析:

      • 若读取的字符是“#”,则建立空树;否则

      1. 建立根节点

      2. 递归建立左子树的二叉链表

      3. 递归建立右子树的二叉

    算法

    • 采用先序,每一个结点都根左右

    private static int index = 0;			//用于记录preStr的索引值
    public BiTree(String preStr) {
        char c = preStr.charAt(index++);
        if(c != '#') {
            root = new BiTreeNode(c);					//根
            root.lchild = new BiTree(preStr).root;		//左
            root.rchild = new BiTree(preStr).root;		//右
        } else {
            root = null;
        }
    }

      💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚

    🌲由完全二叉树的顺序存储结构建立二叉链式存储结构

    🎃 1)由二叉树的特性5可知,结点编号规则:

    • 根节点的编号为0

    • 编号为i的结点

      • 左孩子的编号为2i+1

      • 右孩子的编号为2i+2

    • 完全二叉树及其顺序存储(层次遍历序列)

    🎃 2) 算法:

    public BiTreeNode createBiTree(String sqBiTree, int index) {
        BiTreeNode root = null;
        if(index < sqBiTree.length()) {
            root = new BiTreeNode(sqBiTree.charAt(index));
            root.lchild = createBiTree(sqBiTree, 2*index+1);
            root.rchild = createBiTree(sqBiTree, 2*index+2);
        }
        return root;
    }

    🐋小试牛刀

    练习1:

    已经二叉树,先序序列为abcdefg,中序序列为cbdaegf,重建二叉树?

    练习2:

    已经二叉树,前序遍历序列为{1,2,4,7,3,5,6,8},中序遍历序列{4,7,2,1,5,3,8,6},后序遍历序列是?【先建树在写二叉树】

    练习3 :

    已知一棵树二叉树的先根遍历和中根遍历的序列分别为:A B D G H C E F IG D H B A E C I F,请画出此二叉树,并写出它的后根遍的序列?

    练习4:

    已知二叉树,中根遍历序列为:6,3,4,1,5,8,2,7 后根遍历序列为:3,6,1,8,5,7,2,4 前根遍历序列?

    练习5:

    已知一棵树二叉树的后根遍历和中根遍历的序列分别为:A C D B G I H F EA B C D E F G H I 请画出该二叉树,并写出它的先根遍历的序列。

    如果文章对您有帮助,就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧!

     想要了解更多吗?没时间解释了,快来点一点!

    路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主路遥叶子擅长数据结构,安利Java零基础,spring,等方面的知识https://blog.csdn.net/zsy3757486?type=blog

    展开全文
  • 数据结构第六章课件及建立二叉树的二叉链表存储结构汇总,
  • 利用先序遍历输入法建立二叉树

    千次阅读 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;
    }

    实验结果:

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

    展开全文
  • 数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
  • 本设计中,对二叉树采用链式存储结构,其结构定义如下: typedef struct BiTNode{ TelemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 每个结点中设置三个域,即值域data,左指针域*lchild和右...
  • 采用二叉链表做存储结构,建立二叉树,借助于栈结构来实现二叉树遍历的非递归算法。 二叉树的链式存储结构,是指用链表来表示一棵二叉树,即用链来指示元素的逻辑关系,通常有二叉链表存储和三叉链表存储两种方式,...
  • 非递归建立二叉树

    千次阅读 2020-05-05 13:45:24
    二叉树的实现
  • 建立二叉树,前后中序遍历二叉树,求二叉树的深度
  • 1.建立二叉树、辅助链表、辅助队列结构体 typedef char CElemType; //建立二叉树的对应的结构体 typedef struct BiTNode { CElemType data; struct BiTNode* lchild, * rchild;//创建二叉树的左右孩子 }BiTNode,...
  • 前序递归建立二叉树

    千次阅读 2021-11-15 14:21:53
    上午在写二叉搜索树的最近公共祖先时,很尴尬,发现手写不出来递归建立二叉树的版本,不禁开始怀疑自己到底会不会二叉树,连最基本的建立都不会.....(趁着没人发现赶紧补习一波!!!冲冲冲!) 思路 其实递归建立二叉树和...
  • 队列层次建立二叉树

    千次阅读 2020-03-27 23:02:07
    /*利用顺序队列,层次建立二叉树*/ #include<stdio.h> #include<stdlib.h> #define MAXSIZE 1000 typedef struct TNode{//树的数据结构 char data; struct TNode *lchild,*rchild; }*BinTree; typedef...
  • 题目 description: 已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中,...主要递归函数*createBTNode()*采用先序建立二叉树 从0开始遍历数组str1[],每次在数组str2[]中找到与数组str1[]当前结点相等的结点
  • 后序建立二叉树

    千次阅读 2020-02-09 19:26:12
    采用后序的方法输出二叉树的节点 样例输出 …CFD…BEA 样例输出 F D B E C A 应该是反了,正确是A C E B D F 这道题的难点是需要从叶子节点进行回溯比较,我还没有想到比较简单的做法,欢迎交流。 算法思路: 1.后...
  • 已知后序序遍历序列和中序遍历序列建立二叉树。 例如输入后序遍历序列: FGDBCA, 再输入中序遍历序列: BFDGAC,则 输出该二叉树的先序遍历序列: ABDFGC。具体过程和上一个文章里的先序和中序确定二叉树一样不明白...
  • 已知先序遍历序列和中序遍历序列建立二叉树。 例如输入先序遍历序列: ABDFGC, 再输入中序遍历序列: BFDGAC,则 输出该二叉树的后序遍历序列: FGDBCA。解析:函数中的三个参数,第一个是先序,第二个是后序,第三...
  • 使用C++编写的二叉树类,采用非递归算法构造二叉树类;并附加有其他类函数,如前序、中序、后序及层序遍历函数,均以非递归算法实现;另外给出了测试用代码,验证算法的正确性
  • 按中序顺序建立一棵二叉树。 用先序非递归方式遍历二叉树。 算法设计 二叉树的创建可以是先序创建、先序中序创建、中序后序创建。显然不可以只用中序或者后序单独创建一棵二叉树。根据定义,二叉树的先序遍历是先...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 106,764
精华内容 42,705
关键字:

建立二叉树

友情链接: SAR压制干扰.rar