社群
學習
工具庫
AI工具
休閒
搜尋
繁体中文
首頁 php教程 php手册 PHP实现二叉树/线索二叉树

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jun 21, 2016 am 08:53 AM
function gt nbsp node this

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

Undresser.AI Undress

人工智慧驅動的應用程序，用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！

顯示更多

熱門文章

如何修復KB5055612無法在Windows 10中安裝？
4 週前 By DDD
<🎜>：種植花園 - 完整的突變指南
3 週前 By DDD
<🎜>：泡泡膠模擬器無窮大 - 如何獲取和使用皇家鑰匙
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
北端：融合系統，解釋
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora：巫婆樹的耳語 - 如何解鎖抓鉤
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
顯示更多

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版，非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

顯示更多

熱門話題

Java教學
1669
14
CakePHP 教程
1428
52
Laravel 教程
1329
25
PHP教程
1273
29
C# 教程
1256
24
顯示更多
Related knowledge
解決方法：您的組織要求您更改 PIN 碼 解決方法：您的組織要求您更改 PIN 碼 Oct 04, 2023 pm 05:45 PM

「你的組織要求你更改PIN訊息」將顯示在登入畫面上。當在使用基於組織的帳戶設定的電腦上達到PIN過期限制時，就會發生這種情況，在該電腦上，他們可以控制個人設備。但是，如果您使用個人帳戶設定了Windows，則理想情況下不應顯示錯誤訊息。雖然情況並非總是如此。大多數遇到錯誤的使用者使用個人帳戶報告。為什麼我的組織要求我在Windows11上更改我的PIN？可能是您的帳戶與組織相關聯，您的主要方法應該是驗證這一點。聯絡網域管理員會有所幫助！此外，配置錯誤的本機原則設定或不正確的登錄項目也可能導致錯誤。即

Windows 11 上調整視窗邊框設定的方法：變更顏色和大小 Windows 11 上調整視窗邊框設定的方法：變更顏色和大小 Sep 22, 2023 am 11:37 AM

Windows11將清新優雅的設計帶到了最前沿;現代介面可讓您個性化和更改最精細的細節，例如視窗邊框。在本指南中，我們將討論逐步說明，以協助您在Windows作業系統中建立反映您的風格的環境。如何更改視窗邊框設定？按+開啟“設定”應用程式。 WindowsI前往個人化，然後按一下顏色設定。顏色變更視窗邊框設定視窗11「寬度=」643「高度=」500「&gt;找到在標題列和視窗邊框上顯示強調色選項，然後切換它旁邊的開關。若要在「開始」功能表和工作列上顯示主題色，請開啟「在開始」功能表和工作列上顯示主題

如何在 Windows 11 上變更標題列顏色？ 如何在 Windows 11 上變更標題列顏色？ Sep 14, 2023 pm 03:33 PM

預設情況下，Windows11上的標題列顏色取決於您選擇的深色/淺色主題。但是，您可以將其變更為所需的任何顏色。在本指南中，我們將討論三種方法的逐步說明，以更改它並個性化您的桌面體驗，使其具有視覺吸引力。是否可以更改活動和非活動視窗的標題列顏色？是的，您可以使用「設定」套用變更活動視窗的標題列顏色，也可以使用登錄編輯程式變更非活動視窗的標題列顏色。若要了解這些步驟，請前往下一部分。如何在Windows11中變更標題列的顏色？ 1.使用「設定」應用程式按+開啟設定視窗。 WindowsI前往“個人化”，然

Windows 11 上啟用或停用工作列縮圖預覽的方法 Windows 11 上啟用或停用工作列縮圖預覽的方法 Sep 15, 2023 pm 03:57 PM

