189 8069 5689
小编给大家分享一下javascript如何实现二叉树，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！
前言：
二叉树的特点(例图只是二叉树的一种情况，不要尝试用例图推理以下结论)
除了最下面一层，每个节点都是父节点，每个节点都有且最多有两个子节点；
除了嘴上面一层，每个节点是子节点，每个节点都会有一个父节点；
最上面一层的节点（即例图中的节点50）为根节点；
最下面一层的节点称为叶子节点，他们没有子节点；
左子节点的值 < 父节点的值 <= 右节点的值
1 节点的javascript实现
// 节点对象
function Node(data, left, right) {
this.data = data; // 节点值
this.left = left; // 当前节点的左子节点
this.right = right; // 当前节点的右子节点
this.show = show; // 辅助function
}
function show() {
return this.data;
}感受下上面实现节点的代码，感觉和链表有点相似不是吗，存着当前值，又存着下个节点（左、右子节点）的引用，下面是一张伪代码的草图：
2 二叉树的实现
实现二叉树，当然就是要插入节点构成二叉树，先看看实现二叉树的js代码
function BST() {
this.root = null;
this.insert = insert;
}
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 (true) {
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 BST() {
this.root = null; // 根节点
this.insert = insert;
}
function insert(data) {
// 初始化一个节点，为什么要将左右子节点的引用初始化为空呢，因为可能是叶子节点，加入他有子节点，会在下面的代码添加
var n = new Node(data, null, null);
if (该二叉树是否为空，是空则根节点为空，因此可以用根节点判断二叉树是否为空) {
// 将当前节点存为根节点
this.root = n;
}
else {
// 来到这里就表示，该二叉树不为空，这里关键的是两句代码：
// 0.while (true);
// 1.parent = current；
// 2.current = current.left;/current = current.right;
// 3.break;
var current = this.root;
var parent;
while (true) {
parent = current; // 获得父节点，第一次循环，那么父节点就是根节点
if (data < current.data) { // 当前节点值小于父节点的值就是存左边，记得二叉树的特点吧，如果真是小于父节点，那么就说明该节点属于，该父节点的左子树。
current = current.left;
if (current == null) {
parent.left = n;
break;
}
// 其实上面这样写不好理解，可以等价于下面的代码：
// start
if(current.left == null){ // 若果左节点空，那么这个空的节点就是我们要插入的位置
current.left = n;
break;
}else{
// 不空则继续往下一层找空节点（插入的位置）
current = current.left;
}
// end
}
else {
// 右节点的逻辑代码个左节点的一样的
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}下面是一个更好理解的插入函数
function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
// start change
while (true) {
if (data < current.data) {
if (current.left == null) {
current.left = n;
break;
}else{
current = current.left;
}
}else {
if (current.right == null) {
current.right = n;
break;
}else{
current = current.right;
}
}
}
}
}小结：
二叉树的实现的三个部件
Node对象
function Node(data, left, right) { ... }BST对象
function BST() { ... }插入节点函数
function insert(data) { ... }以上是“javascript如何实现二叉树”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注创新互联网站建设公司行业资讯频道！
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。