09年计算机考研统考试题第3题 数据结构 二叉树遍历的问题！

pz0513

试题我截成图片在附件。
遍历的结点序列为3，1，7，5，6，2，4，可这个序列我怎么看都不觉得是RNL啊，它右子树根本就没遍历完，如果是先遍历右子树，那3、5、6、7都要先于1遍历啊。这到底是怎么看的啊？各位大侠教教我啊！！

[ 本帖最后由 pz0513 于 2009-12-9 19:52 编辑 ]

_unistd_

应该是7、5、6、3、1、2、4吧，，题目的遍历方式没规律啊。。煞笔。。。

pz0513

原帖由 _unistd_ 于 2009-12-6 21:09 发表
应该是7、5、6、3、1、2、4吧，，题目的遍历方式没规律啊。。煞笔。。。

我觉得应该是3、7、5、6、1、2、4吧？

youshuang

用代码一试就看出来是RNL，不过不是书上说的那种简单的RNL。
这个要双堆栈，或者双重递归（两个递归函数）来实现。
人家考的就是思想。

1. 
   
2. #include <iostream>
   
3. #include <stack>
   
4. using namespace std;
   
5. class Node
   
6. {
   
7. public:
   
8.         int m_nNumber;
   
9.         Node* m_pLeft;
   
10.         Node* m_pRight;
    
11.         void AppendLeft( Node* pChild )
    
12.         {
    
13.                 m_pLeft = pChild;
    
14.         }
    
15.         void AppendRight( Node* pChild )
    
16.         {
    
17.                 m_pRight = pChild;
    
18.         }
    
19.         Node( int nNumber ) : m_nNumber( nNumber ){}
    
20. };
    
21. 
    
22. class Tree
    
23. {
    
24. public:
    
25.         Tree( Node* pRoot = NULL ) : m_pRoot( pRoot ){}
    
26.         void Traverse()
    
27.         {
    
28.                 stack< Node* > RootsHaveRight;
    
29.                 stack< Node* > Lefts;
    
30.                 Node* pTemp = m_pRoot;
    
31. 
    
32.                 while ( pTemp )
    
33.                 {
    
34.                         if ( pTemp->m_pRight )
    
35.                         {
    
36.                                 RootsHaveRight.push( pTemp );
    
37.                                 if ( pTemp->m_pLeft )
    
38.                                 {
    
39.                                         Lefts.push( pTemp->m_pLeft );
    
40.                                 }
    
41.                                 pTemp = pTemp->m_pRight;
    
42.                         }
    
43.                         else if ( ! pTemp->m_pRight && pTemp->m_pLeft )
    
44.                         {
    
45.                                 cout << pTemp->m_nNumber << " ";
    
46.                                 if ( ! RootsHaveRight.empty() )
    
47.                                 {
    
48.                                         cout << RootsHaveRight.top()->m_nNumber << " ";
    
49.                                         RootsHaveRight.pop();
    
50.                                 }
    
51.                                 pTemp = pTemp->m_pLeft;
    
52.                         }
    
53.                         else if ( ! pTemp->m_pLeft )
    
54.                         {
    
55.                                 cout << pTemp->m_nNumber << " ";
    
56.                                 if ( ! RootsHaveRight.empty() )
    
57.                                 {
    
58.                                         cout << RootsHaveRight.top()->m_nNumber << " ";
    
59.                                         RootsHaveRight.pop();
    
60.                                 }       
    
61.                                 if ( ! Lefts.empty() )
    
62.                                 {
    
63.                                         pTemp = Lefts.top();
    
64.                                         Lefts.pop();
    
65.                                 }
    
66.                                 else
    
67.                                 {
    
68.                                         cout << endl;
    
69.                                         return;
    
70.                                 }
    
71.                         }
    
72.                 }
    
73.                
    
74.         }
    
75.         void Output( const Node* pRoot ) const
    
76.         {
    
77.                 if ( pRoot )
    
78.                 {
    
79.                         cout << pRoot->m_nNumber << " ";
    
80.                         Output( pRoot->m_pLeft );
    
81.                         Output( pRoot->m_pRight );
    
82.                 }
    
83.         }
    
84.         friend ostream& operator<< ( ostream& rOut, const Tree& rTree )
    
85.         {
    
86.                 rTree.Output( rTree.m_pRoot );
    
87.                 return rOut;
    
88.         }
    
89. private:
    
90.         Node* m_pRoot;
    
91. };
    
92. 
    
93. int main()
    
94. {
    
95.         Node* pOne = new Node( 1 );
    
96.         Node* pTwo = new Node( 2 );
    
97.         Node* pThree = new Node( 3 );
    
98.         Node* pFour = new Node( 4 );
    
99.         Node* pFive = new Node( 5 );
    
100.         Node* pSix = new Node( 6 );
     
101.         Node* pSeven = new Node( 7 );
     
102.         pOne->AppendLeft( pTwo );
     
103.         pOne->AppendRight( pThree );
     
104.         pTwo->AppendLeft( pFour );
     
105.         pThree->AppendLeft( pFive );
     
106.         pFive->AppendLeft( pSix );
     
107.         pFive->AppendRight( pSeven );
     
108. 
     
109.         Tree NewTree( pOne );
     
110.         cout << NewTree << endl;
     
111.         NewTree.Traverse();
     
112.         // mem leak, ooo
     
113.         return 0;
     
114. }
     

复制代码

OwnWaterloo

呃…… 双堆栈……  双重递归……

求详细解释

youshuang

真的没啥意思，我瞎扯而已。
以后不瞎说了。。。

sunchiang

同问。啥叫“双堆栈或者双重递归”？什么样的逻辑只能用双重堆栈，递归实现？单一的为什么实现不了？

youshuang

说多了没用。
下面两个递推数列，让你用递归和非递归方式求a(n)，你会怎么写。

1. 
   
2. a(n) = b(n-1)+c(n-1)
   
3. b(n) = b(n-1)+b(n-2)
   
4. c(n) = c(n-1)+c(n-2)
   

复制代码

1. 
   
2. a(n) = a(n-1)+b(n-1)
   
3. b(n) = b(n-1)+b(n-2)
   

复制代码

至少用两个堆栈或者两个递归函数吧，哈哈哈哈。。。

OwnWaterloo

这个和二叉树遍历有什么关系吗？
恰好可以解释题目的答案？

pz0513

你仔细看看那道题，觉不觉得有错啊？一个选项都不是啊