有哪些信誉好的足球投注网站- 1、本文档共8页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
后序-中序-二叉树还原对于这样一个二叉树
A
/ /
B C
/ / / /
D E F G
////////HIJKMNOP
后序遍历的结果是：HIDJKEBMNFOPGCA，我们称之为POST中序遍历的结果是：HDIBJEKAMFNCOGP，我们称之为MID还原的方法是：
(1)pi指向POST的最后一个字符(2)用pi从POST中取一个字符pc(3)查找pc在MID中出现的位置mi
(4)根据mi确定pc与前一个字符的关系(左孩子/右孩子/没有关系)(5)pi-1
(6)反复重复(2)~(5)步，直到pi0
可以看到，问题的关键在于步骤(4)，即如何确定pc与前一个字符的关系。在这里我们要用到两个辅助结构：
一个链表，存放Helper结构
一个Helper结构，用于记录每一个节点在MID中的下标链表我们可以用STL的list，Helper的结构如下
structHelper{TreeNode*node;int index;public:
Helper(TreeNode*pNode,intidx)
:node(pNode),index(idx){}
};
当然，二叉树的节点也要有：structTreeNode{
char data;
TreeNode*lChild;TreeNode*rChild;public:
TreeNode(charc):data(c),lChild(0),rChild(0){}
};
好了，我们一步一步来看看如何解决这个还原二叉树的问题(1)(A,7)
取POST第一个字符，然后通过Helper放入list中，并构造出一个list的初始环境
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
POST:H
I
D
J
K
E
B
M
N
F
O
P
G
C
A
MID: H
D
I
B
J
E
K
A
M
F
N
C
O
G
P
【list】
nod
0
A
0
idx
-1
7
15
cur
^
nxt
cur,nxt都是指向list中元素的指针，头尾两个元素表示边界(2)(C,11)
取POST第13个字符，根据list来判定它为谁的左孩子/右孩子
可以看到，pc=C，其在MID中的下标mi为11，简略为(C,11)，以后都这么简略
(C,11)在(A,7)右边，因为117，所以C为A的右孩子，并插入到list中，注意cur指针的变动。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
POST:H
I
D
J
K
E
B
M
N
F
O
P
G
C
A
MID: H
D
I
B
J
E
K
A
M
F
N
C
O
G
P
【list】
nod
0
A
C
0
idx
-1
7
11
15
cur
^
nxt
(3)(G,13)
(G,13)在(C,11)右边，因为1311，所以G是C的右孩子，插入list中
【list】
nod 0
A
C
G
0
idx-1
7
11
13
15
cur ^
nxt
下面省略，因为这个和我的另外一篇文章《前序-中序二叉树还原》很像，只不过一个从前往后
一个从后往前，还有一个先确定左孩子，一个先确定右孩子罢了
下面讲一下当A的右子树都还原好了，怎样还原B的情况。同时也讲解了如何还原左孩子的方法。
(12)(B,3)
这个时候链表应该是这样的
【list】
nod
0
A
M
0
idx
-1
7
8
15
cur
^
nxt
(B,3)不在(M,8)右边，nxt=cur,cur--
【list】
nod
0
A
M
0
idx
-1
7
8
15
cur
^
nxt
^
(B,3)不在(A,7),(M,8)中间，删除(M,8)
【list】
nod
0
A
0
idx
-1
7
15
cur
^
nxt
(13)(B,3)
此时(B,3)不在(A,7)右边，nxt=cur,cur--
【list】
nod
0
A
0
idx
-1
7
15
cur
^
nxt
^
(B,3)在(0,-1),(A,7)中间，因此B是A的左孩子，删除A，插入B，cur指向B
【list】
对了，千万不要忘记在确定X节点是Y节点的左/右孩子后要做相应的链接操作哦。下面给出算法的C++
对了，千万不要忘记在确定X节点是Y节点的左/右孩子后要做相应的链接操作哦。
下面给出算法的C++表示，这里我们用iterator
文档评论（0）