学习使用，先用二叉树后序遍历写了个 斐波那契数的例子，后台陆续更新更好的算法，最新在学《算法导论》，开始有点困难，不过不急，慢慢来。。。一天，一周，一个月一个算法，弄明白了，比什么都强！！

这段代码没有解释，不久会更新，先看着代码哈

3. using System;
4. using System.Collections.Generic;
5. using System.Linq;
6. using System.Text;
7.  
8. namespace TEST
9. {
10.     class Program
11.     {
12.         static void Main(string[] args)
13.         {
14.             Console.Write(GetFoo(10));
15.  
16.             Console.Read();
17.         }
18.         //
19.         static long GetFoo(int n)
20.         {
21.             if (IsLeaf(n))
22.             {
23.                 return GetLeafvalue(n);
24.             }
25.             //结果保存栈
26.             Stack<long[]> resultStack = new Stack<long[]>();
27.  
28.             //临时结果数组
29.             long[] tempResultArry = InitTempResultArry();
30.  
31.             //压入临时结果数组
32.             resultStack.Push(tempResultArry);
33.  
34.             //临时节点栈
35.             Stack<int> tempNodeStack = new Stack<int>();
36.  
37.             //压入根节点
38.             tempNodeStack.Push(n);
39.  
40.             //遍历临时节点
41.             while (tempNodeStack.Count > 0)
42.             {
43.                 tempResultArry = resultStack.Last();
44.                 int branchIndex = GetNodeBranchIndex(tempResultArry);
45.  
46.                 //当前节点遍历完成
47.                 if (branchIndex == -1)
48.                 {
49.                     if (resultStack.Count == 1)
50.                     {
51.                         break;
52.                     }
53.                     else
54.                     {
55.                         tempNodeStack.Pop();
56.                         resultStack.Pop();
57.                         
    
58.                         //把结果赋值给上层
59.                         //tempResultArry = resultStack.Last();
60.  
61.                         long tempResult = CalculateResult(tempResultArry);
62.                         tempResultArry[1] = tempResultArry[0];
63.                         tempResultArry[0] = tempResult;
64.                     }
65.                 }
66.                 else
67.                 {
68.                     //没完成，得到要遍历的下一个节点
69.                     int currentNode = tempNodeStack.First();
70.                     int nextNode = GetSubNode(currentNode, branchIndex);
71.  
72.                     if (IsLeaf(nextNode))
73.                     {
74.                         tempResultArry[branchIndex] = GetLeafvalue(nextNode);
75.                     }
76.                     else
77.                     {
78.                         tempNodeStack.Push(nextNode);
79.                         resultStack.Push(InitTempResultArry());
80.                     }
81.  
82.                 }
83.  
84.  
85.             }
86.             return CalculateResult(resultStack.First());
87.         }
88.  
89.         //
90.         static bool IsLeaf(int n)
91.         {
92.             return n < 3;
93.         }
94.         //
95.         static int GetNodeBranchIndex(long[] tempNodeResultArry)
96.         {
97.             for (int i = 0; i < tempNodeResultArry.Length; i++)
98.             {
99.                 if (tempNodeResultArry[i] == -1)
100.                 {
101.                     return i;
102.                 }
103.             }
104.             return -1;//表示没有遍历完成
105.         }
106.  
107.         //
108.         static int GetSubNode(int node, int branchIndex)
109.         {
110.             return node - branchIndex - 1;
111.         }
112.         //
113.         static long GetLeafvalue(int n)
114.         {
115.             return 1;
116.         }
117.         //
118.         static long[] InitTempResultArry()
119.         {
120.             long[] tempResultArry = new long[2];
121.             for (int i = 0; i < 2; i++)
122.             {
123.                 tempResultArry[i] = -1;
124.             }
125.             return tempResultArry;
126.         }
127.  
128.         static long CalculateResult(long[] tmpResults)
129.         {
130.             long retValue = 0;
131.             for (int i = 0; i < 2; i++)
132.             {
133.                 retValue += tmpResults[i];
134.             }
135.             return retValue;
136.         }
137.  
138.     }
139. }

用栈实现递归算法（第一版） - 龙歌网络 - 博客园.