算法：⼆叉树的层次遍历（递归实现+⾮递归实现，lua）⼆叉树知识参考：
递归实现层次遍历算法参考：
上⾯第⼀篇基础写得不错，不了解⼆叉树的值得⼀看。
⽤递归来实现⼆叉树的层次遍历。lua实现
先上代码：
function FindTree(tree, callback)
local function Find(tree, level)
if(tree == nil or level <= 0) then
return false;
end
if (level == 1) then
if callback then
callback(tree.data);
end
return true;
end
local has_left = Find(tree.left, level - 1);
local has_right = Find(tree.right, level - 1);
return has_left or has_right;
end
local level = 1;
while Find(tree, level, callback) do
level = level + 1;
end
end
测试代码：
a={};
a.data = "a"
b, c = {}, {}
b.data = "b"
c.data = "c"
a.left = b
a.right = c
d, e, f, g = {}, {}, {}, {}
d.data = "d"
e.data = "e"
f.data = "f"
g.data = "g"
b.left = d
b.right = e
c.left = f
二叉树中序遍历非递归算法c.right = g
h, i, j = {}, {}, {}
h.data = "h"
i.data = "i"
j.data = "j"
d.left = h
d.right = i
e.left = j
local  list = {}
FindTree(a, function(data)
table.insert(list, data)
end)
at(list, ", "))
结果：
基本思路（下⾯的a是测试树的根结点）：
每步，都是⼀次从根到当前层级的⾃上⽽下的⼀次遍历，从上到下到第1层a,  从上到下到第2层b,c，从上到下到第3层d,e,f,g
详细步骤：
1，FindTree(a, 1) : 如果此树深度⼤于等于1，a结点的data通过回调传回，函数返回true , while循环继续；如果深度为
0，a==null，直接返回false，while循环结束。
2，FindTree(a, 2)：如果此树深度⼤于等于2，传回a的⼦结点（上图b位置，或c位置，或bc位置）的data，返回true , while 循环继续；如果深度⼩于2，返回false，while循环结束。
  这⾥就⽐较复杂了，需要对函数递归有⼀定的了解。执⾏到 has_left = FindTree(tree.left, level - 1); 时，现场被保留（后续代码暂时不执⾏），程序再次进⼊到FindTree函数（即执⾏has_left = FindTree(b, 1)），当a有左⼦节点时，传回a的左⼦节点的data，返回true，即 has_left =true; 否则 has_left = false;  然后执⾏到has_right = FindTree(tree.right, level - 1)；同理，如果有右⼦节点，传回a的右⼦节点的data，返回true，即 has_right=true; 否则 has_right= false。如果a有左⼦节点或右⼦节点（或都有），整个函数返回true，while循环继续；如果a没有左结点和右结点，即深度⼩于2，has_left or has_right = false ，while循环结束。
3，FindTree(a, 3)：如果此树深度⼤于等于3，传回a的深度为3的⼦结点（上图d, e, f, g的各位置随意组合）的data，返回true , while循环继续；如果深度⼩于2，返回false，while循环结束。
  同理，执⾏到 has_left = FindTree(tree.left, level - 1); 时，现场保留，直到has_left = FindTree(tree.left.left, level - 1 -1); 即has_left = FindTree(d, 1)，如果d结点不存在，返回false，has_left = false; 如果存在，打印d结点的data，返回true，has_left = true; e, f, g各个位置的检测同理。
4，…… ， n - 1,
n，FindTree(a, n): 深度⼩于n (此树深度为n-1)，返回false，while循环结束。
⽤⾮递归来实现⼆叉树的层次遍历。lua实现
先上代码：
function FindTree2(tree, callback)
local  nodeList = {tree}
while #nodeList > 0do
local  tempList = {}
for i, v in ipairs(nodeList) do
if callback then
callback(v.data)
end
table.insert(tempList, v.left)
table.insert(tempList, v.right)
end
nodeList = tempList;
end
end
测试代码：如上
测试如果：如上
基本思路：从上到下，每⼀层从左到右依次遍历。把每⼀层⼦节点存放在⼀个列表，直到这个列表为空，则遍历完成。这个⽅式⽐较直观，直接看⼀下上⾯的图和代码，很容易理解。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。