二叉樹遍歷 C#

1、在電腦科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。（百度百科）

廣度優先搜索(Breadth First Search),又叫寬度優先搜索或橫向優先搜索，是從根結點開始沿著樹的寬度搜索遍歷，上面二叉樹的遍歷順序為：ABCDEFG.

深度優先搜索(Depth First Search)是沿著樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。以上面二叉樹為例，深度優先搜索的順序為：ABDECFG。

2、二叉樹的實現

二叉樹的結點包含data，left，right，通過一些結點之間的關係就可以構造二叉樹；

二叉樹節點類

class Node<T>

{

    T data;

    Node<T> left;

    Node<T> right;

    public Node(T value)

    {

        data = value;

        left = null;

        right = null;

    }

    public Node()

    {

        data = default(T);

        left = null;

        right = null;

    }

    public Node(T value,Node<T> lChild,Node<T> rChild)

    {

        data = value;

        left = lChild;

        right = rChild;

    }

    public T Data

    {

        get { return data; }

        set { data = value; }

    }

    public Node<T> Left

    {

        get { return left; }

        set { left = value; }

    }

    public Node<T> Right

    {
    
        get { return right; }

        set { right = value; }

    }

}                       

3、二叉樹類

class LinkBinaryTree<T>

{

    private Node<T> root;//根結點

    public Node<T> Root

    {

        get { return root; }

    }

    public LinkBinaryTree()

    {

        root = null;

    }

    public LinkBinaryTree(T value)

    {

        Node<T> p = new Node<T>(value);

        root = p;

    }

//三種深度遍歷

//中序遍歷

    public void InOrder(Node<T> node)

    {

        if (root == null)

            return;

        if(node!=null)

        {

            InOrder(node.Left);

            Console.Write(node.Data);

            InOrder(node.Right);

        }

    }

//先序遍歷

    public void PreOrder(Node<T> node)

    {

        if (root == null)

            return;

        if (node != null)

        {

            Console.Write(node.Data);

            PreOrder(node.Left);

            PreOrder(node.Right);

        }

    }

//後序遍歷

    public void PostOrder(Node<T> node)

    {

        if (root == null)

            return;

        if (node != null)

        {

            PostOrder(node.Left);

            PostOrder(node.Right);

            Console.Write(node.Data);

        }

    }

//-------廣度遍歷----------使用隊列又稱為先進先出

    public void BFS(Node<T> root)

    {

        if (root == null)

            return;

        Queue<Node<T>> queue = new Queue<Node<T>>();

        queue.Enqueue(root);

        while (queue.Count>0)

        {

            Node<T> node = queue.Dequeue();

            Console.WriteLine(node.Data);

            if (node.Left != null)

                queue.Enqueue(node.Left);

            if (node.Right != null)

                queue.Enqueue(node.Right);

        }

    }

}

深度遍歷：（根節點A的位置）

　　先序輸出：A   B  D  G  H  E  C  K  F  I  J 

　　中序輸出：G  D  H  B   E  A  K  C  I  J  F

　　後序輸出：G  H  D  E   B  K  J  I   F C  A

廣度遍歷：

　　A   B  C  D  E  K  F  G  H  I  J

面試遇到的，於是在網上學習，自己總結一下。小菜瓜，第一次發。有什麼問題望多多提，一起學習。往後我會把自己總結的Unity   lua等都會一一發出來共用。獨樂樂不如眾樂樂嘛，一起進步。------一點都不v5的小菜瓜。