天天看點
傳回

算法(平衡二叉樹)

科普二叉樹

二叉樹

二叉數是每個節點最多有兩個子樹,或者是空樹(n=0),或者是由一個根節點及兩個互不相交的,分别稱為左子樹和右子樹的二叉樹組成

滿二叉樹

有兩個非空子樹(二叉樹中的每個結點恰好有兩個孩子結點切所有葉子結點都在同一層)

也就是一個結點要麼是葉結點，要麼是有兩個子結點的中間結點。

深度為k且含有2^k-1個結點的二叉樹

完全二叉樹

從左到右依次填充

從根結點開始，依次從左到右填充樹結點。

除最後一層外，每一層上的所有節點都有兩個子節點，最後一層都是葉子節點。

平衡二叉樹

AVL樹

[3,1,2,5,9,7]

首先科普下二叉排序樹又稱二叉查找樹,議程二叉搜尋樹

二叉排序樹的規則

比本身大放右邊,比本身小放左邊

算法(平衡二叉樹)
平衡二叉數
  • 首先是一個二叉排序樹
  • 左右兩個子樹的高度差不大于1
下面圖中是平衡的情況
算法(平衡二叉樹)
下面是不平衡的情況
算法(平衡二叉樹)
引入公式
算法(平衡二叉樹)
(LL)右旋 
function toateRight(AvlNode){
    let node=AvlNode.left;//儲存左節點
    AvlNode.left=node.right;
    node.right=AvlNode;    
}
算法(平衡二叉樹)
算法(平衡二叉樹)
算法(平衡二叉樹)
(RR)左旋 
function roateLeft(AvlNode){
    let node=AvlNode.right;//儲存右子節點
    AvlNode.right=node.left;
    node.left=AvlNode;
    return node;
}
算法(平衡二叉樹)
算法(平衡二叉樹)
算法(平衡二叉樹)
左右旋
算法(平衡二叉樹)

大圖

算法(平衡二叉樹)

判斷二叉樹是不是平衡樹

二叉樹任意結點的左右子樹的深度不超過1

深度計算

定義一個初始化的二叉樹
var nodes = {
  node: 6,
  left: {
    node: 5, 
    left: { 
      node: 4 
    }, 
    right: { 
      node: 3 
    }
  },
  right: { 
    node: 2, 
    right: { 
      node: 1 
    } 
  }
}
           
//計算高度
const treeDepth = (root) => {
  if (root == null) {
    return 0;
  }
  let left = treeDepth(root.left)
  let right = treeDepth(root.right)
 return 1+(left>right?left:right)
}
//判斷深度
const isTree=(root)=>{
  if (root == null) {
    return true;
  }
  let left=treeDepth(root.left)
  let right=treeDepth(root.right)
  let diff=left-right;
  if (diff > 1 || diff < -1) {
    return false
  }
  return isTree(root.left)&&isTree(root.right)
}
console.log(isTree(nodes))

判斷二叉數是不是搜尋二叉樹 

//第一種 //中序周遊
let last=-Infinity;
const isValidBST=(root)=>{
  if (root == null) {
    return true;
  }
  //先從左節點開始
  if (isValidBST(root.left)) {
    if (last < root.node) {
      last=root.node;
      return isValidBST(root.right)
    }
  }
  return false
}
console.log(isValidBST(nodes))

//第二種
const isValidBST = root => {
  if (root == null) {
    return true
  }
  return dfs(root, -Infinity, Infinity)
}
const dfs = (root, min, max) => {
  if (root == null) {
    return true
  }
  if (root.node <= min || root.node >= max) {
    return false
  }
  return dfs(root.left, min, root.node) && dfs(root.right, root.node, max)
}
console.log(isValidBST(nodes))

實作一個二叉樹

