算法学些-树、二叉树、二叉搜索树

定义

树(Tree)是元素的集合,每棵树由多个节点(node)组成,用以储存元素。某些节点之间存在着一定的关系,用连线表示,连线称为边(edge)或者链接。边的上端点成为父节点,下端称为子节点。

tree
每个节点可以有多个子节点,而该节点则是相应子节点的父节点。但是每个节点只能有一个父节点(只有一个例外,也就是根节点,它没有父节点),如图中第一棵树的 S 节点即为根节点。而没有子节点的节点则称为叶子节点或叶节点,如上图中第一棵树的 A、R、X 节点。E、X 的父节点是一个节点,所以它们被称为兄弟节点。

  • 树是元素的集合
  • 该集合可以为空。此时树中没有元素,称之为空树(empty tree)。
  • 如果该集合不为空,那么该集合至少含有一个根节点以及 0 个或多个子树。根节点与它的子树的根节点用一个边(edge)或链接相连。

特征

高度(Height)、深度(Depth)、层(Level)

  • 节点的高度 = 节点到叶子结点的最长路径(边数)
  • 节点的深度 = 根节点到这个节点所经历的边的个数
  • 节点的层数 = 节点的深度 + 1
  • 树的高度 = 根节点的高度
    tree

二叉树

定义

二叉树是一种特殊的数据结构,顾名思义,二叉树只有两个叉,也就是两个子节点:左子节点和右子节点。其中,左子节点是左子树的根节点,右子节点是右子树的根节点。当然,这并不是说,二叉树一定要求每个节点都必须有两个子节点,有的节点只有左子节点,而有的节点只有右子节点。

二叉树的三种遍历方法

  • 前序遍历(也叫先序遍历):若二叉树为空,则空操作,否则,对于二叉树中的任意节点,先访问这个节点,然后再访问它的左子树,最后打印它的右子树。
  • 中序遍历:若二叉树为空,则空操作,否则,对于二叉树中的任意节点,先访问它的左子树,然后再访问这个节点本身,最后访问它的右子树。
  • 后序遍历:若二叉树为空,则空操作,否则,对于二叉树中的任意节点,先访问它的左子树,然后访问它的右子树,最后访问这个节点本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** 先序递归遍历 */
void DLR(BiTree bt) {
if (null != bt) {
System.out.println(bt.data);
DLR(bt.lchild);
DLR(bt.rchild);
}
}
/** 中序递归遍历 */
void LDR(BiTree bt) {
if (null != bt) {
LDR(bt.lchild);
System.out.println(bt.data);
LDR(bt.rchild);
}
}
/** 后序递归遍历 */
void LRD(BiTree bt) {
if (null != bt) {
LRD(bt.lchild);
LRD(bt.rchild);
System.out.println(bt.data);
}
}

树与二叉树的区别

  • 二叉树的每个节点最多只能有两个节点,而树则无限制
  • 二叉树中节点的子树分为左子树和右子树,即使某个节点只有一棵树,也必须要指明这棵树是左子树还是右子树,也就是说,二叉树是有序的
  • 树不能为空,至少含有一个节点,而一棵二叉树可以为空

二叉搜索树

定义

二叉查找树(Binary Search Tree,BST)是一种特殊的二叉树,一棵二叉搜索树(BST)是一棵二叉树,其中,每个节点的值都要大于其左子树中任意节点的值而小于右子树中任意节点的值。

特征

  • 若它的左子树不为空,那么左子树上所有节点的key都小于根节点的key。
  • 若它的右子树不为空,那么右子树上所有节点的key都大于根节点的key。
  • 它的左右子树也分别为二叉排序树。

查找

  • 如果二叉查找树为空,则返回空操作,否则,执行一下操作;
  • 先取根节点,如果节点 X 等于根节点,则返回;
  • 如果节点小于根节点,则递归查找左子树;
  • 如果节点大于根节点,则递归查找右子树。

插入

  • 如果树是空的,则直接将新节点插入,否则,执行下面步骤。
  • 要插入的数据比根节点数据大,则到右子树中插入新数据,如果右子树为空,则将新数据直接插入到右子节点的位置;不为空,则继续遍历右子树,查找插入位置。
  • 要插入的数据比根节点数据小,则到左子树中插入数据,如果左子树为空,则直接将新数据插入到左子节点的位置;不为空,则继续遍历左子树,查找插入的位置。

删除

  • 第一种情况,如果要删除的节点没有子节点,直接将父节点指向要删除节点的指针指向 null。比如途中要删除的节点 55。
  • 第二种情况,如果要删除的节点只有一个节点,即只有左子节点或右子节点,则将父节点指向要删除节点的指针指向要删除节点的子节点即可。比如途中要删除的节点
  • 第三种情况,如果要删除的节点有两个子节点,则需要先找到这个节点右子树中的最小节点或者左子树中的最大节点,将其替换到要删除的节点上。然后删除这个右子树中的最小节点或左子树中的最大节点,这样就可以利用
    1、2 两条规则来删除了。

查找最大、最小节点

查找最大、最小节点比较简单,比如要查找二叉查找树的最大节点时,如果二叉查找树为空,则返回空操作,如果不为空,则判断是否只有一个节点(即只有根节点),如果是则返回根节点,否则到右子树中递归查找。同理,查找最小节点类似,只是到左子树中查找而已。