Skip to content

Latest commit

 

History

History
524 lines (452 loc) · 13 KB

7-二叉树（第10章）.md

File metadata and controls

524 lines (452 loc) · 13 KB
Raw

7-二叉树（第10章）

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据 。本章将研究一种特殊的树： 二叉查找树。

7.1 什么是树

树是一种数据结构，由一组以边线连接的节点组成。以下就是一颗普通的树

树

树的节点：一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点。一个节点可以有 0 个、 1 个或多个子节点。没有任何子节点的节点称为叶子节点。

树的遍历：沿着树的一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历

树的深度：树可以分为几个层次，根节点是第 0 层，它的子节点是第 1 层，子节点的子节点是第 2层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度

7.2 二叉树

首先我们要了解下什么是二叉树，二叉树是一种特殊的树，它的子节点个数不超过两个。二叉查找树是在二叉树的基础上对树的结构进行了进一步的约束。

二叉查找树又名二叉排序树，有时候也叫二叉搜索树。它具有以下特征：

  • 若左子树不为空，则左子树上所有的结点的值均小于它根节点的值
  • 若右子树不为空，那么右子树上所有节点的值均大于它根节点的值
  • 左右子树也分别为二叉查找树
  • 没有键值相等的节点

7.3 实现一个二叉树

二叉树都是由节点组成的，所以我们要实现二叉树必须要先实现节点，一个节点通常包含三部分——数据、左子节点、右子节点。因此我们可以定义这样的一个node对象来代表我们的节点。

class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
}

Node 对象既保存数据，也保存和其他节点的链接

现在我们可以创建一个类，用来表示二叉查找树，我们让类只包含一个数据成员：一个表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null，以此创建一个空节点。

接下来我们来实现一个insert方法，用来向树中插入新的节点。实现这个方法的算法如下：

  1. 如果跟节点为null,则把根节点设置为要插入的节点

  2. 如果待插入节点保存的数据小于当前节点，则获取当前节点的左节点，如果左节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的左节点不存在，则直接把待插入的节点设置为当前节点的左节点

  3. 如果待插入节点保存的数据大于当前节点，则获取当前节点的右节点，如果右节点存在则与待插入的节点进行比较，重复步骤2。如果当前节点的右节点不存在，则直接把待插入的节点设置为当前节点的右节点

实现二叉树

class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
}

*验证二叉树

let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)
console.log('bst:',bst)

真实的打印结果很难显示在博客里，画成图的话如下：

二叉树图

实现是正确的，说明我们的二叉树程序没有问题

7.4 二叉树的遍历

二叉树遍历常用的有以下三种。

  • 前序遍历：先访问根->遍历左子树->遍历右子树
  • 中序遍历：遍历左子树->访问根->遍历右子树
  • 后序遍历：遍历左子树->遍历右子树->访问根

遍历的前中后顺序其实是指访问根节点的顺序

前序遍历：

  // 前序遍历
  preOrder(node) {
    if (node != null) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }

中序遍历：

  // 中序遍历
  inOrder(node) {
    if (node != null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }

后序遍历

  // 后序遍历
  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }

**遍历的方法使用的是递归，非常绕，需要多理解理解

完整代码如下

class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }

}

class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
  // 前序遍历
  preOrder(node) {
    if (node != null) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }
  // 中序遍历
  inOrder(node) {
    if (node != null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  // 后序遍历
  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }
}

测试：

let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)

bst.preOrder(bst.root) // 8 3 2 6 4 5 7 9 11

bst.inOrder(bst.root) // 2 3 4 5 6 7 8 9 11

bst.postOrder(bst.root) // 2 5 4 7 6 3 11 9 8

测试没有，说明我们的遍历是正确的。

7.5 二叉树查找

  • 查找给定的值
  • 查找最大值
  • 查找最小值
  // 查找最大是
  getMax() {
    let node = this.root
    while (true) {
      if (node.right === null) {
        console.log(node.data)
        break
      }
      node = node.right
    }
  }
  // 查找最小值
  getMin() {
    let node = this.root
    while (true) {
      if (node.left === null) {
        console.log(node.data)
        break
      }
      node = node.left
    }
  }
  getSomeNum(num) {
    let node = this.root
    while (node) {
      if (num < node.data) {
        node = node.left
      } else if (num > node.data) {
        node = node.right
      } else if (num === node.data) {
        console.log('node.data:', node.data)
        break
      }
    }
  }

测试

bst.getMax() // 11
bst.getMin() // 2
bst.getSomeNum(9) // node.data: 9
bst.getSomeNum(1) //

