乐趣区

关于二叉树:数据结构与算法学习封装二叉树

jiezi

上篇文章也提到了二叉树的劣势以及重要性，那么就让咱们来着手封装一个二叉树吧。咱们先来看看它有哪些常见的操作方法。

二叉搜寻树常见的操作

insert(key): 向树中插入一个新的键
search(key)：在树中查找一个键，如果节点存在，则返回 true；如果不存在，则返回 false
preOrderTraverse：通过先序遍历形式遍历所有节点
inOrderTraverse: 通过中序遍历形式遍历所有节点
postorderTraverse: 通过后序遍历形式遍历所有节点
min：返回树中最小的值
max: 返回树中最大的值
remove(key)：从树中移除某个键

insert（插入）办法

封装代码前咱们先来捋一下 insert 的逻辑

要向树中插入一个新的节点或键要经验三个步骤。

1 第一步是验证插入操作树是否为一个空树。如果是, 咱们要做的就是创立一个 Node 类的实例并将它赋值给 root(根节点) 属性。
2 如果树非空须要找到插入新节点的地位，寻找对应节点的办法：
如下图，如果咱们须要在下图插入一个键为 6 的节点，那么就先拿 6 和 11 做比拟，发现 6 <11，就向左移，再而后 6 和 7 做比拟，6<7 那么持续向下，和 5 做比拟，6>5，那就让 6 插入到 5 的右节点

插入 6 的过程

封装代码
首先每个节点都须要 left(左指针),right(右指针)和 key(键)组成，所以咱们须要先实现一个 Node 类

