二叉树算法之构造

susheng 发布于2019-06-27 16:49 / 2330人阅读

摘要：树在数据结构还是很重要的，这里表示二叉树用括号表示法表示。先写一个二叉树节点类二叉树节点然后构造二叉树指针这里写上一个打印二叉树的函数中序遍历运行结果输入一个字符串语言实现中序遍历

树（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二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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