7.6 从二叉树上删除节点

在二叉树上删除节点会比较复杂，如果要删除的节点没有子节点还好，如果要删除的节点有一个节点或者两个节点，都要考虑到这些节点的处理情况，这时就比较难以处理。

  • 如果待删除节点是叶子节点（没有子节点的节点），那么只需要将从父节点指向它的链接改为 null
  • 如果待删除节点只包含一个子节点，那么原本指向它的节点就得做些调整，使其指向它的子节点。
  • 最后，如果待删除节点包含两个子节点，正确的做法有两种：要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。这里我们选择后一种方式。

程序如下：

  getSmallest(ndoe) {
    while (node.left !== null) {
      node = node.left
    }
    return node
  }
  remove(data) {
    root = removeNode(this.root, data)
  }
  // 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点
  removeNode(node, data) {
    if (node === null) {
      return null
    }
    if (data === node.data) {
      if (node.left === null && node.right === null) {
        return null
      }
      // 没有左子节点
      if (node.left === null) {
        return node.right
      }
      // 没有右子节点
      if (node.right === null) {
        return node.left
      }
      // 有两个字节点
      let tempNode = this.getSmallest(node.right)
      node.data = tempNode.data
      node.right = removeNode(node.right, tempNode.data)
      return node
    } else if (data < node.data) {
      node.left = removeNode(node.left, data)
      return node
    } else {
      node.right = removeNode(node.right, data)
      return node
    }
  }

测试

class Node {
  constructor(data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }

}

class BST {
  constructor() {
    this.root = null
  }
  insert(data) {
    let n = new Node(data, null, null)
    if (this.root === null) {
      this.root = n
    } else {
      var current = this.root
      while (true) {
        if (n.data < current.data) {
          if (current.left === null) {
            current.left = n
            break
          }
          current = current.left
        } else {
          if (current.right === null) {
            current.right = n
            break
          }
          current = current.right
        }
      }
    }

  }
  // 前序遍历
  preOrder(node) {
    if (node != null) {
      console.log(node.data)
      this.preOrder(node.left)
      this.preOrder(node.right)
    }
  }
  // 中序遍历
  inOrder(node) {
    if (node != null) {
      this.inOrder(node.left)
      console.log(node.data)
      this.inOrder(node.right)
    }
  }
  // 后序遍历
  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left)
      this.postOrder(node.right)
      console.log(node.data)
    }
  }
  // 查找最大是
  getMax() {
    let node = this.root
    while (true) {
      if (node.right === null) {
        console.log(node.data)
        break
      }
      node = node.right
    }
  }
  // 查找最小值
  getMin() {
    let node = this.root
    while (true) {
      if (node.left === null) {
        console.log(node.data)
        break
      }
      node = node.left
    }
  }
  getSomeNum(num) {
    let node = this.root
    while (node) {
      if (num < node.data) {
        node = node.left
      } else if (num > node.data) {
        node = node.right
      } else if (num === node.data) {
        console.log('node.data:', node.data)
        break
      }
    }
  }
  getSmallest(ndoe) {
    while (node.left !== null) {
      node = node.left
    }
    return node
  }
  remove(data) {
    this.root = this.removeNode(this.root, data)
  }
  // 如果要删除的节点是当前节点，则返回null，否则返回原节点，并按照规则，递归查找下一个节点是不是目标节点
  removeNode(node, data) {
    if (node === null) {
      return null
    }
    if (data === node.data) {
      if (node.left === null && node.right === null) {
        return null
      }
      // 没有左子节点
      if (node.left === null) {
        return node.right
      }
      // 没有右子节点
      if (node.right === null) {
        return node.left
      }
      // 有两个字节点
      let tempNode = this.getSmallest(node.right)
      node.data = tempNode.data
      node.right = this.removeNode(node.right, tempNode.data)
      return node
    } else if (data < node.data) {
      node.left = this.removeNode(node.left, data)
      return node
    } else {
      node.right = this.removeNode(node.right, data)
      return node
    }
  }
}
let bst = new BST()
bst.insert(8)
bst.insert(3)
bst.insert(6)
bst.insert(4)
bst.insert(9)
bst.insert(11)
bst.insert(2)
bst.insert(5)
bst.insert(7)

bst.remove(9)

bst.inOrder(bst.root)
// 打印结果
2
3
4
5
6
7
8
11

从打印结果看，需要删除的数据被删除了，bst能正常遍历，中序遍历顺序也正确，说明我们删除程序没有问题。自此关于二叉树的知识点就基本讲完了。有实际情况时根据实际情况再调整。