Community
Learn
Tools Library
AI Tools
Leisure
search
English
Home > php教程 > php手册 > PHP实现二叉树/线索二叉树

PHP实现二叉树/线索二叉树

WBOY
Release： 2016-06-21 08:53:05
Original
776 people have browsed it

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>
Copy after login



Related labels：
function gt nbsp node this
source：php.cn
Previous article：Zerver2 for PHP100 集成开发环境 Next article：PHP中$_REQUEST中的数据覆盖问题
Statement of this Website
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
Latest Articles by Author
Latest Issues
function_exists() cannot determine the custom function Function test () {return true;} if (function_exists ('test')) {echo "test is function...
From 2024-04-29 11:01:01
0
2
1429
There is no output in the parent window document.onclick = function(){ window.opener.document.write('I am the output of the child ...
From 2024-04-18 23:52:34
0
1
1284
PX automatic conversion to REM error  <style>html {   font-size: calc(100vw / 3.75);      }...
From 2024-04-16 09:34:16
0
0
4687
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template