前言:
二叉树的特点(例图只是二叉树的一种情况,不要尝试用例图推理以下结论)
- 除了最下面一层,每个节点都是父节点,每个节点都有且最多有两个子节点;
- 除了嘴上面一层,每个节点是子节点,每个节点都会有一个父节点;
- 最上面一层的节点(即例图中的节点50)为根节点;
最下面一层的节点称为叶子节点,他们没有子节点;
左子节点的值 < 父节点的值 <= 右节点的值
1 节点的javascript实现
function show() {
return this.data;
}
return this.data;
}
感受下上面实现节点的代码,感觉和链表有点相似不是吗,存着当前值,又存着下个节点(左、右子节点)的引用,下面是一张伪代码的草图:
2 二叉树的实现
实现二叉树,当然就是要插入节点构成二叉树,先看看实现二叉树的js代码
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;
}
}
}
}
}
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 insert(data) {
// 初始化一个节点,为什么要将左右子节点的引用初始化为空呢,因为可能是叶子节点,加入他有子节点,会在下面的代码添加
var n = new Node(data,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;
}
// 初始化一个节点,为什么要将左右子节点的引用初始化为空呢,因为可能是叶子节点,加入他有子节点,会在下面的代码添加
var n = new Node(data,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;
}
// 其实上面这样写不好理解,可以等价于下面的<a href="/tag/daima/" target="_blank" class="keywords">代码</a>:
// start
if(current.left == null){ // 若果左节点空,那么这个空的节点就是我们要插入的位置
current.left = n;
break;
}else{
// 不空则继续往下一层找空节点(插入的位置)
current = current.left;
}
// end
}
else {
// 右节点的逻辑<a href="/tag/daima/" target="_blank" class="keywords">代码</a>个左节点的一样的
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
}
下面是一个更好理解的插入函数
小结:
二叉树的实现的三个部件
Node对象
BST对象
插入节点函数