<?php#將二叉查找樹轉換為雙向鏈表，要求不能創建新節點，只能調節節點指針#解題思路是從樹的底層開始，調整每個節點的左右子樹，將左子樹的最大節點與根節點相連，將又子樹的最小節點與根節點相連#我們把節點的left當做鏈表的pre指針，right當做鏈表的next指針#直到所有子樹以及根節點轉換完成#樹節點class Node {public $data = null;public $parent = null;public $left = null;public $right = null;}#查找樹最小節點function search_min($root) {$cnode = $root;while ($cnode->left != null) {$cnode = $cnode->left;}return $cnode;}#查找樹的最打節點function search_max($root) {$cnode = $root;while ($cnode->right != null) {$cnode = $cnode->right;}return $cnode;}#查找某個節點中序遍歷的前趨function predecessor($node) {#如果該節點存在左子樹，則查找其左子樹的最大值if ($node->left != null) {return search_max($left);}#否則查找其父節點，直到當前節點是其父節點的右孩子$p = $node->parent;while ($p != null && $node == $p->left) {$node = $p;$p = $p->parent;}return $p;}#查找某個節點中序遍歷的后繼function successor($node) {#如果該節點存在右子樹，則查找其右子樹的最小值if ($node->right != null) {return search_min($node->right);}#否則查找其父節點，直到當前節點是其父節點的左孩子$p = $node->parent;while ($p != null && $node == $p->right) {$node = $p;$p = $p->parent;}return $p;}#插入節點function insert_node($root, $node) {$cnode = $root;$p = $root;#查找合適的插入位置while ($cnode != null) {$p = $cnode; if ($cnode->data > $node->data) {$cnode = $cnode->left;} else {$cnode = $cnode->right;}}if ($p == null) { #如果p為null，說明是空樹$root = $node;} else {if ($p->data > $node->data) {$p->left = $node;} else {$p->right = $node;}$node->parent = $p; }return $root;}#刪除結點function delete_node($root, $dnode) {if ($dnode->left != null || $dnode->right != null) {$c = $dnode;} else {$c = successor($dnode);}if ($c->left != null) {$s = $c->left;} else {$s = $c->right;}if ($s != null) {$s->parent = $c->parent;}if ($c->parent == null) { #c是根節點$root = $s;} else if ($c == $c->parent->left) {$c->parent->left = $s; } else {$c->parent->right = $s;}if ($dnode != $c) {$dnode->data = $c->data;}return $root;}#使用數組建立二叉查找樹function build_btree($a) {$root = new Node();$root->data= $a[0];for ($i = 1; $i < count($a); $i++) {$node = new Node();$node->data = $a[$i];insert_node($root, $node);}return $root;}#二叉樹中序遍歷function inorder_traverse($root) {if ($root->left != null) {inorder_traverse($root->left);}echo $root->data . " ";if ($root->right != null) {inorder_traverse($root->right);}}#鏈表的遍歷function linked_list_traverse($head) {$node = $head;while ($node != null) {echo $node->data . " ";$node = $node->right;}}#二叉查找樹變雙向鏈表function change($root) {#如果有子節點，就往子節點遞歸，直到最后一個非葉子節點，將他們的左右子節點連接成鏈表#然后逐層往上遞歸if ($root->left != null) {btree_to_doublelist($root->left);#這里不用擔心調整左右節點以后search_max查找出來的節點會出錯，因為雖然調整以后樹的結構變了，但是他依然保有二叉樹的性質#看圖1就知道了$predecessor = search_max($root->left);$predecessor->right = $root;$root->left = $predecessor;}if ($root->right != null) {btree_to_doublelist($root->right);$successor = search_min($root->right);$successor->left = $root;$root->right = $successor;}}function btree_to_doublelist($root) {#鏈表頭節點就是二叉查找樹的最小節點$head = search_min($root);change($root);return $head;}$a = array(10, 6, 14, 4, 8, 12, 16);$root = build_btree($a);inorder_traverse($root);echo "<br>";$link_head = btree_to_doublelist($root);linked_list_traverse($link_head);echo "<br>"; ?>

4 6 8 10 12 14 16?
4 6 8 10 12 14 16

?

轉載于:https://www.cnblogs.com/zemliu/archive/2012/09/26/2704881.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的PHP 将二叉查找树转换为双向链表，要求不能创建新节点，只能调节节点指针的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。