工作列縮圖可能很有趣，但它們也可能分散注意力或煩人。考慮到您將滑鼠懸停在該區域的頻率，您可能無意中關閉了重要視窗幾次。另一個缺點是它使用更多的系統資源，因此，如果您一直在尋找一種提高資源效率的方法，我們將向您展示如何停用它。不過，如果您的硬體規格可以處理它並且您喜歡預覽版，則可以啟用它。如何在Windows11中啟用工作列縮圖預覽？ 1.使用「設定」應用程式點擊鍵並點選設定。 Windows按一下系統，然後選擇關於。點選高級系統設定。導航至“進階”選項卡，然後選擇“效能”下的“設定”。在「視覺效果」選

OOBELANGUAGE錯誤Windows 11 / 10修復中出現問題的問題 OOBELANGUAGE錯誤Windows 11 / 10修復中出現問題的問題 Jul 16, 2023 pm 03:29 PM

您是否在Windows安裝程式頁面上看到「出現問題」以及「OOBELANGUAGE」語句？ Windows的安裝有時會因此類錯誤而停止。 OOBE表示開箱即用的體驗。正如錯誤提示所表示的那樣，這是與OOBE語言選擇相關的問題。沒有什麼好擔心的，你可以透過OOBE螢幕本身的漂亮註冊表編輯來解決這個問題。快速修復–1.點選OOBE應用底部的「重試」按鈕。這將繼續進行該過程，而不會再打嗝。 2.使用電源按鈕強制關閉系統。系統重新啟動後，OOBE應繼續。 3.斷開系統與網際網路的連接。在脫機模式下完成OOBE的所

Windows 11 上的顯示縮放比例調整指南 Windows 11 上的顯示縮放比例調整指南 Sep 19, 2023 pm 06:45 PM

在Windows11上的顯示縮放方面，我們都有不同的偏好。有些人喜歡大圖標，有些人喜歡小圖標。但是，我們都同意擁有正確的縮放比例很重要。字體縮放不良或圖像過度縮放可能是工作時真正的生產力殺手，因此您需要知道如何自訂以充分利用系統功能。自訂縮放的優點：對於難以閱讀螢幕上的文字的人來說，這是一個有用的功能。它可以幫助您一次在螢幕上查看更多內容。您可以建立僅適用於某些監視器和應用程式的自訂擴充功能設定檔。可以幫助提高低階硬體的效能。它使您可以更好地控制螢幕上的內容。如何在Windows11

10種在 Windows 11 上調整亮度的方法 10種在 Windows 11 上調整亮度的方法 Dec 18, 2023 pm 02:21 PM

螢幕亮度是使用現代計算設備不可或缺的一部分，尤其是當您長時間注視螢幕時。它可以幫助您減輕眼睛疲勞，提高易讀性，並輕鬆有效地查看內容。但是，根據您的設置，有時很難管理亮度，尤其是在具有新UI更改的Windows11上。如果您在調整亮度時遇到問題，以下是在Windows11上管理亮度的所有方法。如何在Windows11上變更亮度[10種方式解釋]單一顯示器使用者可以使用下列方法在Windows11上調整亮度。這包括使用單一顯示器的桌上型電腦系統以及筆記型電腦。讓我們開始吧。方法1：使用操作中心操作中心是訪問

華為GT3 Pro和GT4的差異是什麼？ 華為GT3 Pro和GT4的差異是什麼？ Dec 29, 2023 pm 02:27 PM

許多用戶在選擇智慧型手錶的時候都會選擇的華為的品牌，其中華為GT3pro和GT4都是非常熱門的選擇，不少用戶都很好奇華為GT3pro和GT4有什麼區別，下面就給大家介紹一下二者。華為GT3pro和GT4有什麼差別一、外觀GT4：46mm和41mm，材質是玻璃鏡板+不鏽鋼機身+高分纖維後殼。 GT3pro：46.6mm和42.9mm，材質是藍寶石玻璃鏡+鈦金屬機身/陶瓷機身+陶瓷後殼二、健康GT4：採用最新的華為Truseen5.5+演算法，結果會更加的精準。 GT3pro：多了ECG心電圖和血管及安

See all articles