资讯专栏INFORMATION COLUMN

数据结构:二叉树

Ashin / 1270人阅读

摘要:链式存储结构由于二叉树的每个结点最多有两个孩子,所以为每个结点设计一个数据域和两个指针域。最终能得到二叉树的完整结构。

这篇文章主要介绍树结构中的一种特殊存在——二叉树。主要内容有:

二叉树的概念

二叉树的基本结构

二叉树的操作

概念

二叉树: 每个结点最多有两个子结点,两个子结点是有次序的,且子结点次序不能颠倒。两个子结点一般称之为左结点及右结点。

层次: 在树中,节点的层次从根开始定义,根为第一层。

深度: 树中节点的最大层次为树的深度。

度: 结点拥有的结点数。

分支结点: 度不为0的结点。

叶子节点: 度为0的结点。

特殊二叉树

满二叉树:所有分支结点都存在左右两节点,并且所有叶子结点都在同一层。

斜树:所有的结点都只有左子结点或者右子结点。

完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<=i<=n)的结点 与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则称之为完全二叉树。

二叉查找树:左子树中节点的值都小于根节点的值,右子树中节点的值都大于根节点的值。

结构 顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系。使用顺序存储结构表现二叉树的时候,在其线性结构中,会存在一些空结点,但是其会占据一定的内存空间,会造成存储空间的浪费。

链式存储结构

由于二叉树的每个结点最多有两个孩子,所以为每个结点设计一个数据域和两个指针域。

结点的定义

结点的结构定义:

class TreeNode {
    var value: String
    var left: TreeNode");
操作 创建二叉树

现在我们创建一棵如图所示的二叉树:

为了能让每个结点确认是否有左右子结点,我们将预期二叉树进行一个扩展:

我们给每一个结点的空指针引出一个虚结点,其值为一个特定值——#。

创建这棵二叉树代码:

let arr = ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"]
var index = 0

func preCreateTree(_ tree: inout BinaryTreeNode");if index > arr.count-1 {
        return
    }

    let value = arr[index]

    index += 1

    if value == "#" {
        tree = nil
    } else {
        // 生成根结点
        tree = BinaryTreeNode(value)

        // 构造左子树
        preCreateTree(&tree!.leftChild)

        // 构造右子树
        preCreateTree(&tree!.rightChild)
    }
}

var root: BinaryTreeNode");
遍历

二叉树的遍历主要分为四种:

前序遍历: 根结点-->左子树-->右子树。

中序遍历: 左子树-->根结点-->右子树。

后序遍历: 左子树-->右子树-->根结点。

层序遍历: 从上至下一层一层遍历。

前序遍历

前面创建二叉树时,我们有一个数组 ["A", "B", "D", "G", "#", "#", "H", "#", "#", "#", "C", "E", "#", "I", "#", "#", "F"],这个数组是如何得到的呢?

就是根据前序遍历扩展二叉树的结果得到的这个数组,并利用这个数组前序创建了我们预期的二叉树。

前序遍历代码:

func preOrderTraverse(_ tree: BinaryTreeNode");if let node = tree {
        print("value is (node.value)")

        // 先序遍历左子树
        preOrderTraverse(node.leftChild)

        // 再先序遍历右子树
        preOrderTraverse(node.rightChild)
    }
}

中序遍历

中序遍历代码:

func inOrdertraverse(_ tree: BinaryTreeNode");if let node = tree {
        // 中序遍历左子树
        inOrdertraverse(node.leftChild)

        print("value is (node.value)")

        // 中序遍历右子树
        inOrdertraverse(node.rightChild)
    }
}

后序遍历

后序遍历代码:

func lastOrdertraverse(_ tree: BinaryTreeNode");if let node = tree {
        // 后序遍历左子树
        lastOrdertraverse(node.leftChild)

        // 后序遍历右子树
        lastOrdertraverse(node.rightChild)

        print("value is (node.value)")
    }
}

层序遍历

层序遍历代码:

func levelOrdertraverse(_ tree: BinaryTreeNode");let root = tree else {
        return
    }
    
    var tempQueue: [BinaryTreeNode] = []
    
    // 将根节点加入数组
    if let _ = root.value {
        tempQueue.insert(root, at: 0)
    }
    
    while tempQueue.count != 0 {
    	  // 取出数组最后一个元素
        let temp = tempQueue.popLast()!
        
        // 将下一层结点依次插入到数组最前面
        if let l = temp.leftChild, l.value != nil {
            tempQueue.insert(l, at: 0)
        }
        
        if let r = temp.rightChild, r.value != nil {
            tempQueue.insert(r, at: 0)
        }
        
        print(temp.value)
    }
}
树的最大深度
func maxDepth(_ tree: BinaryTreeNode");let root = tree else {
        return 0
    }
    
    return max(maxDepth(root.leftChild), maxDepth(root.rightChild)) + 1
}
推导遍历结果

遍历特点:

前序遍历: 根结点-->左子树-->右子树。

中序遍历: 左子树-->根结点-->右子树。

后序遍历: 左子树-->右子树-->根结点。

根据遍历特点,得出解题思路:

    找到根-->找到左右子树

    一直重复这个操作,直到最后一个子节点。

题目一:求后序遍历

题目: 已知前序遍历 ABDGHCEIF 及中序遍历 GDHBAEICF,求出后序遍历顺序?

解答:

    先序遍历的结果是ABDGHCEIF,根据先序得到根节点是A;中序遍历的结果是GDHBAEICF,根据中序得到A之前的节点都是左子树,A之后的节点都是右子树。

    再对左右子树进行第一步的分析。最终能得到二叉树的完整结构。

题目二:求前序遍历

题目: 已知后序遍历 GHDBIEFCA 及中序遍历 GDHBAEICF,求出后序遍历顺序?

解答:

    后序遍历的结果是GHDBIEFCA,根据先序得到根节点是A;中序遍历的结果是GDHBAEICF,根据中序得到A之前的节点都是左子树,A之后的节点都是右子树。

    再对左右子树进行第一步的分析。最终能得到二叉树的完整结构。

总结一下

    已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

    已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

但是,已知前序和后序是不能确定一棵二叉树的。

例如:前序遍历序列为 ABC 及后序遍历序列为 CBA。

可以确定 A 一定是根节点,但是接下来无法确定哪些是左子树,哪些是右子树。此时,这棵二叉树有以下四种可能:

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

转载请注明本文地址:https://www.ucloud.cn/yun/7326.html

相关文章

  • Java数据结构与算法——叉树及操作(包括叉树遍历)

    摘要:本篇主要介绍二叉树的概念二叉树的表示二叉树的操作三种遍历方式实现求二叉树的子树求节点的父节点二叉树高度,可能是考试中的,也可能是面试中的。通常二叉树的遍历根据根节点的遍历次序分为先根遍历中根遍历后根遍历。 声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。 前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇主要介绍二叉树的概念、二叉树的表示、二叉树的操作(三种遍历...

    muddyway 评论0 收藏0
  • js数据结构和算法(三)叉树

    摘要:同样结点树的二叉树,完全二叉树的深度最小。二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表。 二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...

    DesGemini 评论0 收藏0
  • 数据结构初阶之叉树】:叉树相关的性质和经典的习题(用C语言实现,附图详解)

    摘要:当集合为空时,称该二叉树为空二叉树。也就是说,如果一个二叉树的层数为,且结点总数是,则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。 ...

    Martin91 评论0 收藏0

发表评论

0条评论

Ashin

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<