Biegral Blog

1、二叉树

(1)前序遍历

var nodes = [];
function preOrder(node) {
	if (node != null) {
		nodes.push(node);
		preOrder(node.firstElementChild);
		// 在页面中展现一颗二叉树的结构，但需要考虑某些div只有一个子节点的情况
		if (node.firstElementChild != node.lastElementChild) 
			preOrder(node.lastElementChild);
	}
}

(2)中序遍历

var nodes = [];
function inOrder(node) {
	if (node != null) {
		inOrder(node.firstElementChild);
		nodes.push(node);
		if (node.firstElementChild != node.lastElementChild)
			inOrder(node.lastElementChild);
	}
}

(3)后序遍历

var nodes = [];
function postOrder(node) {
	if (node != null) {
		postOrder(node.firstElementChild);
		if (node.firstElementChild != node.lastElementChild)
			postOrder(node.lastElementChild);
		nodes.push(node);
	}
}

2、多叉树

(1)深度优先遍历

1)递归

var nodes = [];
function deepTraversal(node) {
	if (node != null) {  
        nodes.push(node);  
        var children = node.children;  
        for (var i = 0; i < children.length; i++)  
            deepTraversal(children[i]);  
    }  
}

2)非递归

var nodes = [];
function deepTraversal(node) {
	if (node != null) {
		var stack = [];
		stack.push(node);
		while (stack.length != 0) {
			var item = stack.pop();
			nodes.push(item);
			var children = item.children;
			for (var i = children.length - 1; i >= 0; i--)
				stack.push(children[i]);
		}
	}  
}

(2)广度优先遍历

1)递归

var nodes = [];
function wideTraversal(node) {
	var i = 0;
	if (!(node == null)) {
		nodes.push(node);
		wideTraversal(node.nextElementSibling);
		node = nodes[i++];
		wideTraversal(node.firstElementChild);
	}
}

报错：Maximum call stack size exceeded(…)

2)非递归

var nodes = [];
function wideTraversal(selectNode) {
	if (selectNode != null) {
		var queue = [];
		queue.unshift(selectNode);
		while (queue.length != 0) {
			var item = queue.shift();
			nodes.push(item);
			var children = item.children;
			for (var i = 0; i < children.length; i++)
				queue.push(children[i]);
		}
	}
}