精华内容
下载资源
问答
  • 根据二叉树序列构造二叉树

    千次阅读 2017-04-11 19:23:49
    根据二叉树序列构造二叉树
    已知一棵二叉树的前序序列和中序序列,构造该二叉树的过程如下:
    1. 根据前序序列的第一个元素建立根结点;
    2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
    3. 在前序序列中确定左右子树的前序序列;
    4. 由左子树的前序序列和中序序列建立左子树;
    5. 由右子树的前序序列和中序序列建立右子树。
    已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:
    1. 根据后序序列的最后一个元素建立根结点;
    2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
    3. 在后序序列中确定左右子树的后序序列;
    4. 由左子树的后序序列和中序序列建立左子树;
    5. 由右子树的后序序列和中序序列建立右子树。
    例如:已知二叉树的中序序列BDCEAFHG , 后序序列DECBHGFA。
    先序:EBADCFHGIKJ->根:E
    根据根结点来划分中序序列
    中序:ABCDEFGHIJK->ABCD+E+FGHIJK
    由左右子树的结点集合来划分先序序列->先序:E+BADC+FHGIKJ
    分别对左右子树运用相同的方法分解出根和其左右子树的结点集合。依次递归
    展开全文
  • 二叉树序列化和反序列化1、二叉树 ——> 字符串(序列化)2、字符串 ——> 二叉树(反序列化)序列化的方式1、根据先序遍历序列化2、 根据中序遍历序列化3、根据后序遍历序列化4、按层序列化题目:给定一棵二叉树的...

    二叉树序列化和反序列化

    1、二叉树 ——> 字符串(序列化)

    2、字符串 ——> 二叉树(反序列化)

    序列化的方式

    1、根据先序遍历序列化

    2、 根据中序遍历序列化

    3、根据后序遍历序列化

    4、按层序列化

    题目:

    给定一棵二叉树的头节点head,并已知二叉树节点值的类型为32位整型。请设计一种二叉树序列化和反序列化的方案,并用代码实现。

    思路:

    例:先序遍历对二叉树进行序列化

    • 假设序列化结果为str, 初始时str为空字符串。
    • 先序遍历二叉树时如果遇到空节点,在str末尾加上 #!
    • 如果遇到不为空的节点,假设节点值是 4 ,就在str的末尾加上 4!

    举个栗子:

    这里写图片描述

    这里我们可能很奇怪为什么要用一个 ! 特殊字符来表示二叉树节点值的结束?

    这里写图片描述

    反序列化

    将一棵二叉树的先序遍历结果反序列化。

    这里写图片描述

    注意:

    • 选择用什么样的遍历方式序列化,就选择用什么样的方式反序列化。
    • 一棵树序列化的结果是唯一的,唯一的结果生成的二叉树也是唯一的。
    • 中序和后序遍历序列化和反序列化也是类似。

    按层遍历方式对二叉树序列化

    方法:

    • 用队列来进行二叉树的按层遍历,即宽度优先遍历。
    • 除了访问节点的顺序是按层遍历之外,对结果字符串的处理,与上面介绍的处理方式一样(添加特殊字符)。
    • 反序列化过程同理。
    展开全文
  • 二叉树序列化/反序列化

    千次阅读 多人点赞 2018-11-26 17:49:30
    因为要写入文件,我们要把二叉树序列化为一个字符串。 首先,我们要规定,一个结点结束后的标志:“!” 然后就可以通过先序遍历生成先序序列了。   但是,众所周知,只靠先序序列是无法确定一个唯一的二叉树的...

    二叉树被记录成文件的过程,为二叉树的序列化

    通过文件重新建立原来的二叉树的过程,为二叉树的反序列化

    设计方案并实现。

    (已知结点类型为32位整型)

     

    思路:先序遍历实现。

    因为要写入文件,我们要把二叉树序列化为一个字符串。

    首先,我们要规定,一个结点结束后的标志:“!”

    然后就可以通过先序遍历生成先序序列了。

     

    但是,众所周知,只靠先序序列是无法确定一个唯一的二叉树的,原因分析如下:

    比如序列1!2!3!

    我们知道1是根,但是对于2,可以作为左孩子,也可以作为右孩子:

    对于3,我们仍然无法确定,应该作为左孩子还是右孩子,情况显得更加复杂:

    原因:我们对于当前结点,插入新结点是无法判断插入位置,是应该作为左孩子,还是作为右孩子。

    因为我们的NULL并未表示出来。

    如果我们把NULL也用一个符号表示出来:

    比如

    1!2!#!#!3!#!#!

    我们再按照先序遍历的顺序重建:

    对于1,插入2时,就确定要作为左孩子,因为左孩子不为空。

    然后接下来两个#,我们就知道了2的左右孩子为空,然后重建1的右子树即可。

     

    我们定义结点:

    	public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

    序列化:

    	public static String serialByPre(Node head) {
    		if (head == null) {
    			return "#!";
    		}
    		String res = head.value + "!";
    		res += serialByPre(head.left);
    		res += serialByPre(head.right);
    		return res;
    	}

     

    	public static Node reconByPreString(String preStr) {
            //先把字符串转化为结点序列
    		String[] values = preStr.split("!");
    		Queue<String> queue = new LinkedList<String>();
    		for (int i = 0; i != values.length; i++) {
    			queue.offer(values[i]);
    		}
    		return reconPreOrder(queue);
    	}
    
    	public static Node reconPreOrder(Queue<String> queue) {
    		String value = queue.poll();
    		if (value.equals("#")) {
    			return null;//遇空
    		}
    		Node head = new Node(Integer.valueOf(value));
    		head.left = reconPreOrder(queue);
    		head.right = reconPreOrder(queue);
    		return head;
    	}

    这样并未改变先序遍历的时空复杂度,解决了先序序列确定唯一一颗树的问题,实现了二叉树序列化和反序列化。

    展开全文
  • 程序功能:输入二叉树先序序列,输出先序,中序,后序序列 作者:令狐荣豪 完成日期:2019/5/19 =====================================================*/ #include<stdio.h> #include<st...
    /*====================================================
    程序功能:输入二叉树先序序列,输出先序,中序,后序序列
    作者:令狐荣豪
    完成日期:2019/5/19
    =====================================================*/
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct BiTNode
    {
    	char data;//定义二叉链表的结构体
    	struct BiTNode *lchild, *rchild;
    }Bitree;
    
    Bitree *CreateBtree_DLR(Bitree* root);//以先序遍历二叉树
    void PreOrder(Bitree* T);//先序遍历二叉树
    void InOrder(Bitree *T);//中序遍历二叉树
    void PostOrder(Bitree *T);//后序遍历二叉树
    
    
    /*================================
    函数功能:构建二叉树
    =================================*/
    Bitree* CreateBtree_DLR(Bitree* root)
    {
    	char ch;
    	scanf("%c", &ch);
    	if (ch == '@')
    		root = NULL;
    	else
    	{
    		root = (Bitree*)malloc(sizeof(Bitree));
    		root->data = ch;
    		root->lchild = CreateBtree_DLR(root->lchild);//构造左子树
    		root->rchild = CreateBtree_DLR(root->rchild);//构造右子树
    	}
    	return (root);
    }
    
    /*==================================
    函数功能:先序遍历递归算法
    函数输入:树的根结点
    ===================================*/
    void PreOrder(Bitree *T)
    {
    	if (T != NULL)
    	{
    		printf("%c", T->data);
    		PreOrder(T->lchild);
    		PreOrder(T->rchild);
    	}
    }
    
    /*==================================
    函数功能:中序遍历
    ===================================*/
    void InOrder(Bitree *T)
    {
    	if (T != NULL)
    	{
    		InOrder(T->lchild);
    		printf("%c", T->data);
    		InOrder(T->rchild);
    	}
    }
    
    /*=================================
    函数功能:后序遍历
    ==================================*/
    void PostOrder(Bitree *T)
    {
    	if (T != NULL)
    	{
    		PostOrder(T->lchild);
    		PostOrder(T->rchild);
    		printf("%c",T->data);
    	}
    }
    
    int main()
    {
    	Bitree *T = NULL;
    	printf("输入二叉树的先序遍历结点,建立二叉树。(子树为空时输入@)\n");
    	T = CreateBtree_DLR(T);
    
    	printf("\n先序遍历结果:\n");
    	PreOrder(T);
    	printf("\n中序遍历结果:\n");
    	InOrder(T);
    	printf("\n后序遍历的结果:\n");
    	PostOrder(T);
    	return 0;
    }
    
    展开全文
  • 本文主要介绍二叉树序列化和反序列化,内容为二叉树和数组的互相转化。 二叉树序列化 按层遍历二叉树 输出数组 S形遍历二叉树 输出数组 先序遍历二叉树 输出数组 中序遍历二叉树 输出数组 后序遍历二叉树 输出...
  • /*题目描述输入二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列输入第一行输入二叉树的先序遍历序列;第二行输入二叉树的中序遍历序列。输出输出该二叉树的后序遍历序列。示例输入ABDCEFBDAECF...
  • 二叉树序列

    千次阅读 2011-12-05 21:17:23
    问题:如何将二叉树序列化为一个文本文件,使得文件的大小尽可能的小。  想了四种方法:  第一种方法:把二叉树按前序和中序遍历一遍,存两次二叉树。  第二种方法:将二叉树按左枝为0,右枝为1进行路径编码,...
  • 下面三种序列可以唯一的构造唯一的一棵二叉树: 前序序列和中序序列构造二叉树 后序序列和中序序列构造二叉树 层次遍历序列和中序遍历序列构造二叉树 #include<stdio.h> #include<stdlib.h> #...
  • 【题目】C++输入二叉树的层序遍历序列,输出其前序遍历序列 代码: #include<iostream> #include<vector> #include<string> using namespace std; struct TreeNode { string val;//节点的...
  • 二叉树序列化和反序列化(先序)

    千次阅读 2018-05-23 19:07:56
    二叉树序列化将序列化的数据存储到一个数组里,要求数据后面加”!“,没有的数据的用”#!“表示。#include&lt;iostream&gt; #include&lt;string&gt; using namespace std; typedef struct Node ...
  • 请实现两个函数,分别用来序列化和反序列二叉树。 解题思路 序列二叉树:把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是,序列二叉树的过程中,如果遇到空节点,需要以某种符号...
  • 一、二叉树的分层遍历 给定一棵二叉树,要求进行分层遍历,每层的节点值单独打印一行,下图给出事例结构: 思路: 增加两个TreeNode:last和nlast last:表示当前遍历层最右结点 nlast:表示下一层最右结点 ...
  • 二叉树被记录成文件的过程叫做二叉树序列化。序列化的方法有很多,这里我们采用括号序列的方法将其序列化,所谓括号序列指的是对于一个节点生成一个括号,括号内是其子树的括号序列,其中左儿子(若存在)的括号在前...
  • 根据前序序列和中序序列构造二叉树  二叉树的节点类型声明如下:struct BTNode { char val; BTNode *left; BTNode *right; BTNode(char c):val(c), left(NULL), right(NULL); };定理1 任何(n>=0)个不同节点...
  • 二叉树4:二叉树序列化和反序列

    万次阅读 多人点赞 2017-05-02 22:32:55
    二叉树4:二叉树序列化和反序列
  • 先序序列和中序序列构造二叉树,中序序列和后序序列构造二叉树
  • #include #include int pre_p=1,pre[1001],in...//pre为前序序列数组,in为后序序列数组,n为二叉树中的元素个数,即序列长度,count_print用于规范输出格式 typedef struct Node { int data; struct Node *lchil
  • 当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时,其后序序列为什么?当一棵二叉树前序序列和中序序列分别为HGEDBFCA和EGBDHFAC时,其后序序列为什么?虽然我已知道答案为EBDGACFH,请求详细算法,c语言...
  • ensp根据二叉树序列化的定义,二叉树序列化比较简单,用#表示为空,保存时,每个节点用逗号隔开,这样,用前序遍历的形式就可以很容易序列化二叉树。反序列化也同理: class Solution: def __init__(self): se...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 110,661
精华内容 44,264
关键字:

怎么输入二叉树的序列