Tree Traversal(樹的走訪)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

透過一些演算法能夠對 樹狀結構 的節點進行逐一的訪問，可以應用在搜索、序列化或其他的用途上。依據走訪的方式，大致上可分為以下兩大類：

深度優先(Depth-first)

深度優先又分為三種走訪方式，而一般樹和 二元樹 以下分開來討論：

一般樹

前序(Pre-order)

訪問根節點 訪問所有子樹

上圖的走訪順序為：ABDEFHCG

中序(In-order)

訪問第一個子樹 訪問根節點 訪問其他子樹

上圖的走訪順序為：DBEHFAGC

事實上一般樹的情況下，中序走訪並不實用。

後序(Post-order)

訪問所有子樹 訪問根節點

上圖的走訪順序為：DEHFBGCA

二元樹

前序(Pre-order)

訪問根節點 訪問左子樹 訪問右子樹

上圖的走訪順序為：ABDECFG

中序(In-order)

訪問左子樹 訪問根節點 訪問右子樹

上圖的走訪順序為：DBEAFCG

後序(Post-order)

訪問左子樹 訪問右子樹 訪問根節點

上圖的走訪順序為：DEBFGCA

廣度優先(Breadth-first)

廣度優先又可以稱為Level-order，將每一個階層的節點都走訪完後才到下一層。

圖一的走訪順序為：ABCDEFGH

圖二的走訪順序為：ABCDEFG

語法

C#

一般樹

using System; using System.Collections.Generic; using System.Linq; using System.Text; using Tree;

namespace TreeTraversal { public class TreeTraversal { public static List PreOrder (Tree tree) { List list = new List (tree.Count); PreOrder(tree, list); return list; }

private static void PreOrder (Tree tree, List list) { list.Add(tree.Value); foreach (Tree child in tree.Children) PreOrder(child, list); }

public static List InOrder (Tree tree) { List list = new List (tree.Count); InOrder(tree, list); return list; }

private static void InOrder (Tree tree, List list) { IEnumerator > enu =tree.Children.GetEnumerator(); if (enu.MoveNext()) InOrder(enu.Current, list); list.Add(tree.Value); while(enu.MoveNext()) InOrder(enu.Current, list); }

public static List PostOrder (Tree tree) { List list = new List (tree.Count); PostOrder(tree, list); return list; }

private static void PostOrder (Tree tree, List list) { foreach (Tree child in tree.Children) PostOrder(child, list); list.Add(tree.Value); }

public static List BreadthFirst (Tree tree) { List list = new List (tree.Count); Queue > queue = new Queue >(); queue.Enqueue(tree); while (queue.Count > 0) { Tree tmpTree = queue.Dequeue(); list.Add(tmpTree.Value); foreach (Tree child in tmpTree.Children) queue.Enqueue(child); } return list; } } }

二元樹

using System; using System.Collections.Generic; using System.Linq; using System.Text; using BinaryTree;

namespace TreeTraversal { public class BinaryTreeTraversal { public static List PreOrder (BinaryTree tree) { List list = new List (tree.Count); PreOrder(tree, list); return list; }

private static void PreOrder (BinaryTree tree, List list) { list.Add(tree.Value); if(tree.Left != null) PreOrder(tree.Left, list); if (tree.Right != null) PreOrder(tree.Right, list); }

public static List InOrder (BinaryTree tree) { List list = new List (tree.Count); InOrder(tree, list); return list; }

private static void InOrder (BinaryTree tree, List list) { if (tree.Left != null) InOrder(tree.Left, list); list.Add(tree.Value); if (tree.Right != null) InOrder(tree.Right, list); }

public static List PostOrder (BinaryTree tree) { List list = new List (tree.Count); PostOrder(tree, list); return list; }

private static void PostOrder (BinaryTree tree, List list) { if (tree.Left != null) PostOrder(tree.Left, list); if (tree.Right != null) PostOrder(tree.Right, list); list.Add(tree.Value); }

public static List BreadthFirst (BinaryTree tree) { List list = new List (tree.Count); Queue > queue = new Queue >(); queue.Enqueue(tree); while (queue.Count > 0) { BinaryTree tmpTree = queue.Dequeue(); list.Add(tmpTree.Value); if (tmpTree.Left != null) queue.Enqueue(tmpTree.Left); if (tmpTree.Right != null) queue.Enqueue(tmpTree.Right); } return list; } } }

Java

一般樹

import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Queue;

public class TreeTraversal { public static List preOrder(Tree tree) { List list = new ArrayList (tree.size()); preOrder(tree, list); return list; }

private static void preOrder(Tree tree, List list) { list.add(tree.getValue()); for (Tree child : tree.children()) preOrder(child, list); }

public static List inOrder(Tree tree) { List list = new ArrayList (tree.size()); inOrder(tree, list); return list; }

private static void inOrder(Tree tree, List list) { Iterator > iterator =tree.children().iterator(); if (iterator.hasNext()) inOrder(iterator.next(), list); list.add(tree.getValue()); while(iterator.hasNext()) inOrder(iterator.next(), list); }

public static List postOrder(Tree tree) { List list = new ArrayList (tree.size()); postOrder(tree, list); return list; }

private static void postOrder(Tree tree, List list) { for (Tree child : tree.children()) postOrder(child, list); list.add(tree.getValue()); } public static List breadthFirst(Tree tree) { List list = new ArrayList (tree.size()); Queue > queue = new LinkedList >(); queue.add(tree); while (!queue.isEmpty()) { Tree tmpTree = queue.poll(); list.add(tmpTree.getValue()); for (Tree child : tmpTree.children()) queue.add(child); } return list; } }

