【自考】数据结构之二叉树遍历，数据结构二叉树

   什么是数据结构？

   首先看看维基百科的定义：在计算机科学或信息科学中，数据结构（英语：data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。

    课本中的定义：指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机中的存储方式，以及定义在该组数据上的一组操作。

   有哪些内容？

   直接看图了解数据结构的知识点，如下：

    不管是算法还是逻辑结构，都是用数据说话的，所以要先明白了数据的基本概念。大的联系图中已给出，小的知识点需要我们去理解学习。

    这篇博客主要讲一个好玩的知识点：

二叉树遍历

   概念性的知识不再赘述，不懂得可以先看看书。直接通过一道题讲三种遍历(先序，中序，后序)的思路。

   首先附图一张：

 例：一棵二叉树的先序遍历序列为ABCFHIDGJE，中序遍历序列为AHIFCJGDEB。

 解题思路：

通过先序和中序或是中序和后序，都能唯一确定一颗二叉树。

     每确定一个节点就把它从序列中暂时去除，这样就不会干扰下一步，帮助我们理清思路。

     总结： 

      用一种自己理解的方式去做，就会发现其实不难。最近好几个人问过这个问题，总是做着做着就把自己绕进去了。其实这里只要知道三种遍历的规则，理清思路，就没问题啦！

      这只是个人理解，有更好理解的欢迎交流学习！

知道先序（根左右）和中序（左根右），可求后序（左右根）；知道中序和后序，可求先序；知道先序后序，求出的2叉树不唯一。这些书上都讲过。根据这些推。

32.B
33.A
34.D 首先确定根结点是C，该2叉树根结点无右子树，然后后序只剩下dabe了，中序为deba,
e,又确定e为根，而中序的左边只有d，所以e的左孩子是d,所以中序右边只剩ba没确定了。
而后序则是ab,所以能确定a是b的右孩子。
35.B
其它的都按照这样推，就OK
只要记住先序（根左右）中序（左根右）后序（左右根）.就行。
 

在后序遍历中找到根节点,
然后在中序遍历中找到左右子树.
将找到的根节点按序写就是前序遍历

后序遍历为DGJHEBIFC (A)
中序遍历为DBGEHJ (A) CIF
->后序遍历为DGJHEB IFC (A)
前序遍历 A

(A)的左子树后序遍历 DGJHE (B)
(A)的左子树中序遍历 D (B) GEHJ
->(A)的左子树后序遍历为D GJHE(B)
前序遍历 AB

以此类推,前序遍历为ABDEGHJCFI

#include <iostream>
#include <assert.h>
#include <string.h>
#include "BinaryTreeNode.h"
#include "BinaryTree.h"
using namespace std;

/////////////////////////////////////////////////
// 访问当前结点 current

template < class T >
void visitNode( BinaryTreeNode< T > * current )
{
cout << ' ' << current->getData();
}

/////////////////////////////////////////////////
// 恢复二叉树

template< class T >
void rebuildTree( string szInOrder, string szPostOrder, BinaryTreeNode< T > * curParent, int start, int end )
{
//szInOrder 为中序遍历，szPostOrder 为后序遍历
//curParent 为当前父结点
//start 为开始下标，end 为结束下标
if ( start > end )
return;
else {
//在中序遍历中找到当前根节点的位置
int pos = szInOrder.find( szPostOrder[end] );

//当前根节点若有左子树，则插入左子树
if ( pos > start )......余下全文>>