二叉 DOM 树的遍历
[javascript] view plain copy print?
- function Tree() {
- var Node = function(key){
- this.key = key;
- this.left = null;
- this.right = null;
- }
- root =null;
- }
- function Tree() {
- var Node = function(key){
- this.key = key;
- this.left = null;
- this.right = null;
- }
- root =null;
- }
前序遍历
首先访问根结点, 然后遍历左子树, 最后遍历右子树
[javascript] view plain copy print ?
- Tree.prototype.preOrderTraverse = function(callback){
- preOrder(root, callback);
- }
- var preOrder = function(node,callback){
- if(node !== null){
- callback(node.key);
- preOrder(node.left, callback);
- preOrder(node.right, callback);
- }
- }
- Tree.prototype.preOrderTraverse = function(callback){
- preOrder(root, callback);
- }
- var preOrder = function(node,callback){
- if(node !== null){
- callback(node.key);
- preOrder(node.left, callback);
- preOrder(node.right, callback);
- }
- }
修改为 DOM 二叉树:
[javascript] view plain copy print?
- var preOrder = function(node,callback) {
- callback(node);
- if(node.firstElementChild) {// 先判断子元素节点是否存在
- this.preOrder(node.firstElementChild,callback);
- }
- if(node.lastElementChild) {
- this.preOrder(node.lastElementChild,callback);
- }
- };
- var preOrder = function(node,callback) {
- callback(node);
- if(node.firstElementChild) {// 先判断子元素节点是否存在
- this.preOrder(node.firstElementChild,callback);
- }
- if(node.lastElementChild) {
- this.preOrder(node.lastElementChild,callback);
- }
- };
中序遍历
首先遍历左子树, 然后访问根结点, 最后遍历右子树.
[javascript] view plain copy print ?
- Tree.prototype.inOrderTraverse = function(callback){
- inOrder(root, callback);
- }
- var inOrder = function(node,callback){
- if(node !== null){
- inOrder(node.left,callback);
- callback(node.key);
- inOrder(node.right, calback);
- }
- }
- Tree.prototype.inOrderTraverse = function(callback){
- inOrder(root, callback);
- }
- var inOrder = function(node,callback){
- if(node !== null){
- inOrder(node.left,callback);
- callback(node.key);
- inOrder(node.right, calback);
- }
- }
修改为 DOM 二叉树:
[javascript] view plain copy print?
- var inOrder = function(node,callback){
- if(node.firstElementChild) {
- this.inOrder(node.firstElementChild);
- }
- callback(node);
- if(node.lastElementChild) {
- this.inOrder(node.lastElementChild);
- }
- }
- var inOrder = function(node,callback){
- if(node.firstElementChild) {
- this.inOrder(node.firstElementChild);
- }
- callback(node);
- if(node.lastElementChild) {
- this.inOrder(node.lastElementChild);
- }
- }
后序遍历
首先遍历左子树, 然后遍历右子树, 最后访问根结点.
[javascript] view plain copy print?
- Tree.prototype.postOrderTraverse = function(callback){
- postOrder(root, callback);
- }
- var postOrder = function(node,callback){
- if(node !== null){
- postOrder(node.left,callback);
- postOrder(node.right, calback);
- callback(node.key);
- }
- }
- Tree.prototype.postOrderTraverse = function(callback){
- postOrder(root, callback);
- }
- var postOrder = function(node,callback){
- if(node !== null){
- postOrder(node.left,callback);
- postOrder(node.right, calback);
- callback(node.key);
- }
- }
修改为 DOM 二叉树:
[javascript] view plain copy print?
- var postOrder = function(node,callback){
- if(node.firstElementChild) {
- this.postOrder(node.firstElementChild);
- }
- if(node.lastElementChild) {
- this.postOrder(node.lastElementChild);
- }
- callback(node);
- }
- var postOrder = function(node,callback){
- if(node.firstElementChild) {
- this.postOrder(node.firstElementChild);
- }
- if(node.lastElementChild) {
- this.postOrder(node.lastElementChild);
- }
- callback(node);
- }
多叉 DOM 树的遍历
广度优先遍历
首先遍历根节点, 然后访问第一层节点, 第二层节点,...., 直到访问到最后一层.
借助于队列, 用非递归的方式对多叉树进行遍历
[javascript] view plain copy print?
- Tree.prototype.BFSearch = function(node,callback){
- var queue=[];
- while(node!=null){
- callback(node);
- if(node.children.length!=0){
- for (var i=0;i<node.children.length;i++){
- queue.push(node.children[i]);// 借助于队列, 暂存当前节点的所有子节点
- }
- }
- node=queue.shift();// 先入先出, 借助于数据结构: 队列
- }
- };
- Tree.prototype.BFSearch = function(node,callback){
- var queue=[];
- while(node!=null){
- callback(node);
- if(node.children.length!=0){
- for (var i=0;i<node.children.length;i++){
- queue.push(node.children[i]);// 借助于队列, 暂存当前节点的所有子节点
- }
- }
- node=queue.shift();// 先入先出, 借助于数据结构: 队列
- }
- };
深度优先遍历
首先遍历根节点, 然后沿着一条路径遍历到最深的一层, 最后在逐层返回.
借助于栈, 实现多叉 DOM 树 的深度优先遍历.
[javascript] view plain copy print?
- Tree.prototype.DFSearch = function(node,callback){
- var stack=[];
- while(node!=null){
- callback(node);
- if(node.children.length!=0){
- for (var i=node.children.length-1;i>=0;i--){// 按照相反的子节点顺序压入栈
- stack.push(node.children[i]);// 将该节点的所有子节点压入栈
- }
- }
- node = stack.pop();// 弹出栈的子节点顺序就是原来的正确顺序 (因为栈是先入后出的)
- }
- };
- Tree.prototype.DFSearch = function(node,callback){
- var stack=[];
- while(node!=null){
- callback(node);
- if(node.children.length!=0){
- for (var i=node.children.length-1;i>=0;i--){// 按照相反的子节点顺序压入栈
- stack.push(node.children[i]);// 将该节点的所有子节点压入栈
- }
- }
- node = stack.pop();// 弹出栈的子节点顺序就是原来的正确顺序 (因为栈是先入后出的)
- }
- };
二叉 DOM 树的前序, 中序, 后序遍历, 是深度优先遍历的特例
因此, 参考深度优先遍历, 借助栈, 可以以非递归的方式, 实现二叉 DOM 树的 前序, 中序和后序遍历
非递归实现二叉 DOM 树的前序遍历
[javascript] view plain copy print?
- Tree.prototype.preOrder = function(node,callback) {
- var stack=[];
- while(node!== null || stack.length!=0){
- while(node!==null){
- stack.push(node);
- callback.push(node);
- node=node.firstElementChild;
- }
- node=stack.pop();
- node=node.lastElementChild;
- }
- };
- Tree.prototype.preOrder = function(node,callback) {
- var stack=[];
- while(node!== null || stack.length!=0){
- while(node!==null){
- stack.push(node);
- callback.push(node);
- node=node.firstElementChild;
- }
- node=stack.pop();
- node=node.lastElementChild;
- }
- };
非递归实现二叉 DOM 树的中序遍历
[javascript] view plain copy print?
- Tree.prototype.inOrder = function(node,callback) {
- var stack=[];
- while(node!== null || stack.length!=0){
- while(node!==null){
- stack.push(node);
- node=node.firstElementChild;
- }
- node=stack.pop();
- callback(node);
- node=node.lastElementChild;
- }
- };
- Tree.prototype.inOrder = function(node,callback) {
- var stack=[];
- while(node!== null || stack.length!=0){
- while(node!==null){
- stack.push(node);
- node=node.firstElementChild;
- }
- node=stack.pop();
- callback(node);
- node=node.lastElementChild;
- }
- };
非递归实现二叉 DOM 树的后序遍历
每个节点, 都压入栈两次;
在循环体中, 每次弹出一个节点赋给 node
如果 node 仍然等于栈的头结点, 说明 node 的孩子们还没有被操作过, 应该把它的孩子们加入栈中
否则, 说明是第二次弹出该节点, 访问 node.
也就是说, 第一次弹出, 将 node 的孩子压入栈中, 第二次弹出, 访问 node
[javascript] view plain copy print?
- TreeWalker.prototype.postOrder = function(node,callback) {// 非递归实现
- var stack=[];
- stack.push(node);
- stack.push(node);
- while(stack.length != 0)
- {
- node = stack.pop();
- if(stack.length != 0 && node==stack[stack.length-1])
- {
- if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);
- if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);
- }
- else
- callback(node);
- }
- }
- TreeWalker.prototype.postOrder = function(node,callback) {// 非递归实现
- var stack=[];
- stack.push(node);
- stack.push(node);
- while(stack.length != 0)
- {
- node = stack.pop();
- if(stack.length != 0 && node==stack[stack.length-1])
- {
- if(node.lastElementChild) stack.push(node.lastElementChild), stack.push(node.lastElementChild);
- if(node.firstElementChild) stack.push(node.firstElementChild), stack.push(node.firstElementChild);
- }
- else
- callback(node);
- }
- }
来源: https://juejin.im/entry/5afb15066fb9a07a9a110501