分 享

【凤凰社】二叉树遍历 C#

1、在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。(百度百科)

广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索,是从根结点Start沿着树的宽度搜索遍历,上面二叉树的遍历顺序为: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; }

    }

}                       
View Code

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);

        }

    }

}
View Code

深度遍历:(根节点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的小菜瓜。


0 评论

回复