树的遍历的定义

发布网友 发布时间：2022-04-24 08:21

我来回答

共1个回答

热心网友 时间：2022-06-17 23:45

树的这3种遍历方式可递归地定义如下：
如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。
如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。
否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有：
对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T3,..,Tk进行中序遍历。
对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。
n
/ | \
/ | \
/ | \
/ ... | ... \
T1 T2 T3
前序遍历和中序遍历可形式地依次描述如下 ：
三种遍历可以形式地描述如下，其中用到了树的ADT操作：
Procere Preorder_Traversal(v:NodeType); {前序遍历算法}
begin
Visite(v); {访问节点v}
i:=Leftmost_Child(v);
while i<>∧ do
begin
Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
end;
Procere Inorder_Traversal(v:NodeType); {中序遍历算法}
begin
if Leftmost_Child(v)=∧ {判断v是否是叶节点}
then Visite(v)
else
begin
Inorder_Traversal(Leftmost_Child(v)); {中序遍历v的左边第一个儿子节点}
Visite(v); {访问节点v}
i:=Right_Sibling(Leftmost_Child(v)); {i=v的左边第二个儿子}
while i<>∧ do
begin
Inorder_Traversal(i);
{从左边第二个开始到最右边一个为止依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
end;
end;
Procere Postorder_Traversal(v:NodeType); {后序遍历算法}
begin
i:=Leftmost_Child(v);
while i<>∧ do
begin
Preorder_Traversal(i);{从左到右依次访问v的每一个儿子节点i}
i:=Right_Sibling(i);
end;
Visite(v); {访问节点v}
end;