您好,登录后才能下订单哦!
本篇文章给大家分享的是有关关于JavaScript二叉树的详细介绍,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。
可能有一部分人没有读过我上一篇写的二叉堆,所以这里把二叉树的基本概念复制过来了,如果读过的人可以忽略前面针对二叉树基本概念的介绍,另外如果对链表数据结构不清楚的最好先看一下本人之前写的js数据结构-链表
二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。
根节点:二叉树最顶层的节点
分支节点:除了根节点以外且拥有叶子节点
叶子节点:除了自身,没有其他子节点
常用术语
在二叉树中,我们常常还会用父节点和子节点来描述,比如图中2为6和3的父节点,反之6和3是2子节点
在二叉树的第i层上,至多有2^i-1个节点
i=1时,只有一个根节点,2^(i-1) = 2^0 = 1
深度为k的二叉树至多有2^k-1个节点
i=2时,2^k-1 = 2^2 - 1 = 3个节点
对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1
树的节点个数至少为1,而二叉树的节点个数可以为0
树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为2
树的节点没有左右之分,而二叉树的节点有左右之分
二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)
满二叉树:一棵深度为k且有2^k - 1个节点的二叉树称为满二叉树
完全二叉树:完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)
二叉搜索树满足以下的几个性质:
若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也需要满足左边小右边大的性质
我们来举个例子来深入理解以下
一组数据:12,4,18,1,8,16,20
由下图可以看出,左边的图满足了二叉树的性质,它的每个左子节点都小于父节点,右子节点大于其父节点,同时左子树的节点都小于根节点,右子树的节点都大于根节点
二叉搜索树主要的几个操作:
查找(search)
插入(insert)
遍历(transverse)
通过下图,可以知道二叉搜索树的节点通常包含4个域,数据元素,分别指向其左,右节点的指针和一个指向父节点的指针所构成,一般把这种存储结构称为三叉链表。
cdn.segmentfault.com/v-5c2db555/global/img/squares.svg">
用代码初始化一个二叉搜索树的结点:
一个指向父亲节点的指针 parent
一个指向左节点的指针 left
一个指向右节点的指针 right
一个数据元素,里面可以是一个key和value
class BinaryTreeNode { constructor(key, value){ this.parent = null; this.left = null; this.right = null; this.key = key; this.value = value; } }
接着我们再用代码去初始化一个二叉搜索树
在二叉搜索树中我们会维护一个root指针,这个就相当于链表中的head指针,在没有任何节点插入的时候它指向空,在有节点插入以后它指向根节点。
class BinarySearchTree { constructor() { this.root = null; } }
static createNode(key, value) { return new BinarySearchTree(key, value); }
看下面这张图,13是我们要插入的节点,它插入的具体步骤:
跟根节点12做比较,比12大,所以我们确定了,这个节点是往右子树插入的
而根节点的右边已经有节点,那么跟这个节点18做比较,结果小于18所以往18的左节点找位置
而18的左节点也已经有节点了,所以继续跟这个节点做比较,结果小于16
刚好16的左节点是空的(left=null),所以13这个节点就插入到了16的左节点
通过上面的描述,我们来看看代码是怎么写的
定义两个指针,分别是p和tail,最初都指向root,p是用来指向要插入的位置的父节点的指针,而tail是用来查找插入位置的,所以最后它会指向null,用上图举个例子,p最后指向了6这个节点,而tail最后指向了null(tail为null则说明已经找到了要插入的位置)
循环,tail根据我们上面分析的一步一步往下找位置插入,如果比当前节点小就往左找,大则往右找,一直到tail找到一个空位置也就是null
如果当前的root为null,则说明当前结构中并没有节点,所以插入的第一个节点直接为跟节点,即this.root = node
将插入后的节点的parent指针指向父节点
insert(node){ let p = this.root; let tail = this.root; // 循环遍历,去找到对应的位置 while(tail) { p = tail; // 要插入的节点key比当前节点小 if (node.key < tail.key){ tail.left = tail.left; } // 要插入的节点key比当前节点大 else { tail.right = tail.right; } } // 没有根节点,则直接作为根节点插入 if(!p) { this.root = node; return; } // p是最后一个节点,也就是我们要插入的位置的父节点 // 比父节点大则往右边插入 if(p.key < node.key){ p.right = node; } // 比父节点小则往左边插入 else { p.left = node; } // 指向父节点 node.parent = p; }
查找就很简单了,其实和插入差多,都是去别叫左右节点的大小,然后往下找
如果root = null, 则二叉树中没有任何节点,直接return,或者报个错什么的。
循环查找
search(key) { let p = this.root; if(!p) { return; } while(p && p.key !== key){ if(p.key<key){ p = p.right; }else{ p = p.left; } } return p; }
中序遍历(inorder):先遍历左节点,再遍历自己,最后遍历右节点,输出的刚好是有序的列表
前序遍历(preorder):先自己,再遍历左节点,最后遍历右节点
后序遍历(postorder):先左节点,再右节点,最后自己
最常用的一般是中序遍历,因为中序遍历可以得到一个已经排好序的列表,这也是为什么会用二叉搜索树排序的原因
根据上面对中序遍历的解释,那么代码就变的很简单,就是一个递归的过程,递归停止的条件就是节点为null
先遍历左节点-->yield* this._transverse(node.left)
遍历自己 --> yield* node
遍历左节点 --> yield* this._transverse(node.right)
transverse() { return this._transverse(this.root); } *_transverse(node){ if(!node){ return; } yield* this._transverse(node.left); yield node; yield* this._transverse(node.right) }
看上面这张图,我们简化的来看一下,先访问左节点4,再自己12,然后右节点18,这样输出的就刚好是一个12,4,8
补充:这个地方用了generater,所以返回的一个迭代器。可以通过下面这种方式得到一个有序的数组,这里的前提就当是已经有插入的节点了
const tree = new BinaryTree(); //...中间省略插入过程 // 这样就返回了一个有序的数组 var arr = [...tree.transverse()].map(item=>item.key);
class BinaryTreeNode { constructor(key, value) { // 指向父节点 this.p = null; // 左节点 this.left = null; // 右节点 this.right = null; // 键 this.key = key; // 值 this.value = value; } } class BinaryTree { constructor() { this.root = null; } static createNode(key, value) { return new BinaryTreeNode(key, value); } search(key) { let p = this.root; if (!p) { return; } while (p && p.key !== key) { if (p.key < key) { p = p.right; } else { p = p.left; } } return p; } insert(node) { // 尾指针的父节点指针 let p = this.root; // 尾指针 let tail = this.root; while (tail) { p = tail; if (node.key < tail.key) { tail = tail.left; } else { tail = tail.right; } } if (!p) { this.root = node; return; } // 插入 if (p.key < node.key) { p.right = node; } else { p.left = node; } node.p = p; } transverse() { return this.__transverse(this.root); } *__transverse(node) { if (!node) { return; } yield* this.__transverse(node.left); yield node; yield* this.__transverse(node.right); } }
二叉查找树就讲完了哈,其实这个和链表很像的,还是操作那么几个指针,既然叫查找树了,它主要还是用来左一些搜索,还有就是排序了,另外补充一下,二叉查找树里找最大值和最小值也很方便是不是,如果你大致读懂了的话。
以上就是关于JavaScript二叉树的详细介绍,小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。