二叉树(一)

PHP admin 1303℃ 0评论

树!什么是树?它是由n(n>=1)个有限节点组成一个具有层次关系的集合。和线性表一样是一种数据结构

树的特征:

  1. 每个节点有零个或多个子节点;
  2. 没有父节点的节点称为根节点;
  3. 每一个非根节点有且只有一个父节点;
  4. 除了根节点外,每个子节点可以分为多个不相交的子树;

其中数分类有序树和无序树。

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;而二叉树是一个特殊的有序树。

二叉树:每个节点最多含有两个子树的树称为二叉树;二叉树一般情况下它是有序的。

二叉树类型分为:完全二叉树、满二叉树、哈夫曼树(又叫最优二叉树)、其他的二叉树都叫做非完全二叉树。

B数又叫B-树或B_树 洋文叫B-tree 、 B_tree

B-tree 是一个多插平衡树。

平衡树,即平衡二叉树(Balanced Binary Tree)[1] ,具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉树

 

遍历二叉树

  1. 前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。
  2. 中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。
  3. 后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

遍历二叉树

 

在有序二叉树中我们一般都是用中序遍历,中序遍历结果会将结果从小到大排列出来。

中序查询

中序排序结果:40、60、80、100、120、140、160

 

 

转载请注明:My House » 二叉树(一)

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址