0%

树简介

树简介

树跟数组、链表、堆栈一样,是一种数据结构。它由有限个节点,组成具有层次关系的集合

  • 结点的度:一个结点含有的子结点个数称为该结点的度;
  • 树的度:一棵树中,最大结点的度称为树的度;
  • 父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;
  • 深度:对于任意结点n,n的深度为从根到n的唯一路径长,根结点的深度为0;
  • 高度:对于任意结点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0

特点

  • 每个结点或者无子结点或者只有有限个子结点;
  • 有一个特殊的结点,它没有父结点,称为根结点;
  • 每一个非根节点有且只有一个父节点;
  • 树里面没有环路

分类

按照有序性,可以分为有序树和无序树:

  • 无序树:树中任意节点的子结点之间没有顺序关系
  • 有序树:树中任意节点的子结点之间有顺序关系

按照节点包含子树个数,可以分为B树和二叉树,二叉树可以分为以下几种:

  • 二叉树:每个节点最多含有两个子树的树称为二叉树;
  • 二叉查找树:首先它是一颗二叉树,若左子树不空,则左子树上所有结点的值均小于它的根结点的值;若右子树不空,则右子树上所有结点的值均大于它的根结点的值;左、右子树也分别为二叉排序树;
  • 满二叉树:叶节点除外的所有节点均含有两个子树的树被称为满二叉树;
  • 完全二叉树:如果一颗二叉树除去最后一层节点为满二叉树,且最后一层的结点依次从左到右分布
  • 霍夫曼树:带权路径最短的二叉树。
  • 红黑树:红黑树是一颗特殊的二叉查找树,每个节点都是黑色或者红色,根节点、叶子节点是黑色。如果一个节点是红色的,则它的子节点必须是黑色的。
  • 平衡二叉树(AVL):一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树