js实现二叉树及遍历

发表于 | 分类于

什么是二叉树

今天在做百度前端技术学院的任务时，遇到一题涉及二叉树算法的，然而我是一脸懵逼，因为没接触过二叉树算法，所以无存下手。后来上网找资料，渐渐明白了是个什么东西。

这是一篇关于二叉树的详细介绍文章

搞清楚了二叉树是啥，然后怎么实现呢，显然，我需要用js实现，于是又各种找资料，实话说，资料还挺多的，不过也很杂，现在做个总结。

js实现二叉树

说明：将一个数组的值按照二叉树规则遍历，形成二叉树结构。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

function BinaryTree(){

	//定义新节点的构造函数
	function Node(text){
		this.text = text;
		this.left = null;
		this.right = null;
	}

	//定义根节点
	var root = null;  

	//判断根节点
	this.insert = function(text){
		var newNode = new Node(text);
		if (root === null) {
			root = newNode;
		}else{
			insertNode(root,newNode);
		}
	};


	//中间节点的处理函数
	function insertNode(node,newNode){

		if (newNode.text < node.text) {
			if (node.left === null) {
				node.left = newNode;
			}else{
				insertNode(node.left,newNode);
			}
		}else{
			if (node.right === null) {
				node.right = newNode;
			}else{
				insertNode(node.right,newNode);
			}
		}

	}



//定义数组用来存储各节点的数值
var nodes = [8,3,10,1,6,14,4,7,13];

//创建二叉树实例
var binaryTree = new BinaryTree();

//遍历数组，将数组值按照二叉树规则插入
for(var i=0;i<nodes.length;i++){
	binaryTree.insert(nodes[i]);
}

上面代码最终形成的二叉树结构如下图：
二叉树结构

规则说明：

  • 根据取到的数组值，先判断二叉树中根节点是否存在，如果不存在，就将第一个值作为根节点，即上述的8是根节点值。

  • 有了根节点后，再判断后面的值与根节点值大小关系。如果小于根节点值，且左边无值，就放在左边，如果左边已经有值，就回调遍历。如果大于根节点值，且右边无值，就放在右边，如果右边已经有值，就回调遍历。参考上面代码中insertNode函数

遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历有三种方式，如下：

  1. 前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。

  2. 中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。

  3. 后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

在上述代码中的BinaryTree()中添加遍历接口（ … 表示省略的代码 ）:

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

function BinaryTree(){
    
  //...
    
    //中序遍历
	this.inOrderTraverse = function(callback){
		inOrderTraverseNode(root,callback);
	}

	function inOrderTraverseNode(node,callback){
		if(node !== null){
			inOrderTraverseNode(node.left,callback);
			callback(node.text);
			inOrderTraverseNode(node.right,callback);
		}
	}
	
  //...
  
  //定义回调函数，打印节点数值
	var callback = function(text){
		console.log(text);
	}


}


//调用
binaryTree.inOrderTraverse(callback);

//打印结果
1 3 4 6 7 8 10 13 14

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

function BinaryTree(){
    
  //...
    
    //前序遍历
	this.preOrderTraverse = function(callback){
		preOrderTraverseNode(root,callback);
	}

	function preOrderTraverseNode(node,callback){
		if (node !== null) {
			callback(node.text);
			preOrderTraverseNode(node.left,callback);
			preOrderTraverseNode(node.right,callback);
		}
	}

	
  //...
  
  //定义回调函数，打印节点数值
	var callback = function(text){
		console.log(text);
	}


}


//调用
binaryTree.preOrderTraverse(callback);

//打印结果
8 3 1 6 4 7 10 14 13

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

function BinaryTree(){
    
  //...
    
    //后序遍历
	this.postOrderTraverse = function(callback){
		postOrderTraverseNode(root,callback);
	}

	function postOrderTraverseNode(node,callback){
		if (node !== null) {
			postOrderTraverseNode(node.left,callback);
			postOrderTraverseNode(node.right,callback);
			callback(node.text);
		}
	}

	
  //...
  
  //定义回调函数，打印节点数值
	var callback = function(text){
		console.log(text);
	}


}


//调用
binaryTree.postOrderTraverse(callback);

//打印结果
1 4 7 6 3 13 14 10 8

注意：遍历代码是写在BinaryTree()中的，部分代码已省略