数据结构与算法系列之树

283

相关概念解析

  • 节点的高度:节点到叶子节点的最长路径(边数)
  • 节点的深度:根节点到这个节点所经历的边数
  • 节点的层:定义一棵树的根结点层次为1,其他节点的层次是其父结点层次加1。值是节点的深度+1
  • 树的高度:根节点的高度

Tree

二叉树

类型

  1. 完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
  2. 满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
  3. 平衡二叉树——平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

实现一颗二叉查找树

需要实现下面的功能

  • insert(key):插入一个节点
  • remove(key):移除一个节点
  • search(key):搜索目标值的节点
  • postOrder: 后序遍历
  • inOrder: 中顺遍历
  • preOrder: 先序遍历
  • findMax:获取最大节点
  • findMin:获取最小节点
function Node(key) {
    this.key = key;
    this.left = left;
    this.right = right;
}
function BST() {
    let root = null;
    this.insert = function(key) {
        let node = new Node(key);
        if(root === null) {
            root = node;  
        } else {
            root = insertNode(root, node)
        }
    }
    this.remove = function(key) {
        let node = new Node(key);
        root = removeNode(root, node)
    }
    // 搜索
    this.search = function(key) {
        return searchNode(root, key);
    }
    this.findMax = function(key) {
        return findMaxNode(root);
    }
    this.findMin = function() {
        return findMinNode(root);
    }
}
function insertNode(node, newNode) {
    if(newNode.key < node.key) {
        if(node.left === null) {
            node.left = newNode;
        } else {
            insertNode( node.left, newNode);
        }
    } else {
         if(node.right === null) {
            node.right = newNode;
        } else {
            insertNode(node.right, newNode);
        }
    }
}
function searchNode(node, key) {
    if (node === null) {
        return false;
    }
    if(node.key === key) {
        return true;
    }
    else if(node.key < key) {
        return searchNode(node.right, key);
    } else {
        return searchNode(node.left, key);
    }
}
function findMinNode(node) {
    while(node)  {
        node = node.left;
    }
    return node;
}
function findMaxNode(node) {
       while(node)  {
        node = node.right;
    }
    return node;
}
// 移除节点
function removeNode(node, newNode) {
    if(node === null) {
        return  null;
    }
    if (node.key === newNode.key) {
       if(node.left === null && node.right === null) {
            node = null;
            return node;
       }
       else if(node.left === null && node.right !== null) {
            node = node.right;
            return node;
       }
       else if (node.left !== null && node.right === null) {
            node = node.left;
            return node;
       } else {
            // 找到当前节点右子树的最小值节点,替换当前节点
            let temp = findMinNode(node.right);
            node.key = temp.key;
            node.right = removeNode(node.right, temp.key);
            return node;
       }
    } else if(node.key < newNode.key) {
        node.right = removeNode(node.right, newNode)
        return node;
    } else {
        node.left = removeNode(node.left, newNode)
        return node;
        
    }
    
}

二叉搜索树的遍历

  1. 中序遍历

中序遍历是一种以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作

function inOrder(node, callback) {
    if(node !== null) {
        inOrder(node.left)
        callback(node)
        inOrder(node.right)
    }
}
  1. 先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的

先序遍历

function preOrder(node, callback) {
    if(node !== null) {
        callback(node)
        preOrder(node.left)
        preOrder(node.right)
    }
}

3 后序遍历

后序遍历

function postOrder(node, callback) {
    if(node !== null) {
        postOrder(node.left)
        postOrder(node.right)
        callback(node)
    }
    
}