威尼斯wns.9778官网 > 计算机教程 > 【威尼斯wns.9778官网】javascript数据结构与算法-

原标题:【威尼斯wns.9778官网】javascript数据结构与算法-

浏览次数:140 时间:2019-07-05

6. 执行insert(99)的时候;当前的根节点23 小于 99,那么就进入else语句了,那么current值就等于如下:

斜树

示意图如下:

前序遍历:

1. 二叉树查找最小值

复制代码 代码如下:

function Node(data,left,right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
    this.getMin = getMin;
    this.getMax = getMax;
}

function insert(data) {
    var n = new Node(data,null,null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(current) {
            parent = current;
            if(data <  current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
// 中序遍历
function inOrder(node) {
    if(!(node == null)) {
        inOrder(node.left);
        console.log(node.show());
        inOrder(node.right);
    }
}

// 先序遍历 
function preOrder(node) {
    if(!(node == null)) {
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 后序遍历
function postOrder(node) {
    if(!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log("后序遍历" node.show());
    }
}

// 二叉树查找最小值
function getMin(){
    var current = this.root;
    while(!(current.left == null)) {
        current = current.left;
    }
    return current.data;
}

// 二叉树上查找最大值
function getMax() {
    var current = this.root;
    while(!(current.right == null)) {
        current = current.right;
    }
    return current.data;
}
HTML初始化如下:
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
var min = nums.getMin();
console.log(min);

var max = nums.getMax();
console.log(max);

复制代码 代码如下:

   nums.remove(23);

拥有三个结点的普通树只有两种情况:两层或者三层。但由于二叉树要区分左右,所以就会演变成如下的五种形态:

二叉树是一种特殊的树,相对较少的值保存在左节点上,较大的值保存在右节点中。这一特性使得查找的效率非常高,对于数值型和非数值型的数据,比如单词和字符串都是一样。

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

威尼斯wns.9778官网 1

二叉树的性质二:深度为k的二叉树至多有2^k-1个结点(k>=1)

if(current == null) {
    parent.left = n;
    break;
}

bool is_complete(tree *root) 

    queue q; 
    tree *ptr; 
    // 进行广度优先遍历(层次遍历),并把NULL节点也放入队列 
    q.push(root); 
    while ((ptr = q.pop()) != NULL) 
    { 
        q.push(ptr->left); 
        q.push(ptr->right); 
    } 

JS所有代码如下:

        // 有未访问到的的非NULL节点,则树存在空洞,为非完全二叉树 
        if (NULL != ptr) 
        { 
            return false; 
        } 
    } 

再执行这句代码 current = current.right; 那么current就等于null了;因此就把节点22插入到根节点为16上面的右节点上了;

二叉树的性质

function remove(data) {
    root = removeNode(this.root,data);
}
function getSmallest(node) {
   if (node.left == null) {
      return node;
   }
   else {
      return getSmallest(node.left);
   }
}
function 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;
        }
        // 有2个子节点的节点
        var tempNode = 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;
    }
}

最下层的叶子一定集中在左部连续位置。

function Node(data,left,right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
    this.getMin = getMin;
    this.getMax = getMax;
    this.find = find;
}

function insert(data) {
    var n = new Node(data,null,null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(current) {
            parent = current;
            if(data <  current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
// 中序遍历
function inOrder(node) {
    if(!(node == null)) {
        inOrder(node.left);
        console.log(node.show());
        inOrder(node.right);
    }
}

// 先序遍历 
function preOrder(node) {
    if(!(node == null)) {
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 后序遍历
function postOrder(node) {
    if(!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log("后序遍历" node.show());
    }
}

// 二叉树查找最小值
function getMin(){
    var current = this.root;
    while(!(current.left == null)) {
        current = current.left;
    }
    return current.data;
}

// 二叉树上查找最大值
function getMax() {
    var current = this.root;
    while(!(current.right == null)) {
        current = current.right;
    }
    return current.data;
}

// 查找给定值
function find(data) {
    var current = this.root;
    while(current != null) {
        if(current.data == data) {
            return current;
        }else if(data < current.data) {
            current = current.left;
        }else {
            current = current.right;
        }
    }
    return null;
}

    return true; 

遍历二叉树的方法有三种,中序,先序和后序。

复制代码 代码如下:

 

注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。

代码分析如下:

威尼斯wns.9778官网 2

就把当前的节点16插入到根节点的左节点上。

二叉树的遍历有三种方式,如下:

4. 接着执行 insert(37) 的时候,根节点不等于null,因此进入else语句中的while语句,由于37 大于根节点23,所以就进入while语句中的else语句,当前的current值为:

特殊二叉树

威尼斯wns.9778官网 3

算法如下:

威尼斯wns.9778官网 4

在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。如下图所示:

所以执行 if语句代码如下:

二叉树的遍历

威尼斯wns.9778官网 5

function getMax(){
    var current = this.root;
    while(!(current.right == null)){
        current = current.right;
    }
    return current.data;
}

所有JS代码如下:

二叉树的五种基本形态

Current = current.left 因此current = null; 继续执行上面的if语句判断是否为null的时候,因此就把37放入根节点为45的左节点上了。

完全二叉树

当执行到 current = current.left; 的时候,current的值就变为null,所以接着往下执行代码:

复制代码 代码如下:

当执行 current = current.right; 的时候 ,那么current 就等于如下:

威尼斯wns.9778官网 6

1 当执行到getMin()方法内的 var current = this.root的时候,当前的this.root的值为如下:

如果结点度为1,则该结点只有左孩子。

7. 执行 insert(22);的时候,由于根节点为23,所以节点22 小于 23,所以进入while中的if语句里面了,那么当前current值如下:

实现二叉查找树

下面是所有的JS代码:

遍历的顺序为:H I D J E B K F G C A

威尼斯wns.9778官网 7

(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。

以上是插入节点的整个流程!

若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。

赋值给current,因此current等于上面的节点。接着继续循环遍历while,执行到代码 current = current.left , current.left值变成如下:

倒数第二层,若有叶子结点,一定都在右部连续位置。

JS所有代码如下:

这时,当前节点上保存的值就是最小值

我们现在最主要的是要来学习二叉树,二叉树是一种特殊的树,它的特征是 子节点个数不超过2个。如下图就是二叉树的基本结构示意图如下:

function getMin(){
    var current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data;
}

威尼斯wns.9778官网 8

    // 判断是否还有未被访问到的节点 
    while (!q.is_empty()) 
    { 
        ptr = q.pop(); 

function Node(data,left,right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
    this.getMin = getMin;
}

function insert(data) {
    var n = new Node(data,null,null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(current) {
            parent = current;
            if(data <  current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
// 中序遍历
function inOrder(node) {
    if(!(node == null)) {
        inOrder(node.left);
        console.log(node.show());
        inOrder(node.right);
    }
}

// 先序遍历 
function preOrder(node) {
    if(!(node == null)) {
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 后序遍历
function postOrder(node) {
    if(!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log("后序遍历" node.show());
    }
}

// 二叉树查找最小值
function getMin(){
    var current = this.root;
    while(!(current.left == null)) {
        current = current.left;
    }
    return current.data;
}
测试代码初始化如下:
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
var min = nums.getMin();
console.log(min);  // 打印出3

威尼斯wns.9778官网 9

if(current == null) {
    parent.right = n;
    break;
}

二叉树的性质一:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

分析还是和上面最小值分析一个道理,这里就不分析了。

后序遍历:

威尼斯wns.9778官网 10

复制代码 代码如下:

如果待删除的节点只包含一个子节点,那么原本指向它的节点就得做点调整,使其指向它的子节点。

空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树

在二叉树上查找给定值

二叉树的特点

if(current == null) {
    parent.left = n;
    break;
}

二叉树节点定义如下:

当执行current = current.right;这句代码的时候,那么当前current = 45的那个节点(如上图所示);当再执行下面的代码:

威尼斯wns.9778官网 11

if(current == null) {
         parent.right = n;
         break;

}

(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。

function Node(data,left,right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}
function show() {
    return this.data;
}
function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}
function insert(data) {
    var n = new Node(data,null,null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(current) {
            parent = current;
            if(data <  current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
初始代码如下:
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

遍历的顺序为:H D I B E J A F K C G

因此current 不等于null,所以就执行到下一次while循环,继续进入while中的if判断,由于当前的根节点是16,所以也就进入了if里面的代码去执行,在执行这句代码后:

(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

// 先序遍历 
function preOrder(node) {
       if(!(node == null)) {
           console.log(node.show());
           preOrder(node.left);
           preOrder(node.right);
        }
}

二叉树的概念

里面使用递归的方式执行代码,当node.left == null 时候,就返回当前node节点;如下:

威尼斯wns.9778官网 12

if(current == null) {
    parent.right = n;
    break;
}

查找最大和最小值

威尼斯wns.9778官网 13

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

先序遍历打印如下:

同样结点树的二叉树,完全二叉树的深度最小。

威尼斯wns.9778官网 14

复制代码 代码如下:

截图如下:

威尼斯wns.9778官网 15

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

威尼斯wns.9778官网 16

威尼斯wns.9778官网 17

完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的。一个深度为k,节点个数为 2^k - 1 的二叉树为满二叉树(完全二叉树)。就是一棵树,深度为k,并且没有空位。

查找二叉树上的最小值与最大值非常简单,因为较小的值总是在左子节点上,在二叉树上查找最小值,只需要遍历左子树,直到找到最后一个节点。

满二叉树

威尼斯wns.9778官网 18

若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。

所有的JS代码如下:

既然顺序存储方式的适用性不强,那么我们就要考虑链式存储结构啦。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。

node.data = tempNode.data; 那么node.data = 37了;下面是node节点的截图如下:

function Node(data,left,right){
    this.data = data;
    this.left = left;//保存left节点链接
    this.right = right;
    this.show = show;
}

二:遍历二叉查找树;

如上面倒数第一副图的第2、3小图所示。

威尼斯wns.9778官网 19

二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

同时又使用递归的方式removeNode()方法;返回如下节点:

function show(){
    return this.data;//显示保存在节点中的数据
}

// 后序遍历
function postOrder(node) {
    if(!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log("后序遍历" node.show());
    }
}

该方法沿着BST的左子树挨个遍历,直到遍历到BST最左的节点,该节点被定义为:

if(current == null) {
    parent.right = n;
    break;
}

//后序遍历
function postOrder(node){
    if(!node == null){
        postOrder(node.left);
        postOrder(node.right);
        putStr(node.show() " ");
    }
}

就把99节点插入到当前的根节点为45节点的右节点了。

在BST上查找最大值只需要遍历右子树,直到找到最后一个节点,该节点上保存的值就是最大值。

威尼斯wns.9778官网 20

二叉树每个结点最多有两个孩子,所以为它设计一个数据域和两个指针域是比较自然的想法,我们称这样的链表叫做二叉链表。

威尼斯wns.9778官网 21

current.left = null;

1. 比如我现在要删除根节点为23的节点,代码初始化如下:

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点,并且结点的存储位置能体现结点之间的逻辑关系。

威尼斯wns.9778官网 22

复制代码 代码如下:

打印如下:

查找BST上的最小值和最大值非常简单,因为较小的值总是在左子节点上,在BST上查找最小值,只需遍历左子树,直到找到最后一个节点

javascript数据结构与算法-- 二叉树

二叉查找树(BST)由节点组成,所以我们定义一个Node节点对象如下:

JS代码如下:

复制代码 代码如下:

威尼斯wns.9778官网 23

查找最大值

如果待删除节点是叶子节点(没有子节点的节点),那么只需要将父节点指向它的链接指向null;

每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。

function Node(data,left,right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}

function insert(data) {
    var n = new Node(data,null,null);
    if(this.root == null) {
        this.root = n;
    }else {
        var current = this.root;
        var parent;
        while(current) {
            parent = current;
            if(data <  current.data) {
                current = current.left;
                if(current == null) {
                    parent.left = n;
                    break;
                }
            }else {
                current = current.right;
                if(current == null) {
                    parent.right = n;
                    break;
                }
            }
        }
    }
}
// 中序遍历
function inOrder(node) {
    if(!(node == null)) {
        inOrder(node.left);
        console.log(node.show());
        inOrder(node.right);
    }
}

// 先序遍历 
function preOrder(node) {
    if(!(node == null)) {
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 后序遍历
function postOrder(node) {
    if(!(node == null)) {
        postOrder(node.left);
        postOrder(node.right);
        console.log("后序遍历" node.show());
    }
}
页面初始化如下:
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log("--------------");
postOrder(nums.root);

二叉树的顺序存储结构

1. 执行insert(23)时候,由于根节点== null 所以 根节点为23.

叶子结点只能出现在最下两层。

威尼斯wns.9778官网 24

遍历的顺序为:A B D H I E J C F K G

威尼斯wns.9778官网 25

二叉链表

3. 后序:后序遍历先访问叶子节点,从左子树到右子树,再到根节点,如下所示:

完全二叉树的特点有:

威尼斯wns.9778官网 26

威尼斯wns.9778官网 27

1. 中序;

查找最小值

页面初始化 查找二叉树上的45 节点,代码初始化如下:

威尼斯wns.9778官网 28

当执行 current = current.left; 的时候,那么current值变为如下所示:

您可能感兴趣的文章:

威尼斯wns.9778官网 29

//使用递归方式实现中序遍历
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);//先访问左子树
        putstr(node.show() " ");//再访问根节点
        inOrder(node.right);//最后访问右子树
    }
}

威尼斯wns.9778官网 30

//先序遍历
function preOrder(node){
    if(!node == null){
        putstr(node.show() " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

本文由威尼斯wns.9778官网发布于计算机教程,转载请注明出处:【威尼斯wns.9778官网】javascript数据结构与算法-

关键词:

上一篇:CSS3技巧 &mdash;&mdash; 搜索框

下一篇:没有了