数据结构-树

,是一种数据结构。链式 存储方式。由n(n>0)个节点组成。每个节点有零个子节点或多个子节点。没有父节点的成为根节点。

相关术语:

深度:这个树向下的最大层数称为度。

叶节点或终端节点:度为0的节点成为叶节点。

子孙:以某节点为根向下任意的子节点都成为该节点的子孙。

森林:由多个不相交的树的集合成为森林。

分类:

无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树。

有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树。

二叉树:每个节点最多含有两个子树的树称为二叉树。完全二叉树,满二叉树都是为了方便对二叉树进行操作。

霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树;

常见的满二叉树

树的遍历:

树的遍历方式有三种:先序遍历,中序遍历,后序遍历。

先序遍历的规则为:根节点>左节点>右节点

以上图举个栗子:先序结果为1245367

中序遍历的规则为:左节点>根节点>右节点

举个栗子:中序结果为4251637

后序遍历的规则为:左节点>右节点>根节点

举个栗子:后序结果为4526731

在C语言中实现主要思想使用递归,较简单参见CSDN。

根据已知二叉树的三种遍历结果还原二叉树

已知先,中序遍历或者中,后序遍历,是可以画出二叉树的。在已知先,后序,是不可以还原二叉树的。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180701G05DP500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券