C++实现已知二叉树前序遍历和中序遍历,求后序遍历 |
您所在的位置:网站首页 › 如何通过先序遍历和中序遍历确定后序遍历 › C++实现已知二叉树前序遍历和中序遍历,求后序遍历 |
一、基本概念
1.先序遍历(NLR)可以确定二叉树的父子结点; 2.中序遍历(LNR)可以确定二叉树的左右子树; 3.后序遍历(LRN)可以确定二叉树的父子结点; 二、结论1.已知先序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,可以得出二叉树的后序遍历; 2.已知后序遍历,中序遍历序列,能够创建出一棵唯一的二叉树,进而可以得出二叉树的先序序列; 3.综上,必须含有中序遍历(确定二叉树左右孩子),先序遍历或者后序遍历任选一个(确定二叉树父子结点),就可以确定一棵唯一的二叉树 三、C++代码实现1.已知先序遍历和中序遍历,打印后序遍历(见函数void postorder(string preorder, string inorder)); 2.已知中序遍历和后序遍历,打印先序遍历(见函数void preorder(string inorder, string postorder)); #include #include using namespace std; /* 假设根节点在中序遍历中的位置为pos,树的结点数为len,即 len=inorder.length() 代码:pos = inorder.find(preorder[0]) or pos = inorder.find(postorder[postorder.size()-1]) 先序遍历(NLR), 根节点编号(0), 左子树编号(1~pos), 右子树编号(pos+1~len-1) 中序遍历(LNR), 左子树编号(0~pos-1), 根节点编号(pos), 右子树编号(pos+1~len-1) 后序遍历(LRN), 左子树编号(0~pos-1), 右子树编号(pos~len-2), 根点编号(len-1) */ void postorder(string preorder,string inorder){//由先序遍历+中序遍历序列,递归实现后序遍历 (LRN) int len = preorder.length(); if(len==0) return; if(len==1) { //单个结点 cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |