資訊專欄INFORMATION COLUMN
摘要：樹在數(shù)據(jù)結(jié)構(gòu)還是很重要的，這里表示二叉樹用括號表示法表示。先寫一個二叉樹節(jié)點類二叉樹節(jié)點然后構(gòu)造二叉樹指針這里寫上一個打印二叉樹的函數(shù)中序遍歷運行結(jié)果輸入一個字符串語言實現(xiàn)中序遍歷
樹（Tree）在數(shù)據(jù)結(jié)構(gòu)還是很重要的，這里表示二叉樹用括號表示法表示。
先寫一個二叉樹節(jié)點類：
// 二叉樹節(jié)點
class BTNode {
public $data;
public $lchild = NULL;
public $rchild = NULL;
public function __construct($data) {
$this->data = $data;
}
}
然后構(gòu)造二叉樹：
function CreateBTNode(BTNode &$root = NULL, string $str)
{
$strArr = str_split($str);
$stack = [];
$p = NULL; // 指針
$top = -1;
$k = $j = 0;
$root = NULL;
foreach ($strArr as $ch) {
switch ($ch) {
case "(":
$top++;
array_push($stack, $p);
$k = 1;
break;
case ")":
array_pop($stack);
break;
case ",":
$k = 2;
break;
default:
$p = new BTNode($ch);
if($root == NULL) {
$root = $p;
} else {
switch ($k) {
case 1:
end($stack)->lchild = $p;
break;
case 2:
end($stack)->rchild = $p;
break;
}
}
break;
}
}
}
這里寫上一個打印二叉樹的函數(shù)（中序遍歷）：
function PrintBTNode($node)
{
if($node != NULL) {
PrintBTNode($node->lchild);
echo $node->data;
PrintBTNode($node->rchild);
}
}
運行結(jié)果：
輸入一個字符串
"A(B(C,D),G(F))"
package main
import (
"fmt"
"strings"
)
type BinaryTreeNode struct {
data string
lChild *BinaryTreeNode
rChild *BinaryTreeNode
}
func CreateBinaryTree(sequence string) *BinaryTreeNode {
words := strings.Split(sequence, "")
stack := []*BinaryTreeNode{}
var p *BinaryTreeNode = nil
top := -1
k := 0
var root *BinaryTreeNode = nil
for _, word := range words {
switch word {
case "(":
top++
stack = append(stack, p)
k = 1
case ")":
stack = stack[0:top]
top--
k = 0
case ",":
k = 2
default:
p = &BinaryTreeNode{
word,
nil,
nil,
}
if root == nil {
root = p
} else {
endItem := stack[top]
switch k {
case 1:
endItem.lChild = p
case 2:
endItem.rChild = p
}
}
}
}
return root
}
// 中序遍歷
func inOrderBinaryTree(root *BinaryTreeNode) {
if root != nil {
inOrderBinaryTree(root.lChild)
fmt.Print(root.data)
inOrderBinaryTree(root.rChild)
}
}
func main() {
testStr := "A(B(C,D),G(F))"
root := CreateBinaryTree(testStr)
inOrderBinaryTree(root)
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/23113.html
摘要：樹的前序，中序遍歷的結(jié)構(gòu)如下圖可以看出，通過前序遍歷可以確定根節(jié)點，再通過中序遍歷和根節(jié)點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。 從前序與中序遍歷序列構(gòu)造二叉樹 今天帶來的是Leetcode上的一個經(jīng)典題：從前序與中序遍歷序列構(gòu)造二叉樹原題干： /** Definition for a binary ...
摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數(shù)據(jù)結(jié)構(gòu)，使得其無論在增刪，還是查找，時間復(fù)雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據(jù)左子節(jié)點比該節(jié)點小，右子節(jié)點比該節(jié)點大的原則進行循環(huán)判斷即可。 什么是二叉樹 二叉樹就是樹的每個節(jié)點最多只能有兩個子節(jié)點 什么是二叉搜索樹 二叉搜索樹在二叉樹的基礎(chǔ)上，多了一個條件，就是二叉樹在插入值時，若插入值比當(dāng)前節(jié)點小，就插入到左節(jié)點，否則插...
摘要：回來更新一波，最近刷劍指，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書 回來更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...
摘要：回來更新一波，最近刷劍指，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學(xué)了一些樹的知識，發(fā)現(xiàn)也用不上，我想說的是，讀一本書體現(xiàn)不了這本書 回來更新一波，最近刷《劍指offer》，才又發(fā)現(xiàn)樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...
閱讀 543·2023-04-25 14:26
閱讀 1299·2021-11-25 09:43
閱讀 3493·2021-09-22 15:25
閱讀 1461·2019-08-30 15:54
閱讀 536·2019-08-30 12:57
閱讀 781·2019-08-29 17:24
閱讀 3177·2019-08-28 18:13
閱讀 2699·2019-08-28 17:52
