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>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
How to fix KB5055612 fails to install in Windows 10?
4 weeks agoByDDD
Roblox: Bubble Gum Simulator Infinity - How To Get And Use Royal Keys
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Roblox: Grow A Garden - Complete Mutation Guide
3 weeks agoByDDD
Nordhold: Fusion System, Explained
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Mandragora: Whispers Of The Witch Tree - How To Unlock The Grappling Hook
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hot Tools
SublimeText3 Linux new version
SublimeText3 Linux latest version
SecLists
SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.
ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment
DVWA
Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software
Notepad++7.3.1
Easy-to-use and free code editor
