概念
- 有一个根节点
- 每一个节点有左右子节点
- n层二叉树最多2^n-1个节点（满二叉树）
- 完全二叉树前n-1层位满二叉树，最后一层左节点必须先于右节点存在
- 完全二叉树节点数量2^(n-1)~2^n-1
节点类型
1
2
3
4
| function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
|
前序遍历
根节点->左子树->右子树
前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca
递归实现
递归实现最简单，时间复杂度与空间复杂度为O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
| function preorderTraversal(root) {
var array=[];
if(!root) return array;
preorder(root, array);
return array;
}
function preorder(root, array) {
if(!root) return;
array.push(root.val);
preorder(root.left, array);
preorder(root.right,array);
}
|
迭代实现
用栈来存储未遍历的右节点
1
2
3
4
5
6
7
8
9
10
11
12
13
| function preorder(root) {
var array=[],stackNodes=[];
while(root || stackNodes.length) {
if(root) {
array.push(root.val);
if(root.right) stackNodes.push(root.right);
root=root.left;
} else {
root=stackNodes.pop();
}
}
return array;
}
|
Morris遍历类似利用线索二叉树，空域查找存储前驱节点来扫描，时间复杂度O(n),空间复杂度O(1)。
中序遍历
递归实现
递归实现最简单，时间复杂度与空间复杂度为O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
| function inorderTraversal(root) {
var array=[];
if(!root) return array;
preorder(root, array);
return array;
}
function inorder(root, array) {
if(!root) return;
inorder(root.left, array);
array.push(root.val);
inorder(root.right,array);
}
|
迭代实现
用栈来存储已遍历但不能输出的根节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function preorder(root) {
var array=[],stackNodes=[];
while(root || stackNodes.length) {
if(root) {
stackNodes.push(root);
root=root.left;
} else {
var topNode=stackNodes.pop();
array.push(topNode.val);
root=topNode.right;
}
}
return array;
}
|
后序遍历
递归实现
递归实现最简单，时间复杂度与空间复杂度为O(n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function preorderTraversal(root) {
var array=[];
if(!root) return array;
preorder(root, array);
return array;
}
function preorder(root, array) {
if(!root) return;
preorder(root.left, array);
preorder(root.right,array);
array.push(root.val);
}
|
迭代实现
用栈来存储未遍历的右节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function preorder(root) {
var array=[],stackNodes=[].,lastNode=null;
while(root || !array.length) {
if(root) {
stackNodes.push(root);
root=root.left;
} else {
var topNode = stackNodes[stackNodes.length-1];
if(!topNode.right && topNode.right!=lastNode) {
root=topNode.right;
} else {
stackNodes.pop();
array.push(topNode.val);
lastNode=topNode;
}
}
}
return array;
}
|
### Morris遍历
层次遍历
即每一层从左向右输出，元素需要储存有先进先出的特性，所以选用队列存储。
1
2
3
4
5
6
7
8
9
10
11
12
13
| function levelTraverse(root) {
var array=[];
if(!root) return array;
var queue=[];
queue.push(root);
while(!queue.length) {
var tmpNode = queue.shift();
array.push(tmpNode.val);
if(tmpNode.left) queue.push(tmpNode.left);
if(tmpNode.right) queue.push(tmpNode.right);
}
return array;
}
|
层次遍历构建二叉树
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
| //[123#56#] '#'means empty node
function levelCreateBinaryTree(arr) {
if(!arr.length) return null;
//use queue to store the uncreated node
var queue=[];
var root=new TreeNode(arr.shift());
queue.push(root);
var p;
while(queue.length) {
var leftValue=arr.shift();
var rightValue=arr.shift();
p = queue.shift();
if(leftValue && rightValue && leftValue != '#' && rightValue !='#') {
p.left=new TreeNode(leftValue);
p.right=new TreeNode(rightValue);
queue.push(p.left);
queue.push(p.right);
} else if((leftValue===undefined || leftValue=='#') && rightValue && rightValue!='#'){
p.right=new TreeNode(rightValue);
queue.push(p.right);
} else if(leftValue && leftValue!='#' && (rightValue=='#' || rightValue===undefined)){
p.left=new TreeNode(leftValue);
queue.push(p.left);
}
}
return root;
}
|
二叉树打印
1
2
3
4
5
6
7
8
9
| function printBinaryTree(root, prefix, isTail) {
console.log(prefix,isTail?"└──":"├──",root.val);
if(root.left && root.right) {
printBinaryTree(root.left,prefix+(isTail?" ":" | "),false);
printBinaryTree(root.right,prefix+(isTail?" ":" | "),true);
} else if(root.left) {
printBinaryTree(root.left,prefix+(isTail?" ":" | "),true);
}
}
|
二叉树查找
归根究底也是一种遍历
1
2
3
4
5
6
| function searchBinaryTree(root,val) {
if(！root) return null;
if(root.val==val) return root;
return searchBinaryTree(root.left,val)?searchBinaryTree(root.left,val):searchBinaryTree(root.right,val);
}
|
二叉树节点数量统计
1
2
3
4
5
| function countBinaryTree(root,val) {
if(！root) return 0;
return countBinaryTree(root.left)+countBinaryTree(root.right)+1;
}
|
二叉树比较
1
2
3
4
5
6
7
8
9
| function isEqual(root1,root2) {
if(!root1 && !root2) return true;
if(root1 && root2 && root1.val==root2.val) {
if(isEqual(root1.left, root2.left) && isEqual(root1.right,root2.right)) {
return true;
}
}
return false;
}
|
二叉树深度
1
2
3
4
5
6
7
8
| function depthOfTree(root) {
if(!root) return 0;
var depth,leftH,rightH;
leftH = depthOfTree(root.left);
rightH = depthOfTree(root.right);
depth = Math.max(leftH,rightH)+1;
return depth;
}
|
二叉查找树
Binary Search Tree(BST) 对于每个节点，其值大于或等于左孩子，小于等于右孩子。其中序遍历是有序的。BST的查找操作平均复杂度O(lgn)，最坏情况O(n)，故引申出一些平衡搜索树结构：红黑树、AVL、B树等。