时间:2021-05-26
前言:
二叉树的特点(例图只是二叉树的一种情况,不要尝试用例图推理以下结论)
最下面一层的节点称为叶子节点,他们没有子节点;
左子节点的值 < 父节点的值 <= 右节点的值
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对象
BST对象
插入节点函数
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
前言:紧接着上篇二叉树的javascript实现,来说一下二叉树的遍历。本次一本正经的胡说八道,以以下这个二叉树为例子进行遍历:接着是要引入二叉树实现的代码:f
一、获取二叉树的深度就是二叉树最后的层次,如下图:实现代码:复制代码代码如下:defgetheight(self):'''获取二叉树深度'''returnsel
JavaScript中的搜索二叉树实现,供大家参考,具体内容如下二叉搜索树(BST,BinarySearchTree),也称二叉排序树或二叉查找树二叉搜索树是一
问题如何遍历一个二叉树遍历二叉树就是访问二叉树的每一个节点二叉树父结点下先左访问,先序遍历(根左右)例如:遍历以下的二叉树遍历结果:ABDECFPython代码
什么是二叉树,这里不再介绍,可以自行百度:二叉树。在这里利用java实现“表达式二叉树”。表达式二叉树的定义第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表