精华内容
下载资源
问答
  • 如果已知某二叉树的前序遍历结果为{1,2,4,7,3,5,6,8},中序遍历序列为{4,7,2,1,5,3,8,6},求此重建后的二叉树。 1、实现思路:  我们都知道前序遍历是访问节点,然后是左子树,接着是右子树,因此在前序遍历...
            关于二叉树的概念,想必大家基本上都已经很清楚了,那么在这里我就不再一一赘述了。那么请看下面这道题:
    如果已知某二叉树的前序遍历结果为{1,2,4,7,3,5,6,8},中序遍历序列为{4,7,2,1,5,3,8,6},求此重建后的二叉树。
    1、实现思路:
          我们都知道前序遍历是先访问根节点,然后是左子树,接着是右子树,因此在前序遍历序列中,第一个节点值就是根结点的值。但是在中序遍历中根节点是处在序列的中间,左子树的节点的值是位于根节点的左边,右子树的节点的值位于根结点值的右边,因此我们可以通过扫描中序遍历的序列来确定根节点的值和它的右子树和左子树。
    分析过程如下图所示:

    具体的代码实现如下图所示:
    #include<iostream>
    using namespace std;

    //结点信息
    struct BinaryTreeNode
    {
               int _value;
               BinaryTreeNode* _left;
               BinaryTreeNode* _right;
    };

    BinaryTreeNode* RebuiltTree(int * preorder, int* inorder , int length)
    {
               //判空
               if(preorder == NULL || inorder == NULL || length <= 0)
              {
                        return NULL ;
        }

               return _RebuiltTree(preorder , preorder + length - 1, inorder , inorder + length - 1);
              
    }

    //重建二叉树--->传入前序遍历序列的头指针与尾指,中序遍历序列的头指针与尾指针针
    BinaryTreeNode* _RebuiltTree(int * startpreorder, int* endpreorder ,int* startinorder,int * endinorder)
    {
               int rootvalue = startpreorder [0];//前序遍历序列的第一个值为重建后二叉树的根节点的值
               BinaryTreeNode* root = new BinaryTreeNode(); //创建一个指针,并为它申请一块空间,并且这个指针有此二叉树每个节点应有的全部内容
               //将根结点的值赋给root->_value,并且将root->_left 与 root->_right都赋为空
              root->_value = rootvalue;
              root->_left = root->_right = NULL;

               //在前序遍历序列中找根节点
               if (startpreorder == endpreorder)
              {
                        if (startinorder == endinorder && * startpreorder == *startinorder)//如果此条件满足,则找到根结点的值
                       {
                                  return root;
                       }
                        else
                       {
                                 cout<< "非法输入" <<endl;
                       }
              }

               //在中序遍历中找到根结点的值,然后将中序遍历序列划分为两个区间,一个是根节点左边的左子树区间,一个是根节点右边的右子树区间
               int* _startinorder = startinorder ;//让_startinorder指向startinorder,以防后面改变startinorder,从而在后面无法确定左子树的区间。
              
               //在中序遍历序列中查找根结点的值
               while (_startinorder <= endinorder && *_startinorder != rootvalue)
              {
                       ++_startinorder;
              }
               //_startinorder与endinorder相等,并且*_startinorder != rootvalue说明中序遍历序列中没有根节点。
               if (_startinorder == endinorder && *_startinorder != rootvalue)
              {
                       cout << "非法输入" << endl;
              }
               //走到这里说明_startinorder指针已经走到根结点的位置
               int leftlength = _startinorder - startinorder ;//求出左子树的长度及结点个数
               int* leftpreorderEnd = startpreorder + leftlength;
               if (leftlength > 0)
              {
                   //构建左子树
                       root->_left = _RebuiltTree( startpreorder + 1, leftpreorderEnd, startinorder , _startinorder - 1);
              }
               if (leftlength < endpreorder - startpreorder)
              {
                   //构建右子树
                       root->_right = _RebuiltTree(leftpreorderEnd + 1, endpreorder, _startinorder+1, endinorder );
              }
               return root;
    }
    void Test()
    {
               BinaryTreeNode* ret = NULL ;
               int preorder[] = { 1, 2, 4, 7, 3, 5, 6, 8 };
               int inorder[] = { 4, 7, 2, 1, 5, 3, 8, 6 };
              ret = RebuiltTree(preorder, inorder, 8);
              cout << "ret=" << ret << endl;
    }

    展开全文
  • 正常来说只是知道一个二叉树的先序遍历是无法确定一颗二叉树的,但是作为一棵满二叉树,树的形态确定了,先序遍历的顺序固定左右”的条件下,二叉树也就得以确定。        ...

    满二叉树,已知其先序序列求后续序列 C++实现

    分析

           正常来说只是知道一个二叉树的先序遍历是无法确定一颗二叉树的,但是作为一棵满二叉树,树的形态确定了,先序遍历的顺序固定为“根左右”的条件下,二叉树也就得以确定。
           那么在满二叉树的情况下,如何通过先序遍历得到后续遍历呢?让我们先进行下面的分析

    实例分析

    案例满二叉树
    以上图二叉树作为例子:
        其先序遍历为:abdecfg(根左右)
        后续遍历为: debfgca (左右根)

    通常情况下,我们进先序遍历,一定是从根出发,于是这个根便是整个序列中的“头部”:
                   a |  bdecfg
    去掉“头部”以后,剩下的部分由左右两个子树构成。因为先序是根左右的次序,观察&思索也可以发现——剩下的部分从中间等分刚好可以得到这颗树的左右两个子树部分
                   bde  |  cfg
    化分出来的两个子序列也是子树的先序遍历:
                   b |  de               c |  fg

    于是就形成一个“套娃”。然后首先会做出的反应就是递归。

    实现思路

           既然已经确定使用递归了,现在的关键就是:怎么递归、在哪里使用递归、递归做什么以及递归结束的条件(也就是寻找最小的子问题)。
           通过上述实例的分析,整个满二叉树先序遍历的序列可以的流程为:根->左子树->右子树;每颗子树的流程也是:根->左子树->右子树。现在要获取的是后续遍历,在不耗费额外空间时间重构整棵树的条件下,把这个过程改为:左子树->右子树->根。
           在先序序列中如何体现 左子树->右子树->根 的流程呢?不妨在草稿纸上用刚刚的实例看看:
    案例满二叉树
    先序拆解:
                   a |    bde | cfg
                   a |    (b| de) | (c| fg)

    后序(左右根):((de) b)->((fg)c)-> a

    可以发现实际上就是把序列分成:头部、左部、右部,然后按照:左部——右部——头部 的顺序输出。头部只有一个字符,左右部本身视作一个新的先序序列再次划分三部。
           划到后面,左右部只剩下三个字符组成的先序,此时最后一次化分,可以得到只有头部的先序序列,只需要输出头部就可以了,然后逐步回代,因为子树的头输出过了,组成大树以后,其左右子树也就已经完成的输出,也只需要输出头部即可。

    于是就有
    化分函数(树先序序列 ){
        if(序列数量大于一个){
            化分函数(左子树先序序列);
            化分函数(右子树先序序列);
        }
        输出根(头部序列);
    }

    代码实现

    #include <iostream>
    //#include<cmath>
    using namespace std;
    
    #define GET_ARRAY_LEN(array, len) { len = sizeof(array)/sizeof(array[0]);}
    //获取数组长度宏
    
    
    /**
    * @a           目标数组
    * @begin  子树开始的下标
    * @end    子树结束的下标
    **/
    void preToPost(char a[],
    	int begin,
    	int end
    	) {
    	char root = a[begin];   //暂存根,子树遍历完后最后输出
    	
    	if (begin + 1 <= end) {
    		begin = begin + 1;//左端+1(把根节点独立出来)
    		
    		//此时左子树从begin+1位开始,到(begin+end)/2)结束
    		preToPost(a, begin,((begin+end)/2)); //左子树
    
            //此时右子树从((begin+end)/2) + 1)位开始,到end结束
    		preToPost(a, (((begin+end)/2) + 1), end); //右子树
    	}
    	cout << root;  //输出根
    
    }
    
    void main() {
    	//测试数据
    	//char a[] = { 'a','b','d','h','i','e','j','k','c','f','l','m','g','n','o' };  
    	char a[] = { 'a','b','d','e','c','f','g' };
    	int length;  //字符数组长度
    	
    	/*
    	这里可以添加一个判断序列数量是否满足满二叉树的判定
    	if (  ) {
    	   cout<<"输出数据不满足满二叉树条件"<<endl;
    		return ;// 判断是否满足满二叉树的条件
    	}*/
    	
    	GET_ARRAY_LEN(a, length); //调用写好的宏得到数组长度
    	
    	//测试数据输出
    	cout<<"先序遍历为:"<<endl;
    	for (int i = 0;i < length;i++)
    		cout << a[i];
    	cout << endl;
    	
    	cout<<"后序遍历为:"<<endl;
    	preToPost(a, 0, length - 1);
    	cout << endl << endl << endl << endl;
    }
    

    测试结果

    打印结果
    运行环境:Windows10 家庭版、Visual Studio 2019

    展开全文
  • 的先根序列对应二叉树的先序遍历 树的后根序列对应二叉树的中序遍历 从树的二叉链表表示的定义可知,任何一棵和数对应的二叉树,其右子树必空。 都遵循这样一个规律:左孩子右兄弟(也就是说,在二叉树转换...

    树、森林和二叉树的转换

    树转换为二叉树:

     树的先根序列对应二叉树的先序遍历

     树的后根序列对应二叉树的中序遍历

     

    从树的二叉链表表示的定义可知,任何一棵和数对应的二叉树,其右子树必为空。

    都遵循这样一个规律:左孩子右兄弟(也就是说,在二叉树转换为树或者是森林的时候,左孩子是左孩子,右孩子是左孩子的兄弟)

    下面请IGN

    森林转换为二叉树

    (1)把每棵树转换为二叉树。

    (2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。

    展开全文
  • 下面两行先后给出先序和中序遍历序列,均是长度N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 本题主要分成两个...

    4-1-1 && 4-1-4 二叉树及其遍历 树的遍历 && 还原二叉树 (25 分)

    4-1-4 二叉树及其遍历 还原二叉树 (25 分)

    给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。

    输入格式:

    输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。

    输出格式:

    输出为一个整数,即该二叉树的高度。

    输入样例:

    9
    ABDFGHIEC
    FDHGIBEAC
    

    输出样例:

    5
    

    本题主要分成两个部分:根据先序和中序遍历序列建树、求高度

    (中 + 先/后 -> 后/先)(即必须包含中序遍历序列)

    根据先序和中序遍历序列建树:先序序列第一个是根节点,根据根节点在中序序列的位置可以确定左子树和右子树的元素,然后开始递归建左右子树

    求高度:递归实现

    //中 + 先 -> 后
    #include<iostream>
    using namespace std;
    #define MAXN 55
    
    struct Tree
    {
    	char ch;
    	struct Tree* left;
    	struct Tree* right;
    };
    typedef struct Tree* PTree;
    
    PTree BuildTree(char* pre, char* in, int n)
    {
    	if (n == 0)return NULL;
    
    	int m;//找到头结点在中序序列中的位置
    	for (m = 0; in[m] != pre[0]; m++);
    
    	PTree T = new Tree;
    	T->ch = pre[0];
    
    	T->left = BuildTree(pre + 1, in, m);//建立左子树
    	T->right = BuildTree(pre + m + 1, in + m + 1, n - m - 1);//建立右子树
    	return T;
    }
    
    int GetHeight(PTree T)
    {
    	if (T == NULL)
    		return 0;
    	int m = GetHeight(T->left);
    	int n = GetHeight(T->right);
    	return max(m + 1, n + 1);
    }
    
    int main()
    {
    	int n; cin >> n;
    	char preorder[MAXN], inorder[MAXN];
    	for (int i = 0; i < n; i++)
    		cin >> preorder[i];//先序
    	for (int i = 0; i < n; i++)
    		cin >> inorder[i];//中序
    
    	PTree T = BuildTree(preorder, inorder, n);
    	cout<< GetHeight(T);
    
    	return 0;
    }
    

    思考:如何根据后序遍历序列和中序遍历序列建树?

    4-1-1 二叉树及其遍历 树的遍历 (25 分)

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    输入格式:

    输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

    输出格式:

    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。

    输入样例:

    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    

    输出样例:

    4 1 6 3 5 7 2
    
    #include<iostream>
    #include<queue>
    using namespace std;
    #define MAXN 35
    typedef struct Tree* pTree;
    struct Tree
    {
    	int data;
    	pTree left;
    	pTree right;
    };
    
    pTree BuildTree(int* post, int *in, int n)
    {
    	if (n == 0)return NULL;
    
    	int m;
    	for (m = n - 1; in[m] != post[n - 1]; m--);
    
    	pTree T = new Tree;
    	T->data = post[n - 1];
    
    	T->left = BuildTree(post, in, m);
    	T->right = BuildTree(post + m, in + m + 1, n - m - 1);
    	return T;
    }
    
    void Levelorder(pTree T)
    {
    	int flag = 0;
    	queue<pTree>q;
    	q.push(T);
    	while (!q.empty())
    	{
    		pTree temp = q.front();
    		q.pop();
    		if (flag++)cout << " ";
    		cout << temp->data;
    		if (temp->left)
    			q.push(temp->left);
    		if (temp->right)
    			q.push(temp->right);
    	}
    }
    
    int main()
    {
    	int postorder[MAXN], inorder[MAXN];
    	int n; cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> postorder[i];
    	for (int i = 0; i < n; i++)
    		cin >> inorder[i];
    
    	pTree T = BuildTree(postorder, inorder, n);
    	Levelorder(T);
    
    	return 0;
    }
    
    展开全文
  • 一、构造二叉树①:在数据结构中,我们一般都会有...下面直接用例子讲最通俗易懂的了:例:前序和中序,构造二叉树下面还有两个例子,你们可以尝试做一下:1、已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L...
  • PTA 还原二叉树

    2020-08-19 22:06:36
    下面两行先后给出先序和中序遍历序列,均是长度N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出一个整数,即该二叉树的高度。 输入样例: 9 ABDFGHIEC FDHGIBEAC 输出样例: 5 看怎么恢复...
  • 二叉排序树中第k个结点,即二叉排序树中序序列中顺序号k结点,结点Lsize域中存放结点顺序号。要确定二叉排序树中第k个结点,需将k与结点顺序号进行比较,若相等,则找到;若k小于结点...
  • 一、构造二叉树①:在数据结构中,我们一般都会有...下面直接用例子讲最通俗易懂的了:例:前序和中序,构造二叉树下面还有两个例子,你们可以尝试做一下:1、已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L...
  • 7-23 还原二叉树 (25 分)

    千次阅读 2018-11-01 20:29:16
    给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。 输入格式: 输入首先给出正整数N(≤50),树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度N的不包含重复英文字母(区别...
  • 前面我们介绍了树基本概念,并引出了...下面,我们来看一看二叉搜索树。BST(BinarySearchTree,二叉搜索树)可以提高查找性能,二叉搜索树相比于其他数据结构优势在于查找、插入时间复杂度较低,平均O(lo...
  • 首先定义一种前序遍对称的算法,遍历一棵二叉树的根结点,再遍历它的右子结点,最后遍历它的左子结点。 以下面两棵树为例: 对于树A,可以图中看出它明显对称。它的前序遍历序列为{1,2,3,4,2,4,3},前序对称遍历...
  • 下面两行先后给出先序和中序遍历序列,均是长度N的不包含重复英文字母(区别大小写)的字符串。 输出格式: 输出一个整数,即该二叉树的高度。 思路:根据前序遍历和中序遍历来确定左右子树,找到树根即前序...
  • 由前序遍历和中序遍历重建二叉树(前序序列:1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5)今天Val来分享如何利用一个前序遍历和中序遍历来重建...下面以图中二叉树为例子讲解:由前序遍历结果我们可以知道每次遍历的根
  • 练习(8-29)

    2019-08-29 21:51:03
    答:一棵树的先根遍历与其对应二叉树的先序遍历结果相同,树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。 由于二叉树表示的先序遍历和中序遍历棵唯一确定一棵二叉树。因此给定一棵树的先根遍历序列和后跟...
  • 结构可以分为大根堆和小堆,是一个完全二叉树,而堆排序是根据堆这种数据结构设计一种排序,下面先来看看什么是大根堆和小堆 性质:每个结点值都大于其左孩子和右孩子结点值,称之大根堆;每个...
  • 数据结构 树 思考题3

    千次阅读 2020-03-17 12:48:08
    题目1:给出下面这棵树中序遍历结果 根据中序遍历程序: 我们可以看到它不断往左遍历,然后在分叉处到...题目2:非递归方法中序遍历下面这颗二叉树,其堆栈操作序列(P代表push,O代表pop)是什么?...
  • (1)序列按照完全二叉树的排列方法写出来。 (2)从下往上、从左往右找到第一个非叶子结点开始,进行堆调整。如果父结点大于子结点,则不用调整;如果父结点小于子结点,则把父结点和子结点中较大的一个交换。...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    2、实现1所要求代码后,运行设计好代码,将以下几组整数序列建成搜索二叉树,并记录下它们前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
  • 已知前序遍历和后序遍历序列,是无法确定一棵二叉树的,原因在于如果只有一棵子树可能是左孩子也有可能是右孩子。由于只要输出其中一个方案,所以假定左孩子即可。下面就是如何根据前序和后序划分出节点和左右...
  • 例如,长度为8线性表关键码序列为:[6,13,27,30,38,46,47,70],被查元素为38,首先将与线性表中间项比较,即与第4个数据元素30相比较,38大于中间项30值,则在线性表[38,46,47,70]中继续查找;...
  •  已知前序遍历和后序遍历序列,是无法确定一棵二叉树的,原因在于如果只有一棵子树可能是左孩子也有可能是右孩子。由于只要输出其中一个方案,所以假定左孩子即可。下面就是如何根据前序和后序划分出节点和左右...
  • 数据结构实验

    2012-04-13 09:55:47
    例如:当n=8,m=4,i=1时,得到序列为: 4,8,5,2,1,3,7,6 编写程序选择循环队列作为存储结构模拟整个过程,并依次输出出列各人编号。 实验4:矩阵压缩存储及相关操作 (第11周星期三7、8节) 一 、...
  • (53) 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它前序遍历序列是(A) 注:P38,前提要掌握三种遍历方法 A. cedba B. acbed C. decab D. deabc (54) 在下列几种排序方法中,要求内存量最大是(D) 注...
  • 它应该满足下面的特征: <ul><li>集合中必存在唯一一个“第一个元素”</li><li>集合中必存在唯一一个“最后元素”</li><li>除最后一元素之外,其它数据元素均有唯一“后继”</li><li>除第一个...
  • 1. 层次结构模型: 层次结构模型实质上是一种有结点定向有序树,IMS(Information Manage-mentSystem)是其典型代表。 2. 网状结构模型:按照网状数据结构建立数据库系统称为网状数据库系统,其典型代表是DBTG...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

下面二叉树的先根序列为