class CreateNode {constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

insert 封装

// 插入新节点
insert(key) {let newNode = new CreateNode(key);
  // 判断是否为空树
  if (!this.root) {this.root = newNode} else {
    let parent = null;
    let current = this.root;
    // isLeftChild 来判断是左侧还是右侧
    let isLeftChild = false;
    while (current) {
      parent = current
        if (key < current.key) {
            current = current.left;
            isLeftChild = true
           } else {
            current = current.right;
            isLeftChild = false;
        }
    }
    isLeftChild ? parent.left = newNode : parent.right = newNode
 }
}
先序遍历（preOrderTraverse）

先序遍历是以优先于后辈节点的程序拜访每个节点的。先序遍历的一种利用是打印一个结构化的文档。

咱们来看实现.callBack 是为了测试的一个函数，上面同理。

preOrderTraverse(callBack) {this.preOrderTraverseNode(this.root, callBack)
}
preOrderTraverseNode(node, callBack) {if (node) {callBack(node.key);
    this.preOrderTraverseNode(node.left, callBack);
    this.preOrderTraverseNode(node.right, callBack)
  }
}

下面代码是依据函数调用栈来实现的 this.preOrderTraverseNode(node.left, callBack); 走这段代码的时候将 11.7.5.3 相继压入栈中，当 node==null 的时候完结递归，栈中的函数顺次开释。因为曾经执行完了 node.left，每次出栈的时候会执行上面的 node.right，顺次类推就造成了上图的执行程序

中序遍历

中序遍历是一种以上行程序拜访 BST(BinarySearchTree)所有节点的遍历形式也就是以从最小到最大的程序拜访所有节点

中序遍历的一种利用就是对树进行排序操作。咱们来看看它的实现。

inOrderTraverse(callBack) {this.inOrderTraverseNode(this.root, callBack)
}
inOrderTraverseNode(node, callBack) {if (node) {this.inOrderTraverseNode(node.left, callBack);
    callBack(node.key);
    this.inOrderTraverseNode(node.right, callBack)
  }
}
后序遍历

后序遍历则是先拜访节点的后辈节点再拜访节点自身。后序遍历的一种利用是计算一个目录及其子目录中所有文件所占空间的大小。

咱们来看看它的实现。

// 后序遍历
postorderTraverse(callBack) {this.postorderTraverseNode(this.root, callBack)
}
postorderTraverseNode(node, callBack) {if (node) {this.postorderTraverseNode(node.left, callBack);
    this.postorderTraverseNode(node.right, callBack);
    callBack(node.key);
  }
}

想必明确了一种其余两种就会自然而然的明确了，要联合栈内存一起了解。

min(寻找最小值)

在一棵二叉树中最左侧就是最小值

min() {
  let current = this.root;
  while (current.left) {current = current.left}
  return current.key
}
max(寻找最大值)

在一棵二叉树中最右侧就是最小值

max() {
  let current = this.root;
  while (current.right) {current = current.right}
  return current.key
}
search(依据 key 值寻找)

依据 key 值寻找只有以后的 key!= 要寻找的 key 那么就持续向深一层的寻找，如果找不到间接返回 false，找到了返回 true

search(key) {
  let current = this.root;
  while (current && current.key != key) {if (key < current.key) {current = current.left} else if (key > current.key) {current = current.right}
  }
  return current ? true : false
}
删除(remove)

删除操作能够说是二叉树中最难的一个办法了; 上面会一一列举删除须要顾及的场景；

第一步

删除的第一步是先寻找要删除的 key
parent：是对应节点的父节点
isLeftChild：是为了辨别是左子树还是右子树

let current = this.root;
let parent = null;
let isLeftChild = false;
while (current && current.key != key) {
  parent = current;
  if (key < current.key) {
    isLeftChild = true;
    current = current.left;
  } else if (key > current.key) {
    isLeftChild = false;
    current = current.right
 }
}
if (!current) return;
第二步

判断要删除的节点是不是叶子节点，也就是没有左子树 (left) 和右子树(right); 这种状况下间接让 parent 的左子树或者右子树置为 null 即可。例如删除的是下图中 6 这个节点，下面寻找到的 current 为 6，parent 为 5.

if (!current.left && !current.right) {isLeftChild ? parent.left = null : parent.right = null;}
第三步

如果有左子树没有右子树的状况下

1 删除 {5} 节点，{5}节点只有左子树，删除 {5} 这个节点间接让 {7} 的左指针指向 {5} 的左子树 parent.left = current.left

2 删除 {5} 节点，如图 {5} 节点只有右子树，删除 {5} 这个节点间接让 {7} 的左指针指向 {5} 的右子树 parent.left = current.right

3 删除 {20} 节点，如图 {20} 节点只有右子树，删除 {20} 这个节点间接让 {15} 的右指针指向 {20} 的右子树
parent.right = current.right

4 删除 {20} 节点，如图 {20} 节点只有左子树，删除 {20} 这个节点间接让 {15} 的右指针指向 {20} 的左子树
parent.right = current.left

下面的状况都曾经列举革除，因为咱们下面曾经定义了 isLeftChild 的变量，能够轻松晓得 parent 的指针方向，至于删除以后节点的左节点还是有节点这个须要咱们判断一下

if (current.left && !current.right) {isLeftChild ? parent.left = current.left : parent.right = current.left;} else if (current.right && !current.left) {isLeftChild ? parent.left = current.right : parent.right = current.left;}
第四步

删除有两个子节点的树，这一步也是删除办法中场景最多的一步。
如下图删除 {15} 这个节点，那么咱们须要从它的子节点中的某一个提上去而又不会影响二叉树的规定，那么该提取哪一个呢。
这里有个词叫前驱后继，其中咱们抉择前驱也好抉择后继也能够。比方上面删除 {15} 节点他的前驱是 14，那么把 14 提上去又变成了一棵合乎规定的二叉树。{15}的后继为 18，用 18 代替 15 也是一棵合乎规定的树。参照下面咱们能够找到寻找前驱后继的规定：
前驱：删除某节点的左子树中最大的键
后继：删除某节点的右子树中最小的键

删除 15 须要做的逻辑
1. 找到 15 的后继(前驱也能够，这里我抉择后继)18
2. 将 18 提到 15 的地位，让 18 的左指针指向 13，让 18 的右指针指向 20
3. 将 20 的左指针指向 19

删除 11 须要做的逻辑
间接让根 = 后继

获取前驱的代码

getSuccessor(node) {
  let successParent = null;
  while (node.left) {
    successParent = node;
    node = node.left
 }
  if (successParent) {successParent.left = node.right;}
  return node
}

删除有两个子节点的代码

let successor = this.getSuccessor(current.right);
if (current == this.root) {this.root = successor} else if (isLeftChild) {parent.left = successor} else {parent.right = successor;}
successor.left = current.left;
if (current.right != successor) {successor.right = current.right}

残缺代码

class CreateNode {constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {constructor() {this.root = null;}
  // 插入新节点
 insert(key) {let newNode = new CreateNode(key);
    if (!this.root) {this.root = newNode} else {
      let parent = null;
      let current = this.root;
      let isLeftChild = false;
      while (current) {
        parent = current
 if (key < current.key) {
          current = current.left;
          isLeftChild = true
 } else {
          current = current.right;
          isLeftChild = false;
        }
      }
      isLeftChild ? parent.left = newNode : parent.right = newNode
 }
  }
  // 先序遍历
 preOrderTraverse(callBack) {this.preOrderTraverseNode(this.root, callBack)
  }
  preOrderTraverseNode(node, callBack) {if (node) {callBack(node.key);
      this.preOrderTraverseNode(node.left, callBack);
      this.preOrderTraverseNode(node.right, callBack)
    }
  }
  // 中序遍历
 inOrderTraverse(callBack) {this.inOrderTraverseNode(this.root, callBack)
  }
  inOrderTraverseNode(node, callBack) {if (node) {this.inOrderTraverseNode(node.left, callBack);
      callBack(node.key);
      this.inOrderTraverseNode(node.right, callBack)
    }
  }
  // 后序遍历
 postorderTraverse(callBack) {this.postorderTraverseNode(this.root, callBack)
  }
  postorderTraverseNode(node, callBack) {if (node) {this.postorderTraverseNode(node.left, callBack);
      this.postorderTraverseNode(node.right, callBack);
      callBack(node.key);
    }
  }
  // 最大值
 max() {
    let current = this.root;
    while (current.right) {current = current.right}
    return current.key
 }
  // 最小值
 min() {
    let current = this.root;
    while (current.left) {current = current.left}
    return current.key
 }
  // 查问值
 search(key) {
    let current = this.root;
    while (current && current.key != key) {if (key < current.key) {current = current.left} else if (key > current.key) {current = current.right}
    }
    return current ? true : false
 }
  // 删除
 remove(key) {
    let current = this.root;
    let parent = null;
    let isLeftChild = false;
    while (current && current.key != key) {
      parent = current;
      if (key < current.key) {
        isLeftChild = true;
        current = current.left;
      } else if (key > current.key) {
        isLeftChild = false;
        current = current.right
 }
    }
    if (!current) return;
    if (!current.left && !current.right) {isLeftChild ? parent.left = null : parent.right = null;} else {if (current.left && !current.right) {isLeftChild ? parent.left = current.left : parent.right = current.left;} else if (current.right && !current.left) {isLeftChild ? parent.left = current.right : parent.right = current.left;} else {let successor = this.getSuccessor(current.right);
        if (current == this.root) {this.root = successor} else if (isLeftChild) {parent.left = successor} else {parent.right = successor;}
        successor.left = current.left;
        if (current.right != successor) {successor.right = current.right}
      }
    }
  }
  getSuccessor(node) {
    let successParent = null;
    while (node.left) {
      successParent = node;
      node = node.left
 }
    if (successParent) {successParent.left = node.right;}
    return node
  }
}
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(10);
bst.insert(8);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(19);
// 测试先序遍历
 let resString = '';
 bst.preOrderTraverse(function (key) {resString += key + ' ';})
 alert(resString)
// 测试中序遍历
 let resString = '';
  bst.inOrderTraverse(function (key) {resString += key + ' ';});
  alert(resString)
// 测试后序遍历
 let resString = '';
  bst.postorderTraverse(function (key) {resString += key + ' ';});
  alert(resString)
 // 最大值
 alert(bst.max());
 // 最小值
 alert(bst.min());
// 查问值
alert(bst.search(18))
// 删除
bst.remove(11)
退出移动版