综合技术

数据结构之二叉树

微信扫一扫,分享到朋友圈

数据结构之二叉树
0

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

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

比如下图中,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)插入数据的时候,如果碰到一个节点的值与要插入的数据的值相同,就将这个要插入的数据放到这个节点的右子树,也就是把它当成大于这个节点的值来处理。

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

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

阅读原文...


mingyunxiaohai的专栏

Processing large volumes of data safely and fast using Node.js and PostgreSQL

上一篇

揭秘贝索斯蜕变之旅:从洗碗好丈夫变小报头条

下一篇

您也可能喜欢

评论已经被关闭。

插入图片
数据结构之二叉树

长按储存图像,分享给朋友