二元樹

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue;

public class BinaryTreeTraversal { public static List preOrder(BinaryTree tree) { List list = new ArrayList (tree.size()); preOrder(tree, list); return list; }

private static void preOrder(BinaryTree tree, List list) { list.add(tree.getValue()); if(tree.left() != null) preOrder(tree.left(), list); if (tree.right() != null) preOrder(tree.right(), list); }

public static List inOrder(BinaryTree tree) { List list = new ArrayList (tree.size()); inOrder(tree, list); return list; }

private static void inOrder(BinaryTree tree, List list) { if(tree.left() != null) inOrder(tree.left(), list); list.add(tree.getValue()); if (tree.right() != null) inOrder(tree.right(), list); }

public static List postOrder(BinaryTree tree) { List list = new ArrayList (tree.size()); postOrder(tree, list); return list; }

private static void postOrder(BinaryTree tree, List list) { if(tree.left() != null) postOrder(tree.left(), list); if (tree.right() != null) postOrder(tree.right(), list); list.add(tree.getValue()); } public static List breadthFirst(BinaryTree tree) { List list = new ArrayList (tree.size()); Queue > queue = new LinkedList >(); queue.add(tree); while (!queue.isEmpty()) { BinaryTree tmpTree = queue.poll(); list.add(tmpTree.getValue()); if (tmpTree.left() != null) queue.add(tmpTree.left()); if (tmpTree.right() != null) queue.add(tmpTree.right()); } return list; } }

C++

一般樹

#ifndef TREETRAVERSAL_H #define TREETRAVERSAL_H

#include #include #include "Tree.h"

using namespace std;

template class TreeTraversal { public: TreeTraversal() {} virtual ~TreeTraversal() {}

static vector & preOrder(Tree * tree) { vector * vect = new vector (); preOrder(tree, *vect); return *vect; }

static vector & inOrder(Tree * tree) { vector * vect = new vector (); inOrder(tree, *vect); return *vect; }

static vector & postOrder(Tree * tree) { vector * vect = new vector (); postOrder(tree, *vect); return *vect; }

static vector & breadthFirst(Tree * tree) { vector * vect = new vector (); queue *> queue; queue.push(tree); while (!queue.empty()) { Tree * tmpTree = queue.front(); queue.pop(); vect->push_back(tmpTree->getValue()); TreeList * children = tmpTree->children(); children->begin(); while(Tree * child = children->next()) queue.push(child); } return *vect; } protected: private: static void preOrder(Tree * tree, vector & vect) { vect.push_back(tree->getValue()); TreeList * children = tree->children(); children->begin(); while(Tree * child = children->next()) preOrder(child, vect); }

static void inOrder(Tree * tree, vector & vect) { TreeList * children = tree->children(); children->begin(); if(Tree * child = children->next()) inOrder(child, vect); vect.push_back(tree->getValue()); while(Tree * child = children->next()) inOrder(child, vect); }

static void postOrder(Tree * tree, vector & vect) { TreeList * children = tree->children(); children->begin(); while(Tree * child = children->next()) postOrder(child, vect); vect.push_back(tree->getValue()); } };

#endif // TREETRAVERSAL_H

二元樹

#ifndef BINARYTREETRAVERSAL_H #define BINARYTREETRAVERSAL_H

#include #include #include "BinaryTree.h"

using namespace std;

template class BinaryTreeTraversal { public: BinaryTreeTraversal() {} virtual ~BinaryTreeTraversal() {}

static vector & preOrder(BinaryTree * tree) { vector * vect = new vector (); preOrder(tree, *vect); return *vect; }

static vector & inOrder(BinaryTree * tree) { vector * vect = new vector (); inOrder(tree, *vect); return *vect; }

static vector & postOrder(BinaryTree * tree) { vector * vect = new vector (); postOrder(tree, *vect); return *vect; }

static vector & breadthFirst(BinaryTree * tree) { vector * vect = new vector (); queue *> queue; queue.push(tree); while (!queue.empty()) { BinaryTree * tmpTree = queue.front(); queue.pop(); vect->push_back(tmpTree->getValue());

if (tmpTree->left() != 0) queue.push(tmpTree->left()); if (tmpTree->right() != 0) queue.push(tmpTree->right()); } return *vect; } protected: private: static void preOrder(BinaryTree * tree, vector & vect) { vect.push_back(tree->getValue()); if(tree->left() != 0) preOrder(tree->left(), vect); if (tree->right() != 0) preOrder(tree->right(), vect); }

static void inOrder(BinaryTree * tree, vector & vect) { if(tree->left() != 0) inOrder(tree->left(), vect); vect.push_back(tree->getValue()); if (tree->right() != 0) inOrder(tree->right(), vect); }

static void postOrder(BinaryTree * tree, vector & vect) { if(tree->left() != 0) postOrder(tree->left(), vect); if (tree->right() != 0) postOrder(tree->right(), vect); vect.push_back(tree->getValue()); } };

#endif // BINARYTREETRAVERSAL_H -->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

Tree Traversal(樹的走訪)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

最新留言

文章搜尋

文章精選