数据结构之二叉树

栏目: 数据库 · 发布时间: 5年前

内容简介:本文是数据结构和算法之美学习笔记树这种数据结构跟现实中的树很像,里面的每个元素叫做结点,用连线把相邻的结点连接起来,相邻结点之间的关系叫父子关系。比如下图中,A结点是B的父节点,B是A的子结点,B,C,D是兄弟结点,E没有父节点称为根节点,没有子节点的结点是叶子结点,G,H,I,H,K,L都是叶子结点。

本文是数据结构和算法之美学习笔记

树这种数据结构跟现实中的树很像,里面的每个元素叫做结点,用连线把相邻的结点连接起来,相邻结点之间的关系叫父子关系。

比如下图中,A结点是B的父节点,B是A的子结点,B,C,D是兄弟结点,E没有父节点称为根节点,没有子节点的结点是叶子结点,G,H,I,H,K,L都是叶子结点。

数据结构之二叉树

树一般用三个概念可以描述,高度,深度,层

高度:结点到叶子结点的最长路径(边数)

深度:根结点到这个结点所经历的边的个数

层数:结点的深度加1

树的高度:根结点的高度

数据结构之二叉树

高度是从下往上度量,就像数楼层。深度从上往下度量,就像往水下看,层数是跟深度类似,不过是以1为起点。

二叉树

顾名思义,就是每个结点最多有两个叉,也就是两个叶子结点,左子节点和右子节点,左右子节点只要存在一个就行。

如果除了叶子结点外的每个结点都有左右两个子节点,这种二叉树叫“满二叉树”

如果叶子结点都在最底下两层,最后一层的叶子结点都靠左排列,并且除了最后一层,其他的结点个数都要达到最大,这种二叉树叫做“完全二叉树”

如何存储一个二叉树?

可以使用基于指针的或者引用的二叉链式存储法,或者基于数组的顺序存储法。

链式存储法:

每个结点有三个字段,其中一个缓存数据,剩下的两个分别是指向左右子节点的指针。我们只要找到根节点就能通过左右指针找到所有数据。

顺序存储法:

把根节点存储在下标为i=1的位置,左子节点存储在下标为2 i=2的位置,右子节点存储在2 i+1=3的位置,以此类推。

对于顺序存储法来说,完全二叉树更能节省内存。

二叉树的遍历

经典的方法有三种:前序遍历,中序遍历,后序遍历。前中后表示的是结点本身打印的顺序。

  • 前序遍历是对于树种的任意结点来说,先打印这个结点,然后在打印它的左子树,最后打印它的右子树
  • 中序遍历是对于树种任意结点来说,先打印它的左子树,在打印它本身,最后打印它的右子树
  • 后序遍历是先对于树种任意结点来说,先打印左子树,在打印右子树,最后打印结点本身。

其实二叉树的前中后遍历就是一个递归的过程。比如前序遍历,就是先打印跟结点,然后递归打印左子树,在递归打印右子树。

遍历方法:

void preOrder(Node* root) {
  if (root == null) return;
  System.out.print(root.data);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  System.out.print(root.data);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  System.out.print(root.data);
}

还有一种按层遍历,这个需要用到队列

public void levelOrder(BinaryTree tree) {
    // 利用队列先入先出的特点来实现按层遍历
    LinkedList<BinaryTree> linkedList = new LinkedList<>();
    // 记录当前遍历到哪个结点
    BinaryTree currentNode = tree;
    // 根节点入队
    linkedList.add(currentNode);
    // 从队列中弹出各结点数据,直到队列为空,遍历完毕
    while (linkedList.size()>0){
    // 弹出队首元素(当前结点),打印其数据,并依次将其左右子节点入队
      currentNode = linkedList.poll();
      System.out.print(currentNode.data+" -> ");
      if (currentNode.left!=null) {
        linkedList.add(currentNode.left);
      }
      if (currentNode.right!=null) {
        linkedList.add(currentNode.right);
      }
    }
  }

二叉树最大的特点就是支持动态数据集合的快速插入、删除、查找操作。

二叉查找树(Binary Search Tree)

二叉查找树也叫二叉搜索树,是为了实现快速查找而生的,不过它不仅支持快速查找还支持快速插入删除。

二叉查找树规定:在树中的任意一个节点,其左子树的每个值都小于这个节点的值,右子树的每个值都大于这个节点的值。

1.二叉查找树的查找

先取根节点,如果它等于我们要查找的数据,那就返回,如果要查找的数据小于根节点的值,那就在左子树中查找,反之就在右子树中查找。

代码:

public class BinarySearchTree {
  private Node tree;
  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

2.二叉查找树的插入

新插入的数据一般都是在叶子节点,我们需要从根节点开始依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大,并且节点的右子树为空,就把数据插到右子节点的位置,如果不为空就在递归遍历右子树,直到找到插入的位置。如果要插入的数据比节点数值小并且节点的左子树为空,就插入,不为空,递归遍历左子树直到找到插入位置。

代码:

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }
  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

3.二叉查找树的删除

删除操作比插入和查找操作麻烦一点

(1)如果要删除的节点是叶子节点,我们只需更新父节点指向删除节点的指针为null

(2)如果要删除的节点只有一个子节点,我们只需要更新其父节点中指向要删除节点的指针,让它指向要删除的节点的子节点就好了

(3)如果要删除的节点有两个子节点,我们需要找到这个节点的右子树中的最小节点,或者这个节点的左子树的最大节点,把它替换到要删除的节点上。因为父节点的指针一定比所有左子树的节点值大,比右子树的节点的值

代码:

public void delete(int data) {
  Node p = tree; // p 指向要删除的节点,初始化指向根节点
  Node pp = null; // pp 记录的是 p 的父节点
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  if (p == null) return; // 没有找到

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    Node minPP = p; // minPP 表示 minP 的父节点
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    p.data = minP.data; // 将 minP 的数据替换到 p 中
    p = minP; // 下面就变成了删除 minP 了
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p 的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  if (pp == null) tree = child; // 删除的是根节点
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

中序遍历二叉树可以输出有序的数据序列,并且非常高效。因此二叉查找树也叫做二叉 排序 树。

如果数据中有重复的数据怎么办?

(1)二叉查找树中不仅会存储一个数据,我们可以通过链表和支持动态扩容的数组,把相同的值存储在同一个节点上。

(2)插入数据的时候,如果碰到一个节点的值与要插入的数据的值相同,就将这个要插入的数据放到这个节点的右子树,也就是把它当成大于这个节点的值来处理。

当要查找数据的时候,遇到值相同的节点,不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点停止。

删除数据的时候,先找到每个要删除的节点,然后按照前面的删除方法依次删除。


以上所述就是小编给大家介绍的《数据结构之二叉树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

信息时代三部曲:经济、社会与文化

信息时代三部曲:经济、社会与文化

[美] 曼纽尔·卡斯特(Manuel Castells) / 夏铸九、王志弘 / 社会科学文献出版社 / 2003 / 33.00

《信息时代三部曲:经济、社会与文化》包括《网络社会的崛起》《认同的力量》《千年终结》,由英国Blackwell Publishers Ltd. 授权出版,据原书1997版和2000版译出。2001年和2006年版《网络社会的崛起》也使用了同一ISBN。一起来看看 《信息时代三部曲:经济、社会与文化》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具