實作了二叉樹的添加,删除,查找,排序 
//二叉樹結點
class TreeNode {
    constructor(n, left, right){
        this.n = n;
        this.left = left;
        this.right = right;
    }
}
//二叉樹
class BinaryTree {
    constructor(){
        this.length = 0;
        this.root = null;
        this.arr = [];
    }
    //添加對外入口，首個參數是數組，要求數組裡都是數字，如果有不是數字則試圖轉成數字，如果有任何一個無法強制轉成數字，則本操作無效
    addNode(){
        let arr = arguments[0];
        if(arr.length == 0) return false;
        return this.judgeData(\'_addNode\', arr)
    }
    //删除結點
    deleteNode(){
        let arr = arguments[0];
        if(arr.length == 0) return false;
        return this.judgeData(\'_deleteNode\', arr)
    }
    //傳值判斷，如果全部正确，則全部加入叉樹
    judgeData(func, arr){
        let flag = false;
        //任何一個無法轉成數字，都會失敗
        if(arr.every(n => !Number.isNaN(n))){
            let _this = this;
            arr.map(n => _this[func](n));
            flag = true;
        }
        return flag;
    }
    //添加的真實實作
    _addNode(n){
        n = Number(n);
        let current = this.root;
        let treeNode = new TreeNode(n, null, null);
        if(this.root === null){
            this.root = treeNode;
        }
        else {
            current = this.root;
            while(current){
                let parent = current;
                if(n < current.n){
                    current = current.left;
                    if(current === null){
                        parent.left = treeNode;
                    }
                }
                else {
                    current = current.right;
                    if(current === null){
                        parent.right = treeNode;
                    }
                }
            }
        }
        this.length++;
        return treeNode;
    }
    //删除節點的真實實作
    _deleteNode(n){
        n = Number(n);
        if(this.root === null){
            return;
        }
        //查找該節點，删除節點操作比較複雜，為排除找不到被删除的節點的情況，簡化代碼，先保證該節點是存在的，雖然這樣做其實重複了一次查詢了，但二叉樹的查找效率很高，這是可接受的
        let deleteNode = this.findNode(n);
        if(!deleteNode){
            return;
        }
        //如果删除的是根節點
        if(deleteNode === this.root){
            if(this.root.left === null && this.root.right === null){
                this.root = null;
            }
            else if(this.root.left === null){
                this.root = this.root.right;
            }
            else if(this.root.right === null){
                this.root = this.root.left;
            }
            else {
                let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);
                replacePNode[rp] = null;
                replaceNode.left = this.root.left;
                replaceNode.right = this.root.right;
                this.root = replaceNode;
            }
        }
        else {
            //被删除的父節點，子節點在父節點的位置p，有left,right兩種可能
            let [deleteParent, p] = this.findParentNode(deleteNode);
            if(deleteNode.left === null && deleteNode.right === null){
                deleteParent[p] = null;
            }
            else if(deleteNode.left === null){
                deleteParent[p] = deleteNode.right;
            }
            else if(deleteNode.right === null){
                deleteParent[p] = deleteNode.left;
            }
            else {
                //用來替換被删除的節點，父節點，節點在父節點的位置
                let [replaceNode, replacePNode, rp] = this.findLeftTreeMax(deleteNode);
                if(replacePNode === deleteNode){
                    deleteParent[p] = replaceNode;
                }
                else {
                    deleteParent[p] = replaceNode;
                    replacePNode.right = null;
                }
                replacePNode[rp] = null;
                replaceNode.left = deleteNode.left;
                replaceNode.right = deleteNode.right;
            }
        }
        this.length--;
    }
    //查找
    findNode(n){
        let result = null;
        let current = this.root;
        while(current){
            if(n === current.n){
                result = current;
                break;
            }
            else if(n < current.n){
                current = current.left;
            }
            else {
                current = current.right;
            }
        }
        return result;
    }
    //查找父節點
    findParentNode(node){
        let [parent, child, p] = [null, null, null];
        if(this.root !== node){
            parent = this.root;
            if(node.n < parent.n){
                child = parent.left;
                p = \'left\';
            }
            else {
                child = parent.right;
                p = \'right\';
            }
            while(child){
                if(node.n === child.n){
                    break;
                }
                else if(node.n < child.n){
                    parent = child;
                    child = parent.left;
                    p = \'left\';
                }
                else {
                    parent = child;
                    child = parent.right;
                    p = \'right\';
                }
            }
        }
        return [parent, p];
    }
    //查找目前有左子樹的節點的最大值的節點M，如有A個節點被删除，M是最接近A點之一（還有一個是右子樹節點的最小值）
    findLeftTreeMax(topNode){
        let [node, parent, p] = [null, null, null];
        if(this.root === null || topNode.left === null){
            return [node, parent, p];
        }
        parent = topNode;
        node = topNode.left;
        p = \'left\';
        while(node.right){
            parent = node;
            node = node.right;
            p = \'right\';
        }
        return [node, parent, p];
    }
    //查找最大值
    maxValue(){
        if(this.root !== null){
            return this._findLimit(\'right\');
        }
    }
    //查找最小值
    minValue(){
        if(this.root !== null){
            return this._findLimit(\'left\');
        }
    }
    //實作查找特殊值
    _findLimit(pro){
        let n = this.root.n;
        let current = this.root;
        while(current[pro]){
            current = current[pro];
            n = current.n;
        }
        return n;
    }
    //中序排序,并用數組的形式顯示
    sortMiddleToArr(){
        this._sortMiddleToArr(this.root);
        return this.arr;
    }
    //中序方法
    _sortMiddleToArr(node){
        if(node !== null){
            this._sortMiddleToArr(node.left);
            this.arr.push(node.n);
            this._sortMiddleToArr(node.right);
        }
    }
    //列印二叉樹對象
    printNode(){
        console.log(JSON.parse(JSON.stringify(this.root)));
    }
}
//測試
var binaryTree = new BinaryTree();
binaryTree.addNode([50, 24, 18, 65, 4, 80, 75, 20, 37, 40, 60]);
binaryTree.printNode();//{n: 50, left: {…}, right: {…}}
console.log(binaryTree.maxValue());//80
console.log(binaryTree.minValue());//4
console.log(binaryTree.sortMiddleToArr());// [4, 18, 20, 24, 37, 40, 50, 60, 65, 75, 80]
binaryTree.deleteNode([50]);
binaryTree.printNode();//{n: 40, left: {…}, right: {…}}

排序複習 

function ArrayList() {
        this.array = [];
    }
    ArrayList.prototype = {
        constructor: ArrayList,
        insert: function(item) {
            this.array.push(item);
        },
        toString: function() {
            return this.array.join();
        },
        swap: function(index1, index2) {
            var aux = this.array[index2];
            this.array[index2] = this.array[index1];
            this.array[index1] = aux;
        },
        //冒泡排序
        bubbleSort: function() {
            var length = this.array.length;
            for (var i = 0; i < length; i++) {
                for (var j = 0; j < length - 1 - i; j++) {
                    if (this.array[j] > this.array[j + 1]) {
                        this.swap(j, j + 1);
                    }
                }
            }
        },
        //選擇排序
        selectionSort: function() {
            var length = this.array.length;
            var indexMin;
            for (var i = 0; i < length - 1; i++) {
                indexMin = i;
                for (var j = i; j < length; j++) {
                    if (this.array[indexMin] > this.array[j]) {
                        indexMin = j;
                    }
                }
                if (indexMin !== i) {
                    this.swap(indexMin, i);
                }
            }
        },
        //插入排序
        insertionSort: function() {
            var length = this.array.length;
            var j;
            var temp;
            for (var i = 1; i < length; i++) {
                temp = this.array[i];
                j = i;
                while (j > 0 && this.array[j - 1] > temp) {
                    this.array[j] = this.array[j - 1];
                    j--;
                }
                this.array[j] = temp;
            }
        },
        //歸并排序
        mergeSort: function() {
            function mergeSortRec(array) {
                var length = array.length;
                if (length === 1) {
                    return array;
                }
                var mid = Math.floor(length / 2);
                var left = array.slice(0, mid);
                var right = array.slice(mid, length);
                return merge(mergeSortRec(left), mergeSortRec(right));
            }

            function merge(left, right) {
                var result = [];
                var il = 0;
                var ir = 0;
                while (il < left.length && ir < right.length) {
                    if (left[il] < right[ir]) {
                        result.push(left[il++]);
                    } else {
                        result.push(right[ir++]);
                    }
                }
                while (il < left.length) {
                    result.push(left[il++]);
                }
                while (ir < right.length) {
                    result.push(right[ir++]);
                }
                return result;
            }
            this.array = mergeSortRec(this.array);
        },
        //快速排序
        quickSort:function(){
            function sort(array){
                if (array.length <= 1) {
                    return array;
                }
                var pivotIndex = Math.floor(array.length/2);
                var pivot = array.splice(pivotIndex,1)[0];
                var left = [];
                var right = [];
                for(var i = 0; i < array.length; i++){
                    if (array[i] < pivot) {
                        left.push(array[i]);
                    }else{
                        right.push(array[i]);
                    }
                }
                return sort(left).concat([pivot],sort(right));
            }

            this.array = sort(this.array);
        }
    };

...................................................................................................................###############################################################################################################################################################

上一篇: vb與vb.net有什麼差別？學過vb後，vb.net是不是就很好學了？
下一篇: 資料結構之 平衡二叉樹 from https://www.cnblogs.com/zhujunxxxxx/p/3348798.html