当前位置:  编程技术>c/c++/嵌入式

C++实现二叉树遍历序列的求解方法

    来源: 互联网  发布时间:2014-10-27

    本文导语:  本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值。具体分析如下: 一、由遍历序列构造二叉树              如上图所示为一个二叉树,可知它的遍历序列分别为: ...

本文详细讲述了C++实现二叉树遍历序列的求解方法,对于数据结构与算法的学习有着很好的参考借鉴价值。具体分析如下:

一、由遍历序列构造二叉树

        

    如上图所示为一个二叉树,可知它的遍历序列分别为:

                      先序遍历:ABDECFG

                      中序遍历:DBEAFCG

                      后序遍历:DEBFGCA

我们需要知道的是,由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树;由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树;但是如果只知道先序序列和后序序列,则无法唯一确定一棵二叉树。

二、已知二叉树的先序序列和中序序列,求后序序列。

因为由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树,所以进而可以唯一地确定它的后序遍历。在先序遍历序列中,第一个结点一定是二叉树的根结点,而在中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列就是左子树的中序序列,后一个子序列就是右子树的中序序列。根据这两个子序列的长度,可以在先序序列中找到对应的左子树先序序列和右子树先序序列。而左子树先序序列的第一个结点是左子树的根结点,右子树先序序列的第一个结点是右子树的根结点。如此递归地进行下去,便能唯一地确定这棵二叉树。

C++实现代码如下:

/*************************************************************************
 > File Name: Test.cpp
 > Author: SongLee
 ************************************************************************/
#include
using namespace std;

struct TreeNode
{
  struct TreeNode* left;
  struct TreeNode* right;
  char elem;
};


TreeNode* PostOrderFromOrderings(char* inorder, char* preorder, int length)
{
  if(length == 0)
  {
    return NULL;
  }
  TreeNode* node = new TreeNode;
  node->elem = *preorder;
  int rootIndex = 0;
  for(; rootIndex < length; rootIndex++) // 求左子树的长度
  {
    if(inorder[rootIndex] == *preorder)
      break;
  }
  node->left = PostOrderFromOrderings(inorder, preorder + 1, rootIndex);
  node->right = PostOrderFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
  cout elem  Author: SongLee
 ************************************************************************/
#include
using namespace std;

struct TreeNode
{
  struct TreeNode* left;
  struct TreeNode* right;
  char elem;
};

TreeNode* PreOrderFromOrderings(char* inorder, char* postorder, int length)
{
  if(length == 0)
  {
    return NULL;
  }
  TreeNode* node = new TreeNode;
  node->elem = postorder[length-1];
  int rootIndex = 0;
  for(; rootIndex < length; rootIndex++)  // 求左子树的长度
  {
    if(inorder[rootIndex] == postorder[length-1])
      break;
  }
  cout elem left = PreOrderFromOrderings(inorder, postorder, rootIndex);
  node->right = PreOrderFromOrderings(inorder + rootIndex + 1, postorder + rootIndex, length - (rootIndex + 1));
  return node;
}

int main()
{
  char* post = "DEBFGCA";
  char* in = "DBEAFCG";
  PreOrderFromOrderings(in, post, 7);
  cout 

    
 
 

您可能感兴趣的文章:

  • Base64编码原理详解及c++编码解码实现
  • 我实现了个J2EE技术的服务器,支持TCP、UDP和数据库,由于性能的原因,需要改为C或C++实现,我是C、C++新手,我该如何入手呢?看什么样的
  • c++实现MD5算法代码示例
  • java 与 C++ 实现后绑定的方法
  • c++通用模板类(template class)定义实现详细介绍
  • Qt实现的C++框架 qtioccontainer
  • 用C或C++实现主存的分配与回收
  • 在linux系统上,如何用C++实现获取和设置系统时间?
  • 文本压缩算法C++实现 Golden Huffman
  • C++标准库实现 libc++
  • C++的XMLRPC实现 XMLRPC++
  • Java/JavaScript API 的 C++ 实现 libj
  • c++ 连接两个字符串实现代码 实现类似strcat功能
  • c++在unix中如何实现CString的方法?或者说有没有替换CString的类?
  • 请问:java中如何实现C++中的sizeof()方法?
  • 用C或C++编程,模拟可变分区存储管理且首次适应的算法实现存储器的分配与回收
  • vim中如何实现c++代码编写的自动格式化和语法高亮的功能?
  • C++实现CreatThread函数主线程与工作线程交互的方法
  • 请教为什么在C++编译通过并实现的程序,在linux下就会出错
  • linux下c++怎样实现回调(CALLBACK)函数?
  • 在linux下如何用c++实现建立一个文件夹
  • 先序遍历二叉树的递归实现与非递归实现深入解析
  • 请问怎么用Java实现一个URL的遍历??急!!!!
  • PHP采用自定义函数实现遍历目录下所有文件的方法
  • C#使用yield关键字让自定义集合实现foreach遍历的方法
  • 在java的GUI的应用程序中能否实现对容器(如Frame)中的所有组件遍历?
  • C++实现二叉树非递归遍历方法实例总结
  • JAVA遍历map的几种实现方法代码
  • python实现dict版图遍历示例
  • Jquery遍历节点的实现代码
  • 关于shell遍历查询怎么实现?
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 求解!Java如何能在多个applet之间实现类似asp的session类!
  • PXA270下利用IIS通道实现音频,重复启动死机问题求解
  • 不理解exec家族的调用是如何实现的。。。求解
  • NRPE+Nagios + NetSnmp 实现系统监控求解
  • 请问如何用java实现ie的save as...的功能?(200分求解,不够另加)
  • c语言多线程实现并行服务器遇到点小问题,求解!
  • 实现类似ls功能遇到的问题,求解!
  • 关于shell实现。。求解
  • c#实现一元二次方程求解器示例分享
  • 高分求解!请问类似tomcat服务器的启动关闭是怎样实现?
  • 高分求解---struts怎样实现表单验证不通过重新导向输入页面,并给出出错信息?
  • C++实现第K顺序统计量的求解方法
  • 通过javascript实现DIV居中,兼容各浏览器版本
  • socket实现多文件并发传输,求助多线程实现问题?
  • Python GUI编程:tkinter实现一个窗口并居中代码
  • interface 到底有什么用???实现接口,怎么实现??
  • 通过javascript库JQuery实现页面跳转功能代码
  • 怎么用Jsp实现在页面实现树型结构?
  • sharepoint 2010 使用STSNavigate函数实现文件下载举例
  • windows 下的PortTunnel 在linux下怎么实现?或者相应的已经实现的软件?端口映射
  • php实现socket实现客户端和服务端数据通信源代码
  • 网站重定向用C语言实现iptables,ACL实现
  • flash AS3反射实现(describeType和getDefinitionByName)
  • 在linux下如何编程实现nslookup命令实现的IP地址和域名互相转换的功能?
  • boost unordered_map和std::list相结合的实现LRU算法
  • 求在freebsd+Squid下实现pc上网的透明代理的实现方法!给出具体配置方法的高分谢!
  • c#通过委托delegate与Dictionary实现action选择器代码举例
  • linux下如实现与window下的驱动器实现文件共享??
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • qt如何实现:操作键盘实现数据的滚动?
  • iphone cocos2d 精灵的动画效果(图片,纹理,帧)CCAnimation实现




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3