PHP实现二叉树/线索二叉树
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>Nach dem Login kopieren
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Heiße KI -Werkzeuge
Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos
AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.
Undress AI Tool
Ausziehbilder kostenlos
Clothoff.io
KI-Kleiderentferner
AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.
Heißer Artikel
R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor
By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
1 Monate vor
By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
4 Wochen vor
By 尊渡假赌尊渡假赌尊渡假赌
Wie lange dauert es, um Split Fiction zu schlagen?
3 Wochen vor
By DDD
R.E.P.O. Dateispeicherspeicherort: Wo ist es und wie schützt sie?
3 Wochen vor
By DDD
Heiße Werkzeuge
Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor
SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen
Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung
Dreamweaver CS6
Visuelle Webentwicklungstools
SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)
Heiße Themen
Lösung: Ihre Organisation verlangt von Ihnen, dass Sie Ihre PIN ändern
Oct 04, 2023 pm 05:45 PM
Auf dem Anmeldebildschirm wird die Meldung „Ihre Organisation hat Sie gebeten, Ihre PIN zu ändern“ angezeigt. Dies geschieht, wenn das PIN-Ablauflimit auf einem Computer erreicht wird, der organisationsbasierte Kontoeinstellungen verwendet und die Kontrolle über persönliche Geräte hat. Wenn Sie Windows jedoch über ein persönliches Konto einrichten, sollte die Fehlermeldung im Idealfall nicht erscheinen. Obwohl dies nicht immer der Fall ist. Die meisten Benutzer, die auf Fehler stoßen, melden dies über ihre persönlichen Konten. Warum fordert mich meine Organisation auf, meine PIN unter Windows 11 zu ändern? Es ist möglich, dass Ihr Konto mit einer Organisation verknüpft ist. Ihr primärer Ansatz sollte darin bestehen, dies zu überprüfen. Die Kontaktaufnahme mit Ihrem Domain-Administrator kann hilfreich sein! Darüber hinaus können falsch konfigurierte lokale Richtlinieneinstellungen oder falsche Registrierungsschlüssel Fehler verursachen. Im Augenblick
So passen Sie die Fensterrahmeneinstellungen unter Windows 11 an: Farbe und Größe ändern
Sep 22, 2023 am 11:37 AM
Windows 11 bringt frisches und elegantes Design in den Vordergrund; die moderne Benutzeroberfläche ermöglicht es Ihnen, feinste Details, wie zum Beispiel Fensterränder, zu personalisieren und zu ändern. In diesem Leitfaden besprechen wir Schritt-für-Schritt-Anleitungen, die Ihnen dabei helfen, eine Umgebung zu erstellen, die Ihrem Stil im Windows-Betriebssystem entspricht. Wie ändere ich die Fensterrahmeneinstellungen? Drücken Sie +, um die Einstellungen-App zu öffnen. WindowsIch gehe zu Personalisierung und klicke auf Farbeinstellungen. Farbänderung Fensterränder Einstellungen Fenster 11" Breite="643" Höhe="500" > Suchen Sie die Option Akzentfarbe auf Titelleiste und Fensterrändern anzeigen und schalten Sie den Schalter daneben um. Um Akzentfarben im Startmenü und in der Taskleiste anzuzeigen Um die Designfarbe im Startmenü und in der Taskleiste anzuzeigen, aktivieren Sie „Design im Startmenü und in der Taskleiste anzeigen“.
Wie ändere ich die Farbe der Titelleiste unter Windows 11?
Sep 14, 2023 pm 03:33 PM
Standardmäßig hängt die Farbe der Titelleiste unter Windows 11 vom gewählten Dunkel-/Hell-Design ab. Sie können es jedoch in jede gewünschte Farbe ändern. In diesem Leitfaden besprechen wir Schritt-für-Schritt-Anleitungen für drei Möglichkeiten, wie Sie Ihr Desktop-Erlebnis ändern und personalisieren können, um es optisch ansprechend zu gestalten. Ist es möglich, die Farbe der Titelleiste von aktiven und inaktiven Fenstern zu ändern? Ja, Sie können die Farbe der Titelleiste aktiver Fenster mit der App „Einstellungen“ ändern, oder Sie können die Farbe der Titelleiste inaktiver Fenster mit dem Registrierungseditor ändern. Um diese Schritte zu lernen, fahren Sie mit dem nächsten Abschnitt fort. Wie ändere ich die Farbe der Titelleiste in Windows 11? 1. Drücken Sie in der App „Einstellungen“ +, um das Einstellungsfenster zu öffnen. WindowsIch gehe zu „Personalisierung“ und dann
OOBELANGUAGE-Fehlerprobleme bei der Reparatur von Windows 11/10
Jul 16, 2023 pm 03:29 PM
Wird auf der Windows Installer-Seite „Ein Problem ist aufgetreten“ zusammen mit der Anweisung „OOBELANGUAGE“ angezeigt? Aufgrund solcher Fehler bricht die Installation von Windows manchmal ab. OOBE bedeutet Out-of-the-Box-Erlebnis. Wie aus der Fehlermeldung hervorgeht, handelt es sich hierbei um ein Problem im Zusammenhang mit der OOBE-Sprachauswahl. Sie müssen sich keine Sorgen machen, Sie können dieses Problem durch eine geschickte Bearbeitung der Registrierung über den OOBE-Bildschirm selbst lösen. Schnelllösung – 1. Klicken Sie unten in der OOBE-App auf die Schaltfläche „Wiederholen“. Dadurch wird der Prozess ohne weitere Probleme fortgesetzt. 2. Verwenden Sie den Netzschalter, um das Herunterfahren des Systems zu erzwingen. Nach dem Neustart des Systems sollte OOBE fortgesetzt werden. 3. Trennen Sie das System vom Internet. Schließen Sie alle Aspekte von OOBE im Offline-Modus ab
So aktivieren oder deaktivieren Sie die Vorschau von Miniaturansichten in der Taskleiste unter Windows 11
Sep 15, 2023 pm 03:57 PM
Miniaturansichten in der Taskleiste können Spaß machen, aber auch ablenken oder stören. Wenn man bedenkt, wie oft Sie mit der Maus über diesen Bereich fahren, haben Sie möglicherweise ein paar Mal versehentlich wichtige Fenster geschlossen. Ein weiterer Nachteil besteht darin, dass es mehr Systemressourcen verbraucht. Wenn Sie also nach einer Möglichkeit suchen, ressourceneffizienter zu arbeiten, zeigen wir Ihnen, wie Sie es deaktivieren können. Wenn Ihre Hardware-Spezifikationen jedoch dafür geeignet sind und Ihnen die Vorschau gefällt, können Sie sie aktivieren. Wie aktiviere ich die Miniaturvorschau der Taskleiste in Windows 11? 1. Tippen Sie in der App „Einstellungen“ auf die Taste und klicken Sie auf „Einstellungen“. Klicken Sie unter Windows auf „System“ und wählen Sie „Info“. Klicken Sie auf Erweiterte Systemeinstellungen. Navigieren Sie zur Registerkarte „Erweitert“ und wählen Sie unter „Leistung“ die Option „Einstellungen“ aus. Wählen Sie „Visuelle Effekte“
Was sind die Unterschiede zwischen Huawei GT3 Pro und GT4?
Dec 29, 2023 pm 02:27 PM
Viele Benutzer werden sich bei der Auswahl von Smartwatches für die Marke Huawei entscheiden. Viele Benutzer sind neugierig auf den Unterschied zwischen Huawei GT3pro und GT4. Was sind die Unterschiede zwischen Huawei GT3pro und GT4? 1. Aussehen GT4: 46 mm und 41 mm, das Material ist Glasspiegel + Edelstahlgehäuse + hochauflösende Faserrückschale. GT3pro: 46,6 mm und 42,9 mm, das Material ist Saphirglas + Titangehäuse/Keramikgehäuse + Keramikrückschale 2. Gesundes GT4: Mit dem neuesten Huawei Truseen5.5+-Algorithmus werden die Ergebnisse genauer. GT3pro: EKG-Elektrokardiogramm sowie Blutgefäß und Sicherheit hinzugefügt
Anleitung zur Anzeigeskalierung unter Windows 11
Sep 19, 2023 pm 06:45 PM
Wir alle haben unterschiedliche Vorlieben, wenn es um die Anzeigeskalierung unter Windows 11 geht. Manche Leute mögen große Symbole, andere mögen kleine Symbole. Wir sind uns jedoch alle einig, dass die richtige Skalierung wichtig ist. Eine schlechte Schriftartenskalierung oder eine Überskalierung von Bildern kann bei der Arbeit ein echter Produktivitätskiller sein. Sie müssen daher wissen, wie Sie sie anpassen können, um die Fähigkeiten Ihres Systems optimal zu nutzen. Vorteile des benutzerdefinierten Zooms: Dies ist eine nützliche Funktion für Personen, die Schwierigkeiten haben, Text auf dem Bildschirm zu lesen. Es hilft Ihnen, mehr gleichzeitig auf dem Bildschirm zu sehen. Sie können benutzerdefinierte Erweiterungsprofile erstellen, die nur für bestimmte Monitore und Anwendungen gelten. Kann dazu beitragen, die Leistung von Low-End-Hardware zu verbessern. Dadurch haben Sie mehr Kontrolle darüber, was auf Ihrem Bildschirm angezeigt wird. So verwenden Sie Windows 11
10 Möglichkeiten, die Helligkeit unter Windows 11 anzupassen
Dec 18, 2023 pm 02:21 PM
Die Bildschirmhelligkeit ist ein wesentlicher Bestandteil der Nutzung moderner Computergeräte, insbesondere wenn Sie über einen längeren Zeitraum auf den Bildschirm schauen. Es hilft Ihnen, die Belastung Ihrer Augen zu reduzieren, die Lesbarkeit zu verbessern und Inhalte einfach und effizient anzuzeigen. Abhängig von Ihren Einstellungen kann es jedoch manchmal schwierig sein, die Helligkeit zu verwalten, insbesondere unter Windows 11 mit den neuen Änderungen an der Benutzeroberfläche. Wenn Sie Probleme beim Anpassen der Helligkeit haben, finden Sie hier alle Möglichkeiten, die Helligkeit unter Windows 11 zu verwalten. So ändern Sie die Helligkeit unter Windows 11 [10 Möglichkeiten erklärt] Benutzer eines einzelnen Monitors können die folgenden Methoden verwenden, um die Helligkeit unter Windows 11 anzupassen. Hierzu zählen sowohl Desktop-Systeme mit einem einzelnen Monitor als auch Laptops. Lasst uns beginnen. Methode 1: Verwenden Sie das Action Center. Das Action Center ist zugänglich
