重拾算法(3)——用458329个测试用例全面测试二叉树和线索二叉树的遍历算法
在""和""中，我给出了二叉树和线索二叉树的遍历算法。给出算法容易，证明算法的正确性就不容易了。本文就通过自动化测试的方式证明给出的遍历算法是完全正确的。458329个测试用例是深度为1到5的所有的树结构的形态，所以我才胆敢说是"全面"测试。
我的证明思路如下
只需对深度为1到5的所有形态的树结构分别进行测试即可
如果我的遍历算法对深度为1到5的所有形态的树结构都是正确的，那么我就确信这个算法是完全正确的。
测试一个二叉树T的方法：分别用递归算法（记为R）和非递归算法（记为NR）对其进行遍历，如果遍历顺序相同，就说明两个算法都是正确的。
实际上如果能够得到深度为1到5的树结构，自然也可以得到6、7、8...的，但是深度到5的时候，不同形态的树结构就有458329种了，得到的结果文件就有800M，再深一度我怕我可怜的PC就受不了了，所以深度就到5为止。
注：测试线索二叉树是用线索二叉树的遍历方法和一般二叉树的遍历方法（即刚刚的NR）进行对比测试的。一般二叉树的遍历方法我用的也是非递归的。
想办法得到所有深度为1、2、3、4、5的树结构，记为集合S
这个只能通过程序去计算获得，手工一个一个写是不现实的。后文将讲述如何计算。
对S中每一个树T：
按照前序遍历的顺序，对T中的结点依次编号0、1、2、3、4、...（按照中序、后序、层次遍历的顺序编号也可以，编号只是为了区分各个结点）
仿照DOS里的树结构的显示方式显示T的结构，举例如下：
按先序遍历对结点进行编号的某树
1 tree 577: 2 [0] 3 ├─[1] 4 │ ├─[2] 5 │ │ ├─null 6 │ │ └─null 7 │ └─[3] 8 │ ├─[4] 9 │ │ ├─null10 │ │ └─null11 │ └─[5]12 │ ├─null13 │ └─null14 └─[6]15 ├─[7]16 │ ├─[8]17 │ │ ├─null18 │ │ └─null19 │ └─null20 └─[9]21 ├─null22 └─[10]23 ├─null24 └─null
对树T依次进行前序、中序、后序遍历，每种遍历都使用非递归和递归两种方式进行，每种方式都按照遍历顺序输出结点编号，然后对比两种方式的输出结果是否相同（相同表示算法正确，否则表示算法错误）
记录所有出错的用例，用以发现算法的纰漏并修改。
我已经根据出错的情形进行分析，完善了算法，现在已经是0 error了。
得到所有深度为1到5的树结构
深度为1的树结构只有1个
1 tree 1:2 ([0])3 ├─null4 └─null
深度为2的树结构有3个
1 tree 2: 2 [0] 3 ├─[1] 4 │ ├─null 5 │ └─null 6 └─null 7 tree 3: 8 [0] 9 ├─null10 └─[1]11 ├─null12 └─null13 tree 4:14 [0]15 ├─[1]16 │ ├─null17 │ └─null18 └─[2]19 ├─null20 └─null
深度为3的树结构有21个
1 tree 5: 2 [0] 3 ├─[1] 4 │ ├─[2] 5 │ │ ├─null 6 │ │ └─null 7 │ └─null 8 └─null 9 tree 6: 10 [0] 11 ├─[1] 12 │ ├─null 13 │ └─[2] 14 │ ├─null 15 │ └─null 16 └─null 17 tree 7: 18 [0] 19 ├─[1] 20 │ ├─[2] 21 │ │ ├─null 22 │ │ └─null 23 │ └─[3] 24 │ ├─null 25 │ └─null 26 └─null 27 tree 8: 28 [0] 29 ├─null 30 └─[1] 31 ├─[2] 32 │ ├─null 33 │ └─null 34 └─null 35 tree 9: 36 [0] 37 ├─null 38 └─[1] 39 ├─null 40 └─[2] 41 ├─null 42 └─null 43 tree 10: 44 [0] 45 ├─null 46 └─[1] 47 ├─[2] 48 │ ├─null 49 │ └─null 50 └─[3] 51 ├─null 52 └─null 53 tree 11: 54 [0] 55 ├─[1] 56 │ ├─[2] 57 │ │ ├─null 58 │ │ └─null 59 │ └─null 60 └─[3] 61 ├─null 62 └─null 63 tree 12: 64 [0] 65 ├─[1] 66 │ ├─null 67 │ └─[2] 68 │ ├─null 69 │ └─null 70 └─[3] 71 ├─null 72 └─null 73 tree 13: 74 [0] 75 ├─[1] 76 │ ├─[2] 77 │ │ ├─null 78 │ │ └─null 79 │ └─[3] 80 │ ├─null 81 │ └─null 82 └─[4] 83 ├─null 84 └─null 85 tree 14: 86 [0] 87 ├─[1] 88 │ ├─null 89 │ └─null 90 └─[2] 91 ├─[3] 92 │ ├─null 93 │ └─null 94 └─null 95 tree 15: 96 [0] 97 ├─[1] 98 │ ├─[2] 99 │ │ ├─null100 │ │ └─null101 │ └─null102 └─[3]103 ├─[4]104 │ ├─null105 │ └─null106 └─null107 tree 16:108 [0]109 ├─[1]110 │ ├─null111 │ └─[2]112 │ ├─null113 │ └─null114 └─[3]115 ├─[4]116 │ ├─null117 │ └─null118 └─null119 tree 17:120 [0]121 ├─[1]122 │ ├─[2]123 │ │ ├─null124 │ │ └─null125 │ └─[3]126 │ ├─null127 │ └─null128 └─[4]129 ├─[5]130 │ ├─null131 │ └─null132 └─null133 tree 18:134 [0]135 ├─[1]136 │ ├─null137 │ └─null138 └─[2]139 ├─null140 └─[3]141 ├─null142 └─null143 tree 19:144 [0]145 ├─[1]146 │ ├─[2]147 │ │ ├─null148 │ │ └─null149 │ └─null150 └─[3]151 ├─null152 └─[4]153 ├─null154 └─null155 tree 20:156 [0]157 ├─[1]158 │ ├─null159 │ └─[2]160 │ ├─null161 │ └─null162 └─[3]163 ├─null164 └─[4]165 ├─null166 └─null167 tree 21:168 [0]169 ├─[1]170 │ ├─[2]171 │ │ ├─null172 │ │ └─null173 │ └─[3]174 │ ├─null175 │ └─null176 └─[4]177 ├─null178 └─[5]179 ├─null180 └─null181 tree 22:182 [0]183 ├─[1]184 │ ├─null185 │ └─null186 └─[2]187 ├─[3]188 │ ├─null189 │ └─null190 └─[4]191 ├─null192 └─null193 tree 23:194 [0]195 ├─[1]196 │ ├─[2]197 │ │ ├─null198 │ │ └─null199 │ └─null200 └─[3]201 ├─[4]202 │ ├─null203 │ └─null204 └─[5]205 ├─null206 └─null207 tree 24:208 [0]209 ├─[1]210 │ ├─null211 │ └─[2]212 │ ├─null213 │ └─null214 └─[3]215 ├─[4]216 │ ├─null217 │ └─null218 └─[5]219 ├─null220 └─null221 tree 25:222 [0]223 ├─[1]224 │ ├─[2]225 │ │ ├─null226 │ │ └─null227 │ └─[3]228 │ ├─null229 │ └─null230 └─[4]231 ├─[5]232 │ ├─null233 │ └─null234 └─[6]235 ├─null236 └─null
深度为4的树结构有651个，深度为5的树结构有457653个，这就太多了，此处不能一一列举。
规律
通过深度为1、2、3的树结构，可以找到一些重要的规律。
深度为2的树结构（记为T2-1、T2-2、T2-3），可以由深度为1的树结构（记为T1-1）按如下规则进化而来：
T1-1有1个结点，这个结点一共有2*1个为null的Left/Right，只要分别给他们连上1个或0个新结点，就成了T2中的某一个（2^(2*1)-1=3）；而所有这种连法就恰好得到了所有的T2的情况（即3）。
为什么要"-1"呢？因为如果两个为null的Left/Right都不连新结点，就仍然为T1-1，就是没有真正进化，所以要去掉这种情况。
再进一步看一下。
深度为3的树结构（记为T3-1、T3-2、T3-3、...），可以由深度为2的树结构（T2-1、T2-2、T2-3）按如下规则进化而来：
T2-1的深度最大的结点有1个，这些深度最大的结点一共有2*1个为null的Left/Right，只要分别给他们连上1个或0个新结点，就成了T2中的某一个（2^(2*1)-1=3）。
T2-2的深度最大的结点有1个，这些深度最大的结点一共有2*1个为null的Left/Right，只要分别给他们连上1个或0个新结点，就成了T2中的某一个（2^(2*1)-1=3）。
T2-3的深度最大的结点有2个，这些深度最大的结点一共有2*2个为null的Left/Right，只要分别给他们连上1个或0个新结点，就成了T2中的某一个（2^(2*2)-1=15）。
同上的原因，我们要记得"-1"。
而所有这种连法就恰好得到了所有的T3的情况（3+3+15=21种情况）。
好了，现在获取所有深度为1、2、3、4、5的树结构的方法已经很明显了。深度为N的树结构要通过深度为N-1的树结构进化得到。
写代码之前，还要考虑一个小问题，深度为1到5的树结构有458329个，如果一次性获取458329个树结构（我一开始就是这么办的），我的PC内存就受不了了，卡的要死要活的。所以我改进一下，每得到一个新的树结构，就立即对其进行测试；如果这个树结构的深度为maxDepth，测试之后就将其丢弃，静待.NET将其空间回收。这样效果就好多了，深度为5都没有卡顿。
测试线索二叉树的代码
下面是测试线索二叉树的代码。测试普通的二叉树代码和这个原理是一样的。
首先是测试一个树结构
1 static bool TestNode(ThreadedBinaryTreeNodenode, int index) 2 { 3 var arranger = new IntArranger (); 4 node.Traverse(TraverseOrder.Preorder, arranger);//给各个树结点编号 5 Console.WriteLine("--------------------------------------------------------------------------------"); 6 Console.WriteLine("tree {0}:", index); 7 Console.WriteLine(node.ToTree());//打印树结构 8 var result = true; 9 foreach (var order in Enum.GetNames(typeof(TraverseOrder)))//分别用前序中序后序层次的遍历方式进行测试10 {11 Console.WriteLine(order + ":");12 var o = (TraverseOrder)Enum.Parse(typeof(TraverseOrder), order);13 var nonRecursiveOutput = string.Empty;14 {15 var printer = new Printer ();16 node.Traverse(o, printer);//用线索二叉树的遍历方式测试17 nonRecursiveOutput = printer.ToString();//获取结点的遍历顺序18 }19 var recursiveOutput = string.Empty;20 { 21 var printer = new Printer ();22 node.NormalTraverse(o, printer);//用一般二叉树的遍历方式测试23 recursiveOutput = printer.ToString();//获取结点的遍历顺序24 }25 if (nonRecursiveOutput != recursiveOutput)//对比两种方法得到的结果是否相同26 {27 Console.WriteLine("Error: different output from traverse and recursive traverse!");28 Console.WriteLine(" traverse:");29 Console.WriteLine(nonRecursiveOutput);30 Console.WriteLine(" recursive traverse:");31 Console.WriteLine(recursiveOutput);32 result = false;//测试结果failed，标记一下，以供统计33 }34 else35 {36 Console.WriteLine(nonRecursiveOutput);37 }38 39 }40 return result;41 }
然后是生成和测试所有深度为1到maxDepth的树结构
1 public static void Test(int maxDepth) 2 { 3 Console.WriteLine("Testing ThreadedBinaryTreeNode .Traverse()"); 4 5 if (maxDepth <= 0) { return; } 6 7 var firstNode = new ThreadedBinaryTreeNode (); 8 var queue = new Queue >(); 9 queue.Enqueue(firstNode);10 var errorCount = 0;11 var testCaseIndex = 1;12 var successful = TestNode(firstNode, testCaseIndex++);//测试深度为1的树结构13 if (!successful) { errorCount++; }14 15 if (maxDepth > 1)16 {17 while (queue.Count > 0)//由深度为N的树结构进化出深度为N+1的树结构18 {19 var node = queue.Dequeue();//获取下一个要进行进化的树结构的根节点node20 21 var recorder = new DeepestLeaveRecorder ();22 node.Traverse(TraverseOrder.Layer, recorder);//获取此树结构所有深度为最深的结点23 var deepestLeavesCount = recorder.DeepestLeaves.Count;24 var booleanList = new List ();//booleanList充当是否连上新结点的标记，true为连，false为不连。25 for (var i = 0; i < deepestLeavesCount * 2; i++)26 {27 booleanList.Add(false);//booleanList相当于一个二进制数28 }29 var derivedNodesCount = Math.Pow(2, deepestLeavesCount * 2) - 1;//node有这么多种进化方式30 for (var i = 0; i < derivedNodesCount; i++)31 {32 IncreaseBooleanList(booleanList);//对booleanList进行“加1”操作，以获取下一个进化方式33 var newNode = node.Clone() as ThreadedBinaryTreeNode ;34 var r = new DeepestLeaveRecorder ();35 newNode.Traverse(TraverseOrder.Layer, r);//获取待进化的树结构所有深度为最深的结点36 var index = 0;37 foreach (var leave in r.DeepestLeaves)38 {39 if (booleanList[index * 2])//对leave这一结点的Left进行连接40 {41 var n = new ThreadedBinaryTreeNode ();42 leave.Point2PreviousNode = false; leave.Left = n;43 n.Parent = leave;44 }45 if (booleanList[index * 2 + 1])//对leave这一结点的Right进行连接46 {47 var n = new ThreadedBinaryTreeNode ();48 leave.Point2NextNode = false; leave.Right = n;49 n.Parent = leave;50 }51 index++;52 }53 var depth = newNode.GetDepth();54 if (depth < maxDepth)//深度不足maxDepth，说明此newNode还应该进化，因此入队待用55 {56 queue.Enqueue(newNode);57 }58 successful = TestNode(newNode, testCaseIndex++);//测试newNode59 if (!successful) { errorCount++; }60 }61 }62 }63 Console.WriteLine("--------------------------------------------------------------------------------");64 Console.WriteLine("{0} error(s) occured.", errorCount); 65 } 下面是一些辅助用的代码。
遍历时对每个结点node依次调用DoActionOnNode方法。
1 public abstract class ThreadedNodeWorker2 {3 public abstract void DoActionOnNode(ThreadedBinaryTreeNode node);4 }
对树节点进行编号
1 class IntArranger: ThreadedNodeWorker 2 {3 int index = 0;4 public override void DoActionOnNode(ThreadedBinaryTreeNode node)5 {6 node.Id = index;7 index++;8 }9 }
获取树结构的遍历顺序
1 class Printer: ThreadedNodeWorker 2 { 3 public override String ToString() 4 { 5 return builder.ToString(); 6 } 7 StringBuilder builder = new StringBuilder(); 8 public override void DoActionOnNode(ThreadedBinaryTreeNode node) 9 {10 var strNode = node.ToString();11 builder.Append(strNode);12 }13 }
获取树结构所有深度为最深的结点
1 class DeepestLeaveRecorder : ThreadedNodeWorker 2 { 3 List > deepestLeaves = new List >(); 4 public IList > DeepestLeaves 5 { get { return this.deepestLeaves; } } 6 Dictionary , int> nodeDepthDict = new Dictionary , int>(); 7 int deepestDeep = 0; 8 public override void DoActionOnNode(ThreadedBinaryTreeNode node) 9 {10 if (node == null) { return; }11 if (nodeDepthDict.ContainsKey(node)) { return; }12 var depthOfNode = GetDepthOfNode(node);13 nodeDepthDict.Add(node, depthOfNode);14 if (deepestDeep == depthOfNode)15 {16 deepestLeaves.Add(node);17 }18 else if (deepestDeep < depthOfNode)19 {20 deepestLeaves.Clear();21 deepestLeaves.Add(node);22 deepestDeep = depthOfNode;23 }24 }25 26 int GetDepthOfNode(ThreadedBinaryTreeNode node)27 {28 if (node == null) { return 0; }29 var result = 1;30 while (node.Parent != null)31 {32 result++;33 node = node.Parent;34 }35 return result;36 }37 } 生成类DOS的树结构视图的代码
1 public partial class ThreadedBinaryTreeNode2 { 3 public String ToTree() 4 { 5 var builder = new StringBuilder(); 6 int tabSpace = 0; 7 GetBuilder(builder, this, ref tabSpace); 8 return builder.ToString(); 9 }10 11 private void GetBuilder(StringBuilder builder, ThreadedBinaryTreeNode node, ref int tabSpace, bool placeHolder = false, ThreadedBinaryTreeNode parent = null, bool left = false)12 {13 if (placeHolder)14 {15 builder.Append(GetPremarks(null, placeHolder, parent, left));16 builder.AppendLine("null");17 }18 else19 {20 if (node == null) { return; }21 builder.Append(GetPremarks(node));22 builder.AppendLine(node.ToString());23 24 tabSpace++;25 26 if ((node.Left != null) && (!node.Point2PreviousNode)) { GetBuilder(builder, node.Left, ref tabSpace); }27 else { GetBuilder(builder, null, ref tabSpace, true, node, true); }28 29 if ((node.Right != null) && (!node.Point2NextNode)) { GetBuilder(builder, node.Right, ref tabSpace); }30 else { GetBuilder(builder, null, ref tabSpace, true, node, false); }31 32 tabSpace--;33 }34 }35 36 private string GetPremarks(ThreadedBinaryTreeNode node, bool placeHolder = false, ThreadedBinaryTreeNode parent = null, bool left = false)37 {38 ThreadedBinaryTreeNode originalParent;39 if (placeHolder)40 { originalParent = parent; }41 else42 { originalParent = node.Parent; }43 44 var ptrParent = originalParent;45 if (ptrParent == null) return string.Empty;46 var lstLine = new List ();47 while (ptrParent != null)48 {49 var pp = ptrParent.Parent;50 if (pp != null)51 {52 lstLine.Add((pp.Left == ptrParent));// && (pp.Right != null));53 }54 ptrParent = pp;55 }56 var builder = new StringBuilder();57 for (var i = lstLine.Count - 1; i >=0; i--)58 {59 if (lstLine[i]) { builder.Append(" │ "); }60 else { builder.Append(" "); }61 }62 if (placeHolder)63 {64 if (left) { builder.Append(" ├─"); }65 else { builder.Append(" └─"); }66 }67 else68 {69 ptrParent = originalParent;70 if ((ptrParent.Left == node))// && (ptrParent.Right != null))71 { builder.Append(" ├─"); }72 else { builder.Append(" └─"); }73 }74 75 return builder.ToString();76 }77 }
总结
我已经根据出错的用例完善了算法，现已成功通过所有458329个测试用例。
下面给出maxDepth为3时的输出结果：
1 Testing ThreadedBinaryTreeNode.Traverse() 2 -------------------------------------------------------------------------------- 3 tree 1: 4 ([0]) 5 ├─null 6 └─null 7 8 Preorder: 9 ([0]) 10 Inorder: 11 ([0]) 12 Postorder: 13 ([0]) 14 Layer: 15 ([0]) 16 -------------------------------------------------------------------------------- 17 tree 2: 18 ([0]→1) 19 ├─(0←[1]) 20 │ ├─null 21 │ └─null 22 └─null 23 24 Preorder: 25 ([0]→1)(0←[1]) 26 Inorder: 27 ([1]→0)([0]) 28 Postorder: 29 ([1]→0)([0]) 30 Layer: 31 ([0]→1)(0←[1]) 32 -------------------------------------------------------------------------------- 33 tree 3: 34 ([0]) 35 ├─null 36 └─(0←[1]) 37 ├─null 38 └─null 39 40 Preorder: 41 ([0])(0←[1]) 42 Inorder: 43 ([0])(0←[1]) 44 Postorder: 45 ([1]→0)(1←[0]) 46 Layer: 47 ([0])(0←[1]) 48 -------------------------------------------------------------------------------- 49 tree 4: 50 ([0]) 51 ├─(0←[1]→2) 52 │ ├─null 53 │ └─null 54 └─(1←[2]) 55 ├─null 56 └─null 57 58 Preorder: 59 ([0])(0←[1]→2)(1←[2]) 60 Inorder: 61 ([1]→0)([0])(0←[2]) 62 Postorder: 63 ([1]→2)(1←[2]→0)([0]) 64 Layer: 65 ([0])(0←[1]→2)(1←[2]) 66 -------------------------------------------------------------------------------- 67 tree 5: 68 ([0]→1) 69 ├─([1]→2) 70 │ ├─(1←[2]) 71 │ │ ├─null 72 │ │ └─null 73 │ └─null 74 └─null 75 76 Preorder: 77 ([0]→1)([1]→2)(1←[2]) 78 Inorder: 79 ([2]→1)([1]→0)([0]) 80 Postorder: 81 ([2]→1)([1]→0)([0]) 82 Layer: 83 ([0]→1)([1]→2)(1←[2]) 84 -------------------------------------------------------------------------------- 85 tree 6: 86 ([0]→1) 87 ├─(0←[1]) 88 │ ├─null 89 │ └─(1←[2]) 90 │ ├─null 91 │ └─null 92 └─null 93 94 Preorder: 95 ([0]→1)(0←[1])(1←[2]) 96 Inorder: 97 ([1])(1←[2]→0)([0]) 98 Postorder: 99 ([2]→1)(2←[1])([0])100 Layer:101 ([0]→1)(0←[1])(1←[2])102 --------------------------------------------------------------------------------103 tree 7:104 ([0]→1)105 ├─([1])106 │ ├─(1←[2]→3)107 │ │ ├─null108 │ │ └─null109 │ └─(2←[3])110 │ ├─null111 │ └─null112 └─null113 114 Preorder:115 ([0]→1)([1])(1←[2]→3)(2←[3])116 Inorder:117 ([2]→1)([1])(1←[3]→0)([0])118 Postorder:119 ([2]→3)(2←[3]→1)([1])([0])120 Layer:121 ([0]→1)([1])(1←[2]→3)(2←[3])122 --------------------------------------------------------------------------------123 tree 8:124 ([0])125 ├─null126 └─([1]→2)127 ├─(1←[2])128 │ ├─null129 │ └─null130 └─null131 132 Preorder:133 ([0])([1]→2)(1←[2])134 Inorder:135 ([0])(0←[2]→1)([1])136 Postorder:137 ([2]→1)([1]→0)(1←[0])138 Layer:139 ([0])([1]→2)(1←[2])140 --------------------------------------------------------------------------------141 tree 9:142 ([0])143 ├─null144 └─(0←[1])145 ├─null146 └─(1←[2])147 ├─null148 └─null149 150 Preorder:151 ([0])(0←[1])(1←[2])152 Inorder:153 ([0])(0←[1])(1←[2])154 Postorder:155 ([2]→1)(2←[1])(1←[0])156 Layer:157 ([0])(0←[1])(1←[2])158 --------------------------------------------------------------------------------159 tree 10:160 ([0])161 ├─null162 └─([1])163 ├─(1←[2]→3)164 │ ├─null165 │ └─null166 └─(2←[3])167 ├─null168 └─null169 170 Preorder:171 ([0])([1])(1←[2]→3)(2←[3])172 Inorder:173 ([0])(0←[2]→1)([1])(1←[3])174 Postorder:175 ([2]→3)(2←[3]→1)([1])(1←[0])176 Layer:177 ([0])([1])(1←[2]→3)(2←[3])178 --------------------------------------------------------------------------------179 tree 11:180 ([0])181 ├─([1]→2)182 │ ├─(1←[2]→3)183 │ │ ├─null184 │ │ └─null185 │ └─null186 └─(2←[3])187 ├─null188 └─null189 190 Preorder:191 ([0])([1]→2)(1←[2]→3)(2←[3])192 Inorder:193 ([2]→1)([1]→0)([0])(0←[3])194 Postorder:195 ([2]→1)([1]→3)(1←[3]→0)([0])196 Layer:197 ([0])([1]→3)(1←[3]→2)(3←[2])198 --------------------------------------------------------------------------------199 tree 12:200 ([0])201 ├─(0←[1])202 │ ├─null203 │ └─(1←[2]→3)204 │ ├─null205 │ └─null206 └─(2←[3])207 ├─null208 └─null209 210 Preorder:211 ([0])(0←[1])(1←[2]→3)(2←[3])212 Inorder:213 ([1])(1←[2]→0)([0])(0←[3])214 Postorder:215 ([2]→1)(2←[1])(1←[3]→0)([0])216 Layer:217 ([0])(0←[1])(1←[3]→2)(3←[2])218 --------------------------------------------------------------------------------219 tree 13:220 ([0])221 ├─([1])222 │ ├─(1←[2]→3)223 │ │ ├─null224 │ │ └─null225 │ └─(2←[3]→4)226 │ ├─null227 │ └─null228 └─(3←[4])229 ├─null230 └─null231 232 Preorder:233 ([0])([1])(1←[2]→3)(2←[3]→4)(3←[4])234 Inorder:235 ([2]→1)([1])(1←[3]→0)([0])(0←[4])236 Postorder:237 ([2]→3)(2←[3]→1)([1])(1←[4]→0)([0])238 Layer:239 ([0])([1])(1←[4]→2)(4←[2]→3)(2←[3])240 --------------------------------------------------------------------------------241 tree 14:242 ([0])243 ├─(0←[1]→2)244 │ ├─null245 │ └─null246 └─([2]→3)247 ├─(2←[3])248 │ ├─null249 │ └─null250 └─null251 252 Preorder:253 ([0])(0←[1]→2)([2]→3)(2←[3])254 Inorder:255 ([1]→0)([0])(0←[3]→2)([2])256 Postorder:257 ([1]→3)(1←[3]→2)([2]→0)([0])258 Layer:259 ([0])(0←[1]→2)([2]→3)(2←[3])260 --------------------------------------------------------------------------------261 tree 15:262 ([0])263 ├─([1]→2)264 │ ├─(1←[2]→3)265 │ │ ├─null266 │ │ └─null267 │ └─null268 └─([3]→4)269 ├─(3←[4])270 │ ├─null271 │ └─null272 └─null273 274 Preorder:275 ([0])([1]→2)(1←[2]→3)([3]→4)(3←[4])276 Inorder:277 ([2]→1)([1]→0)([0])(0←[4]→3)([3])278 Postorder:279 ([2]→1)([1]→4)(1←[4]→3)([3]→0)([0])280 Layer:281 ([0])([1]→3)([3]→2)(3←[2]→4)(2←[4])282 --------------------------------------------------------------------------------283 tree 16:284 ([0])285 ├─(0←[1])286 │ ├─null287 │ └─(1←[2]→3)288 │ ├─null289 │ └─null290 └─([3]→4)291 ├─(3←[4])292 │ ├─null293 │ └─null294 └─null295 296 Preorder:297 ([0])(0←[1])(1←[2]→3)([3]→4)(3←[4])298 Inorder:299 ([1])(1←[2]→0)([0])(0←[4]→3)([3])300 Postorder:301 ([2]→1)(2←[1])(1←[4]→3)([3]→0)([0])302 Layer:303 ([0])(0←[1])([3]→2)(3←[2]→4)(2←[4])304 --------------------------------------------------------------------------------305 tree 17:306 ([0])307 ├─([1])308 │ ├─(1←[2]→3)309 │ │ ├─null310 │ │ └─null311 │ └─(2←[3]→4)312 │ ├─null313 │ └─null314 └─([4]→5)315 ├─(4←[5])316 │ ├─null317 │ └─null318 └─null319 320 Preorder:321 ([0])([1])(1←[2]→3)(2←[3]→4)([4]→5)(4←[5])322 Inorder:323 ([2]→1)([1])(1←[3]→0)([0])(0←[5]→4)([4])324 Postorder:325 ([2]→3)(2←[3]→1)([1])(1←[5]→4)([4]→0)([0])326 Layer:327 ([0])([1])([4]→2)(4←[2]→3)(2←[3]→5)(3←[5])328 --------------------------------------------------------------------------------329 tree 18:330 ([0])331 ├─(0←[1]→2)332 │ ├─null333 │ └─null334 └─(1←[2])335 ├─null336 └─(2←[3])337 ├─null338 └─null339 340 Preorder:341 ([0])(0←[1]→2)(1←[2])(2←[3])342 Inorder:343 ([1]→0)([0])(0←[2])(2←[3])344 Postorder:345 ([1]→3)(1←[3]→2)(3←[2])([0])346 Layer:347 ([0])(0←[1]→2)(1←[2])(2←[3])348 --------------------------------------------------------------------------------349 tree 19:350 ([0])351 ├─([1]→2)352 │ ├─(1←[2]→3)353 │ │ ├─null354 │ │ └─null355 │ └─null356 └─(2←[3])357 ├─null358 └─(3←[4])359 ├─null360 └─null361 362 Preorder:363 ([0])([1]→2)(1←[2]→3)(2←[3])(3←[4])364 Inorder:365 ([2]→1)([1]→0)([0])(0←[3])(3←[4])366 Postorder:367 ([2]→1)([1]→4)(1←[4]→3)(4←[3])([0])368 Layer:369 ([0])([1]→3)(1←[3])(3←[2]→4)(2←[4])370 --------------------------------------------------------------------------------371 tree 20:372 ([0])373 ├─(0←[1])374 │ ├─null375 │ └─(1←[2]→3)376 │ ├─null377 │ └─null378 └─(2←[3])379 ├─null380 └─(3←[4])381 ├─null382 └─null383 384 Preorder:385 ([0])(0←[1])(1←[2]→3)(2←[3])(3←[4])386 Inorder:387 ([1])(1←[2]→0)([0])(0←[3])(3←[4])388 Postorder:389 ([2]→1)(2←[1])(1←[4]→3)(4←[3])([0])390 Layer:391 ([0])(0←[1])(1←[3])(3←[2]→4)(2←[4])392 --------------------------------------------------------------------------------393 tree 21:394 ([0])395 ├─([1])396 │ ├─(1←[2]→3)397 │ │ ├─null398 │ │ └─null399 │ └─(2←[3]→4)400 │ ├─null401 │ └─null402 └─(3←[4])403 ├─null404 └─(4←[5])405 ├─null406 └─null407 408 Preorder:409 ([0])([1])(1←[2]→3)(2←[3]→4)(3←[4])(4←[5])410 Inorder:411 ([2]→1)([1])(1←[3]→0)([0])(0←[4])(4←[5])412 Postorder:413 ([2]→3)(2←[3]→1)([1])(1←[5]→4)(5←[4])([0])414 Layer:415 ([0])([1])(1←[4])(4←[2]→3)(2←[3]→5)(3←[5])416 --------------------------------------------------------------------------------417 tree 22:418 ([0])419 ├─(0←[1]→2)420 │ ├─null421 │ └─null422 └─([2])423 ├─(2←[3]→4)424 │ ├─null425 │ └─null426 └─(3←[4])427 ├─null428 └─null429 430 Preorder:431 ([0])(0←[1]→2)([2])(2←[3]→4)(3←[4])432 Inorder:433 ([1]→0)([0])(0←[3]→2)([2])(2←[4])434 Postorder:435 ([1]→3)(1←[3]→4)(3←[4]→2)([2])([0])436 Layer:437 ([0])(0←[1]→2)([2])(2←[3]→4)(3←[4])438 --------------------------------------------------------------------------------439 tree 23:440 ([0])441 ├─([1]→2)442 │ ├─(1←[2]→3)443 │ │ ├─null444 │ │ └─null445 │ └─null446 └─([3])447 ├─(3←[4]→5)448 │ ├─null449 │ └─null450 └─(4←[5])451 ├─null452 └─null453 454 Preorder:455 ([0])([1]→2)(1←[2]→3)([3])(3←[4]→5)(4←[5])456 Inorder:457 ([2]→1)([1]→0)([0])(0←[4]→3)([3])(3←[5])458 Postorder:459 ([2]→1)([1]→4)(1←[4]→5)(4←[5]→3)([3])([0])460 Layer:461 ([0])([1]→3)([3])(3←[2]→4)(2←[4]→5)(4←[5])462 --------------------------------------------------------------------------------463 tree 24:464 ([0])465 ├─(0←[1])466 │ ├─null467 │ └─(1←[2]→3)468 │ ├─null469 │ └─null470 └─([3])471 ├─(3←[4]→5)472 │ ├─null473 │ └─null474 └─(4←[5])475 ├─null476 └─null477 478 Preorder:479 ([0])(0←[1])(1←[2]→3)([3])(3←[4]→5)(4←[5])480 Inorder:481 ([1])(1←[2]→0)([0])(0←[4]→3)([3])(3←[5])482 Postorder:483 ([2]→1)(2←[1])(1←[4]→5)(4←[5]→3)([3])([0])484 Layer:485 ([0])(0←[1])([3])(3←[2]→4)(2←[4]→5)(4←[5])486 --------------------------------------------------------------------------------487 tree 25:488 ([0])489 ├─([1])490 │ ├─(1←[2]→3)491 │ │ ├─null492 │ │ └─null493 │ └─(2←[3]→4)494 │ ├─null495 │ └─null496 └─([4])497 ├─(4←[5]→6)498 │ ├─null499 │ └─null500 └─(5←[6])501 ├─null502 └─null503 504 Preorder:505 ([0])([1])(1←[2]→3)(2←[3]→4)([4])(4←[5]→6)(5←[6])506 Inorder:507 ([2]→1)([1])(1←[3]→0)([0])(0←[5]→4)([4])(4←[6])508 Postorder:509 ([2]→3)(2←[3]→1)([1])(1←[5]→6)(5←[6]→4)([4])([0])510 Layer:511 ([0])([1])([4])(4←[2]→3)(2←[3]→5)(3←[5]→6)(5←[6])512 --------------------------------------------------------------------------------513 0 error(s) occured.
现在我可以放心大胆地说，我给出的二叉树和线索二叉树的遍历算法是真正正确的！
需要工程源码的同学麻烦点个赞并留言你的Email~