二叉樹算法之構造

susheng 發布于2019-06-27 16:49 / 2351人閱讀

摘要：樹在數據結構還是很重要的，這里表示二叉樹用括號表示法表示。先寫一個二叉樹節點類二叉樹節點然后構造二叉樹指針這里寫上一個打印二叉樹的函數中序遍歷運行結果輸入一個字符串語言實現中序遍歷

樹（Tree）在數據結構還是很重要的，這里表示二叉樹用括號表示法表示。
先寫一個二叉樹節點類：

// 二叉樹節點
class BTNode {
    public $data;

    public $lchild = NULL;

    public $rchild = NULL;

    public function __construct($data) {
        $this->data = $data;
    }
}

然后構造二叉樹：

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;
        }
    }
}

這里寫上一個打印二叉樹的函數（中序遍歷）：

function PrintBTNode($node)
{
    if($node != NULL) {
        PrintBTNode($node->lchild);
        echo $node->data;
        PrintBTNode($node->rchild);
    }
}

運行結果：
輸入一個字符串
"A(B(C,D),G(F))"

go語言實現

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)
}

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖二叉樹 python二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/23113.html

算法之不定期更新（四）—— 從前序與中序遍歷序列構造二叉樹（2018-06-02）

摘要：樹的前序，中序遍歷的結構如下圖可以看出，通過前序遍歷可以確定根節點，再通過中序遍歷和根節點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。從前序與中序遍歷序列構造二叉樹今天帶來的是Leetcode上的一個經典題：從前序與中序遍歷序列構造二叉樹原題干： /** Definition for a binary ...

charles_paul 2019-08-26 11:57 評論0 收藏0
JavaScript算法之二叉搜索樹

摘要：二叉搜索樹的特性二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是，為二叉樹的高度。二叉搜索樹的查找查找很簡單，根據左子節點比該節點小，右子節點比該節點大的原則進行循環判斷即可。什么是二叉樹二叉樹就是樹的每個節點最多只能有兩個子節點什么是二叉搜索樹二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插...

khlbat 2019-08-21 16:26 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章六）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

Cympros 2019-06-28 13:56 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章五）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

developerworks 2019-06-27 16:27 評論0 收藏0
二叉樹遍歷

摘要：前言本篇文章是在二叉排序樹的基礎上進行遍歷查找與刪除結點。接下來我們根據構造的這顆二叉樹進行相應遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷。中序遍歷二叉排序樹，得到的數組是有序的且是升序的。前言本篇文章是在二叉排序樹的基礎上進行遍歷、查找、與刪除結點。那么首先來看一下什么是二叉排序樹？二叉排序樹定義二叉排序樹，又稱二叉查找樹、二叉搜索樹。若...

aboutU 2019-08-26 13:54 評論0 收藏0