数据结构与算法-二叉树

数据结构与算法-二叉树及二叉搜索树

1.建立二叉树

在做二叉树的leetcode算法题中,会发现没有本地环境,如何搭建二叉树的本地环境(JavaScript)。

首先建立Tree,在其中定义节点构造方法以及生成树的函数方法。

function Tree() {
    let Node = function (val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
    Tree.prototype.createTree = function () {
        let root = new Node(1);
        root.left = new Node(null);
        root.right = new Node(2);
        root.right.left = new Node(3);
        return root;
    }
}
数据结构与算法-二叉树

2.建立二叉搜索树

使用javascript建立二叉搜索树(左子树都比根节点要小,右子树都比根节点要大,且子节点也满足上述条件)

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

二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势

function tree() {
    //tree内部的函数对象(节点结构),链表来表示节点
    function Node(val) {
        this.val = val
        this.left = null
        this.right = null
    }
    //根节点初始值为null
    this.root = null
    //添加插入节点的功能
    tree.prototype.insert = function (val) {
        var newNode = new Node(val)
        //判断节点是否有值(insertNode)
        this.root == null ? this.root = newNode : this.insertNode(this.root, newNode)
    }
    tree.prototype.insertNode = function (node, newnode) {
        if (newnode.val < node.val) {
            //上一层的链表保存Node
            node.left == null ? node.left = newnode : this.insertNode(node.left, newnode)
        } else {
            node.right == null ? node.right = newnode : this.insertNode(node.right, newnode)
        }
    }
}
完成上述功能(产生一个树)
//test insert
var bst = new tree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
console.log(bst)
console.log(bst.root)
数据结构与算法-二叉树

3.二叉搜索树的前中后序遍历(递归解法)

var root = bst.root
var Arr1 = []

//前序遍历
function preorderTraversal(root) {
    if (!root) return Arr1;
    Arr1.push(root.val);
    preorderTraversal(root.left)
    preorderTraversal(root.right)
    return Arr1;
};

var Arr2 = []
//中序遍历
var inorderTraversal = function (root) {
    if (!root) return Arr2;
    inorderTraversal(root.left);
    Arr2.push(root.val);
    inorderTraversal(root.right);
    return Arr2;
};


var Arr3 = []
//后序遍历
var postorderTraversal = function (root) {
    if (!root) return Arr3;
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    Arr3.push(root.val);
    return Arr3;
};
preorderTraversal(root)
console.log(Arr1)


inorderTraversal(root)
console.log(Arr2)

postorderTraversal(root)
console.log(Arr3)

//结果如下
[
  11,  7,  5, 15,
  13, 12, 14, 20
]
[
   5,  7, 11, 12,
  13, 14, 15, 20
]
[
   5,  7, 12, 14,
  13, 20, 15, 11
]

前序遍历:[11, 7, 5, 15,13, 12, 14, 20]
中序遍历:[5, 7, 11, 12,13, 14, 15, 20]
后序遍历:[5, 7, 12, 14,13, 20, 15, 11]

4.参考

介绍二叉树以及二叉树的前中后序遍历

上一篇:bibtex4word 插入参考文献


下一篇:[数据结构] python 二叉搜索树(BST树)的插入