PHP实现二叉树、线索二叉树，如下代码：
<ol class="dp-c">
<li class="alt"><span><span><?php </span></span></span></li>
<li><span> <span class="keyword">require</span><span> </span><span class="string">'biTree.php'</span><span>; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="vars">$str</span><span> = </span><span class="string">'ko#be8#tr####acy#####'</span><span>; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="vars">$tree</span><span> = </span><span class="keyword">new</span><span> BiTree(</span><span class="vars">$str</span><span>); </span></span></li>
<li class="alt"><span> <span class="vars">$tree</span><span>->createThreadTree(); </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="func">echo</span><span> </span><span class="vars">$tree</span><span>->threadList() . </span><span class="string">"\n"</span><span>;从第一个结点开始遍历线索二叉树 </span></span></li>
<li><span> <span class="func">echo</span><span> </span><span class="vars">$tree</span><span>->threadListReserv();从最后一个结点开始反向遍历 </span></span></li>
<li class="alt"><span>?> </span></li>
<li><span><span class="comment">//biTree.php</span><span> </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//结点类</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">class</span><span> Node{ </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$data</span><span> = NULL; </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="vars">$left</span><span> = NULL; </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$right</span><span> = NULL; </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="vars">$lTag</span><span> = 0; </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$rTag</span><span> = 0; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> Node(</span><span class="vars">$data</span><span> = false){ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->data = </span><span class="vars">$data</span><span>; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//我不喜欢使用魔术方法 </span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getData(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setData(</span><span class="vars">$data</span><span>){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->data = </span><span class="vars">$data</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getLeft(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->left; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setLeft(</span><span class="vars">$left</span><span>){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->left = </span><span class="vars">$left</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getRight(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->right; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setRight(</span><span class="vars">$right</span><span>){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->right = </span><span class="vars">$right</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getLTag(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->lTag; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setLTag(</span><span class="vars">$tag</span><span>){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->lTag = </span><span class="vars">$tag</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getRTag(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->rTag; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> setRTag(</span><span class="vars">$tag</span><span>){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->rTag = </span><span class="vars">$tag</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//线索二叉树类</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">class</span><span> BiTree{ </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$datas</span><span> = NULL;</span><span class="comment">//要导入的字符串;</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="vars">$root</span><span> = NULL; </span><span class="comment">//根结点</span><span> </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$leafCount</span><span> = 0;</span><span class="comment">//叶子结点个数</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="vars">$headNode</span><span> = NULL; </span><span class="comment">//线索二叉树的头结点</span><span> </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="vars">$preNode</span><span> = NULL;</span><span class="comment">//遍历线索化二叉树时保存前一个遍历的结点</span><span> </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> BiTree(</span><span class="vars">$datas</span><span>){ </span></span></li>
<li class="alt"><span> <span class="func">is_array</span><span>(</span><span class="vars">$datas</span><span>) </span><span class="vars">$datas</span><span> = </span><span class="func">str_split</span><span>(</span><span class="vars">$datas</span><span>); </span></span></li>
<li><span> <span class="vars">$this</span><span>->datas = </span><span class="vars">$datas</span><span>; </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->backupData = </span><span class="vars">$this</span><span>->datas; </span></span></li>
<li><span> <span class="vars">$this</span><span>->createTree(TRUE); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//前序遍历创建树</span><span> </span></span></li>
<li class="alt"><span> <span class="comment">//$root 判断是不是要创建根结点</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> createTree(</span><span class="vars">$root</span><span> = FALSE){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="func">empty</span><span class="keyword">empty</span><span>(</span><span class="vars">$this</span><span>->datas)) </span><span class="keyword">return</span><span> NULL; </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="vars">$first</span><span> = </span><span class="func">array_shift</span><span>(</span><span class="vars">$this</span><span>->datas); </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$first</span><span> == </span><span class="string">'#'</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> NULL; </span></span></li>
<li><span> }<span class="keyword">else</span><span>{ </span></span></li>
<li class="alt"><span> <span class="vars">$node</span><span> = </span><span class="keyword">new</span><span> Node(</span><span class="vars">$first</span><span>); </span></span></li>
<li><span> <span class="vars">$root</span><span> && </span><span class="vars">$this</span><span>->root = </span><span class="vars">$node</span><span>; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="vars">$node</span><span>->setLeft(</span><span class="vars">$this</span><span>->createTree()); </span></span></li>
<li class="alt"><span> <span class="vars">$node</span><span>->setRight(</span><span class="vars">$this</span><span>->createTree()); </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//返回二叉树叶子结点的个数</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getLeafCount(){ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->figureLeafCount(</span><span class="vars">$this</span><span>->root); </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->leafCount; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> figureLeafCount(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> == NULL) </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> false; </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$this</span><span>->checkEmpty(</span><span class="vars">$node</span><span>)){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->leafCount ++; </span></span></li>
<li class="alt"><span> }<span class="keyword">else</span><span>{ </span></span></li>
<li><span> <span class="vars">$this</span><span>->figureLeafCount(</span><span class="vars">$node</span><span>->getLeft()); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->figureLeafCount(</span><span class="vars">$node</span><span>->getRight()); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//判断结点是不是叶子结点</span><span> </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> checkEmpty(</span><span class="vars">$node</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span>->getLeft() == NULL && </span><span class="vars">$node</span><span>->getRight() == NULL){ </span></span></li>
<li><span> <span class="keyword">return</span><span> true; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">return</span><span> false; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//返回二叉树深度</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getDepth(){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->traversDepth(</span><span class="vars">$this</span><span>->root); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//遍历求二叉树深度</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> traversDepth(</span><span class="vars">$node</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> == NULL){ </span></span></li>
<li><span> <span class="keyword">return</span><span> 0; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="vars">$u</span><span> = </span><span class="vars">$this</span><span>->traversDepth(</span><span class="vars">$node</span><span>->getLeft()) + 1; </span></span></li>
<li><span> <span class="vars">$v</span><span> = </span><span class="vars">$this</span><span>->traversDepth(</span><span class="vars">$node</span><span>->getRight()) + 1; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$u</span><span> > </span><span class="vars">$v</span><span> ? </span><span class="vars">$u</span><span> : </span><span class="vars">$v</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//返回遍历结果,以字符串的形式</span><span> </span></span></li>
<li><span> <span class="comment">//$order 按遍历形式返回,前中后 </span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getList(</span><span class="vars">$order</span><span> = </span><span class="string">'front'</span><span>){ </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$this</span><span>->root == NULL) </span><span class="keyword">return</span><span> NULL; </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="vars">$nodeList</span><span> = </span><span class="keyword">array</span><span>(); </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">switch</span><span> (</span><span class="vars">$order</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">case</span><span> </span><span class="string">"front"</span><span>: </span></span></li>
<li><span> <span class="vars">$this</span><span>->frontList(</span><span class="vars">$this</span><span>->root, </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> <span class="keyword">break</span><span>; </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">case</span><span> </span><span class="string">"middle"</span><span>: </span></span></li>
<li><span> <span class="vars">$this</span><span>->middleList(</span><span class="vars">$this</span><span>->root, </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> <span class="keyword">break</span><span>; </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">case</span><span> </span><span class="string">"last"</span><span>: </span></span></li>
<li><span> <span class="vars">$this</span><span>->lastList(</span><span class="vars">$this</span><span>->root, </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> <span class="keyword">break</span><span>; </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">default</span><span>: </span></span></li>
<li><span> <span class="vars">$this</span><span>->frontList(</span><span class="vars">$this</span><span>->root, </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> <span class="keyword">break</span><span>; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">return</span><span> implode(</span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//创建线索二叉树</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> createThreadTree(){ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->headNode = </span><span class="keyword">new</span><span> Node(); </span></span></li>
<li><span> <span class="vars">$this</span><span>->preNode = & </span><span class="vars">$this</span><span>->headNode; </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->headNode->setLTag(0); </span></span></li>
<li><span> <span class="vars">$this</span><span>->headNode->setLeft(</span><span class="vars">$this</span><span>->root); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->headNode->setRTag(1); </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->threadTraverse(</span><span class="vars">$this</span><span>->root); </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->preNode->setRight(</span><span class="vars">$this</span><span>->headNode); </span></span></li>
<li><span> <span class="vars">$this</span><span>->preNode->setRTag(1); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->headNode->setRight(</span><span class="vars">$this</span><span>->preNode); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//线索化二叉树</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> threadTraverse(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> != NULL){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span>->getLeft() == NULL){ </span></span></li>
<li><span> <span class="vars">$node</span><span>->setLTag(1); </span></span></li>
<li class="alt"><span> <span class="vars">$node</span><span>->setLeft(</span><span class="vars">$this</span><span>->preNode); </span></span></li>
<li><span> }<span class="keyword">else</span><span>{ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->threadTraverse(</span><span class="vars">$node</span><span>->getLeft()); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$this</span><span>->preNode != </span><span class="vars">$this</span><span>->headNode && </span><span class="vars">$this</span><span>->preNode->getRight() == NULL){ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->preNode->setRTag(1); </span></span></li>
<li><span> <span class="vars">$this</span><span>->preNode->setRight(</span><span class="vars">$node</span><span>); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->preNode = & </span><span class="vars">$node</span><span>;</span><span class="comment">//注意传引用</span><span> </span></span></li>
<li><span> <span class="vars">$this</span><span>->threadTraverse(</span><span class="vars">$node</span><span>->getRight()); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//从第一个结点遍历中序线索二叉树</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> threadList(){ </span></span></li>
<li><span> <span class="vars">$arr</span><span> = </span><span class="keyword">array</span><span>(); </span></span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">for</span><span>(</span><span class="vars">$node</span><span> = </span><span class="vars">$this</span><span>->getFirstThreadNode(</span><span class="vars">$this</span><span>->root); </span><span class="vars">$node</span><span> != </span><span class="vars">$this</span><span>->headNode; </span><span class="vars">$node</span><span> = </span><span class="vars">$this</span><span>->getNextNode(</span><span class="vars">$node</span><span>)){ </span></span></li>
<li class="alt"><span> <span class="vars">$arr</span><span>[] = </span><span class="vars">$node</span><span>->getData(); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">return</span><span> implode(</span><span class="vars">$arr</span><span>); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//从尾结点反向遍历中序线索二叉树</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> threadListReserv(){ </span></span></li>
<li class="alt"><span> <span class="vars">$arr</span><span> = </span><span class="keyword">array</span><span>(); </span></span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">for</span><span>(</span><span class="vars">$node</span><span> = </span><span class="vars">$this</span><span>->headNode->getRight(); </span><span class="vars">$node</span><span> != </span><span class="vars">$this</span><span>->headNode; </span><span class="vars">$node</span><span> = </span><span class="vars">$this</span><span>->getPreNode(</span><span class="vars">$node</span><span>)){ </span></span></li>
<li><span> <span class="vars">$arr</span><span>[] = </span><span class="vars">$node</span><span>->getData(); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">return</span><span> implode(</span><span class="vars">$arr</span><span>); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//返回某个结点的前驱</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getPreNode(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span>->getLTag() == 1){ </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>->getLeft(); </span></span></li>
<li><span> }<span class="keyword">else</span><span>{ </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->getLastThreadNode(</span><span class="vars">$node</span><span>->getLeft()); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//返回某个结点的后继</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getNextNode(</span><span class="vars">$node</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span>->getRTag() == 1){ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>->getRight(); </span></span></li>
<li class="alt"><span> }<span class="keyword">else</span><span>{ </span></span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->getFirstThreadNode(</span><span class="vars">$node</span><span>->getRight()); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//返回中序线索二叉树的第一个结点</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getFirstThreadNode(</span><span class="vars">$node</span><span>){ </span></span></li>
<li><span> <span class="keyword">while</span><span>(</span><span class="vars">$node</span><span>->getLTag() == 0){ </span></span></li>
<li class="alt"><span> <span class="vars">$node</span><span> = </span><span class="vars">$node</span><span>->getLeft(); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>; </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//返回中序线索二叉树的最后一个结点</span><span> </span></span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getLastThreadNode(</span><span class="vars">$node</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">while</span><span>(</span><span class="vars">$node</span><span>->getRTag() == 0){ </span></span></li>
<li><span> <span class="vars">$node</span><span> = </span><span class="vars">$node</span><span>->getRight(); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$node</span><span>; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//前序遍历</span><span> </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> frontList(</span><span class="vars">$node</span><span>, & </span><span class="vars">$nodeList</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> !== NULL){ </span></span></li>
<li><span> <span class="vars">$nodeList</span><span>[] = </span><span class="vars">$node</span><span>->getData(); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->frontList(</span><span class="vars">$node</span><span>->getLeft(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li><span> <span class="vars">$this</span><span>->frontList(</span><span class="vars">$node</span><span>->getRight(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="comment">//中序遍历</span><span> </span></span></li>
<li class="alt"><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> middleList(</span><span class="vars">$node</span><span>, & </span><span class="vars">$nodeList</span><span>){ </span></span></li>
<li><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> != NULL){ </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->middleList(</span><span class="vars">$node</span><span>->getLeft(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li><span> <span class="vars">$nodeList</span><span>[] = </span><span class="vars">$node</span><span>->getData(); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->middleList(</span><span class="vars">$node</span><span>->getRight(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> } </span></li>
<li><span> </span></li>
<li class="alt"><span> <span class="comment">//后序遍历</span><span> </span></span></li>
<li><span> <span class="keyword">private</span><span> </span><span class="keyword">function</span><span> lastList(</span><span class="vars">$node</span><span>, & </span><span class="vars">$nodeList</span><span>){ </span></span></li>
<li class="alt"><span> <span class="keyword">if</span><span>(</span><span class="vars">$node</span><span> != NULL){ </span></span></li>
<li><span> <span class="vars">$this</span><span>->lastList(</span><span class="vars">$node</span><span>->getLeft(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li class="alt"><span> <span class="vars">$this</span><span>->lastList(</span><span class="vars">$node</span><span>->getRight(), </span><span class="vars">$nodeList</span><span>); </span></span></li>
<li><span> <span class="vars">$nodeList</span><span>[] = </span><span class="vars">$node</span><span>->getData(); </span></span></li>
<li class="alt"><span> } </span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getData(){ </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->data; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> </span></li>
<li><span> <span class="keyword">public</span><span> </span><span class="keyword">function</span><span> getRoot(){ </span></span></li>
<li class="alt"><span> <span class="keyword">return</span><span> </span><span class="vars">$this</span><span>->root; </span></span></li>
<li><span> } </span></li>
<li class="alt"><span> } </span></li>
<li><span>?> </span></li>
</ol>
陳述
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
AI Hentai Generator
免費產生 AI 無盡。
熱門文章
R.E.P.O.能量晶體解釋及其做什麼（黃色晶體）
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
刺客信條陰影：貝殼謎語解決方案
2 週前ByDDD
R.E.P.O.如果您聽不到任何人，如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：如何解鎖Myrise中的所有內容
4 週前By尊渡假赌尊渡假赌尊渡假赌
熱工具
MantisBT
Mantis是一個易於部署的基於Web的缺陷追蹤工具，用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。
記事本++7.3.1
好用且免費的程式碼編輯器
MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中，你可以繼續在那裡關注我們。 MinGW：GNU編譯器集合（GCC）的本機Windows移植版本，可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔；包括對MSVC執行時間的擴展，以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。
PhpStorm Mac 版本
最新（2018.2.1 ）專業的PHP整合開發工具
SublimeText3漢化版
中文版，非常好用
