JavaScript篇（一）二叉树的插入 (附:可视化)
程序员文章站
2022-08-02 11:30:51
一、二叉树概念 二叉树（binary tree）是一颗树，其中每个节点都不能有多于两个的儿子。 字节一面，第一道就是二叉树的插入，在这里其实是对于一个二叉查找树的插入。 使二叉树成为二叉查找树的性质是，对于树中的每个节点X，它的左子树中所有项的值小于X中的项目，而它的右子树所有的项的值大于X中的项。 ......
一、二叉树概念
二叉树（binary tree）是一颗树，其中每个节点都不能有多于两个的儿子。
字节一面，第一道就是二叉树的插入，在这里其实是对于一个二叉查找树的插入。
使二叉树成为二叉查找树的性质是，对于树中的每个节点x，它的左子树中所有项的值小于x中的项目，而它的右子树所有的项的值大于x中的项。
如下图，两颗都是二叉树，左边的树是查找树，右边的树则不是。右边的树在其项为6的节点（该节点正好是根节点）的左子树中，有一个节点的项是7。
接下来我们要实现二叉树的插入：
eg: 对于[ 2, 5, 4, 1, 3, 6] =>
二、实现思路
1.实例化node节点
若根节点为空，便将newnode赋给root节点；
若根节点存在，则插入新节点。
2.插入左子树或右子树
1) 如果newnode小于node
1.如果node.left(左孩子)为空，newnode赋给node.left
2.否则再次比较newnode < node.left
2) 如果newnode大于node
1.如果node.right(右孩子)为空，newnode赋给node.right
2.否则再次比较newnode> node.right
三、代码实现
1 function binarytree(){
2 // 定义节点
3 var node = function(key){
4 this.key = key;
5 this.left = null;
6 this.right = null;
7 }
8 // 初始化根节点
9 var root = null;
10 // 插入节点
11 this.insert = function(key){
12 // 实例化node节点
13 var newnode = new node(key);
14 // 根节点为空，便将newnode赋给root节点
15 if (root === null) {
16 root = newnode;
17 } else {
18 // 根节点存在，插入新节点
19 insertnode(root, newnode);
20 };
21 }
22 // 插入节点(中序遍历)
23 var insertnode = function(node, newnode){
24 // node 当前节点
25 // newnode 新节点
26 // 若newnode小于node，则插入到node的左侧
27 if(newnode.key < node.key){
28 // 若node的左孩子为空，则插入为node的左孩子
29 if(node.left === null){
30 node.left = newnode;
31 } else {
32 // 若node的左孩子不为空，则继续去和node的左孩子比较进行插入
33 insertnode(node.left, newnode);
34 }
35 }else {
36 if(node.right === null){
37 node.right = newnode;
38 }else{
39 insertnode(node.right, newnode);
40 }
41 }
42 }
43 }
var nodes = [2, 5, 4, 1, 3, 6];
var binarytree = new binarytree(); // 将数组中的每个元素插入到二叉树中
nodes.foreach(function(key){
binarytree.insert(key);
})
附:可视化二叉树排序，更好去理解!(转至:)
<!doctype html>
<html>
<title>二叉排序树</title>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body >
<canvas id="canvas" width="1366" height="768" ></canvas>
</body>
</html>
<script type="text/javascript">
//二叉算法函数
function binarytree(){
//node 节点函数
var node=function(key){
this.key=key;
this.left=null;
this.right=null;
this.x = 0;//图形绘制坐标
this.y = 0;//图形绘制坐标
};
/**二叉树可视图形描述**/
this.graphical = [];//图形数组
this.lrmove = 100;//左右偏移量
this.udmove = 100;//上下偏移量
/**==================**/
//定义根节点
var root=null;
//插入节点 循环递归函数 左右分插
this.insertnode=function(node,newnode){
if(newnode.key < node.key){
if(node.left===null){
var x = node.x;
var y = node.y;
newnode.x = (x -= this.udmove);
newnode.y = (y += this.lrmove);
node.left=newnode;
}else{
this.insertnode(node.left,newnode);
}
}else{
if(node.right===null){
var x = node.x;
var y = node.y;
newnode.x = (x += this.udmove);
newnode.y = (y += this.lrmove);
node.right=newnode;
}else{
this.insertnode(node.right,newnode);
}
}
};
//入口程序
this.insert=function(key){
var newnode= new node(key);
if(root===null){
root=newnode;
root.x = 500;
root.y = 100;
this.graphical.push(root);
}else{
this.insertnode(root,newnode);
}
};
var inordertraversenode = function(node,callback){
if(node !== null){
inordertraversenode(node.left,callback);
callback(node.key);
inordertraversenode(node.right,callback);
}
}
this.inordertraverse = function(callback){
inordertraversenode(root,callback);
}
}
var nodes=[8,3,10,1,6,14,4,15,12,13];
var binarytree=new binarytree;
for(var i = 0 ; i < nodes.length ; i++){
binarytree.insert(nodes[i]);
}
var callback = function(key){
console.log(key)
}
binarytree.inordertraverse(callback);
/*=====================================================开始绘制================================*/
var canvas = document.getelementbyid("canvas");
var context = canvas.getcontext('2d'); //获取对应的2d对象(画笔)
function draw(key,x,y){
this.counter = 0;
this.render = function(c){
c.fillstyle = "hsl("+ this.counter +", 100%, 50%)";
c.strokestyle = '#fff'; //设置笔触的颜色
c.font = "bold 40px '字体','字体','微软雅黑','宋体'"; //设置字体
c.textbaseline = 'hanging'; //在绘制文本时使用的当前文本基线
c.filltext(key ,x ,y);
}
this.update = function(){
this.counter += 5;
}
}
var fontcavasearr = [];
function init() {
loop();//绘制文字
setinterval(run, 1000/30);
}
function run(x,y){
context.fillstyle = "rgba(0,0,0,0.1)";
context.fillrect(0,0,1366,768); //绘制 1366*768 像素的已填充矩形：
for (i=0; i<fontcavasearr.length; i++) {
var particle = fontcavasearr[i];
particle.render(context);
particle.update();
}
gline();//绘制线条
}
function loop(){
font(binarytree.graphical[0]);
}
function font(obj){
if(obj.key != null && obj.key != undefined){
var drawfont = new draw(obj.key,obj.x,obj.y);
fontcavasearr.push(drawfont);
}
if(obj.left != null && obj.left != undefined){
var drawfont = new draw(obj.left.key,obj.left.x,obj.left.y);
fontcavasearr.push(drawfont);
font(obj.left);
}
if(obj.right != null && obj.right != undefined){
var drawfont = new draw(obj.right.key,obj.right.x,obj.right.y);
fontcavasearr.push(drawfont);
font(obj.right);
}
}
function gline(){
line(binarytree.graphical[0]);
}
function line(obj){
context.linejoin="round";
context.linecap="butt";
context.beginpath();
if(obj.left != null && obj.left != undefined){
context.moveto(obj.x+20,obj.y+20);
context.lineto(obj.left.x+20,obj.left.y+20);
context.stroke();
context.closepath();
line(obj.left);
}
if(obj.right != null && obj.right != undefined){
context.moveto(obj.x+20,obj.y+20);
context.lineto(obj.right.x+20,obj.right.y+20);
context.stroke();
context.closepath();
line(obj.right);
}
}
init();
</script>
下一篇： ES6 -箭头函数 ，对象的函数解构