JS中的二叉树遍历详解(2)

Morris遍历
这个方法即不用递归也不用栈实现三种深度遍历，空间复杂度为O(1)（这个概念我也不是特别清楚org）
（这三种算法我先放着，有空再研究）
Morris先序:

var morrisPre = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right != cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 console.log(cur1.value) cur1 = cur1.left continue } else { cur2.right = null } } else { console.log(cur1.value) } cur1 = cur1.right } }

Morris中序:

var morrisIn = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null } } console.log(cur1.value) cur1 = cur1.right } }

Morris后序:

var morrisPost = function(head) { if(!head) { return } var cur1 = head, cur2 = null while(cur1) { cur2 = cur1.left if(cur2) { while(cur2.right && cur2.right !== cur1) { cur2 = cur2.right } if(!cur2.right) { cur2.right = cur1 cur1 = cur1.left continue } else { cur2.right = null printEdge(cur1.left) } } cur1 = cur1.right } printEdge(head) } var printEdge = function(head) {

以上就是本文的全部内容，希望对大家的学习有所帮助。

您可能感兴趣的文章: