tree.cs

此程序可实现一定的功能

using System;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;

namespace MyGraph
{
    public class Tree
    {
        public LinkedList<Vertex> VtxList;
        public Tree()
        {
            VtxList = new LinkedList<Vertex>();
        }
        public LinkedListNode<Vertex> FindVtx(int vtx)
        {
            LinkedListNode<Vertex> tempVtx = VtxList.First;
            while (tempVtx != null)
            {
                if (tempVtx.Value.vtx == vtx)
                    return tempVtx;
                tempVtx = tempVtx.Next;
            }
            return tempVtx;
        }
//对树进行插入，因为是树的类型，不支持森林，不允许单独插入节点，那样可能会出现森林
//必须以边的形式插入，并且当要插入边的起始节点和终止节点都不在节点链表中时，不允许
//插入，因为这样会出现森林；当要插入边的起始节点和终止节点都在节点链表中时，不允许
//插入，因为这样会出现环路
        public void Insert(int from,int to)
        {
            Vertex tempVtx;
            LinkedListNode<Vertex> tempVtxLink ;
            if (VtxList.Count == 0)
            {
                tempVtx = new Vertex(from);
                VtxList.AddLast(tempVtx);
                
            }
            else
            {
                
                if ((FindVtx(from) == null)&&(FindVtx(to)==null))
                {
                    Console.WriteLine("ERROR");
                    return;
                }
                if ((FindVtx(from) != null) && (FindVtx(to) != null))
                {
                    Console.WriteLine("ERROR");
                    return;
                }
            }
            tempVtxLink = FindVtx(from);
            if (tempVtxLink == null)
            {
                tempVtx = new Vertex(from);
                VtxList.AddLast(tempVtx);
                tempVtxLink = VtxList.Last;
            }
            EdgeLink tempEdge = new EdgeLink(to);
            tempVtxLink.Value.list.AddLast(tempEdge);
            if (FindVtx(to) == null)
            {
                tempVtx = new Vertex(to);
                VtxList.AddLast(tempVtx);
            }
        }
        public void Delete(int v)
        {
            LinkedListNode<Vertex> tempVtx = VtxList.First;
            while (tempVtx != null)
            {
                if (tempVtx.Value.vtx == v)
                {
                    LinkedListNode<Vertex> temp = tempVtx;
                    tempVtx = tempVtx.Next;
                    VtxList.Remove(temp);
                }
                else
                {
                    LinkedListNode<EdgeLink> tempEdge = tempVtx.Value.list.First;
                    while (tempEdge != null)
                    {
                        if (tempEdge.Value.destVtx == v)
                        {
                            tempVtx.Value.list.Remove(tempEdge);
                            break;
                        }
                        tempEdge = tempEdge.Next;
                    }
                    tempVtx = tempVtx.Next;
                }
            }
        }
        public void InsertInfo(int from, int to, string info)
        {
            LinkedListNode<Vertex> tempVtx = VtxList.First;
            while (tempVtx != null)
            {
                if (tempVtx.Value.vtx == from)
                {
                    LinkedListNode<EdgeLink> tempEdge = tempVtx.Value.list.First;
                    while (tempEdge != null)
                    {
                        if (tempEdge.Value.destVtx == to)
                        {
                            tempEdge.Value.info = info;
                            return;
                        }
                        tempEdge = tempEdge.Next;
                    }
                }
                tempVtx = tempVtx.Next;
            }
        }
//前序遍历，输出的是节点的链表
        public void PreOrder(LinkedListNode<Vertex> vtx, LinkedList<int> output)
        {
            if (vtx != null)
            {
                int tempVtx = vtx.Value.vtx;
                output.AddLast(tempVtx);
                LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
                LinkedListNode<Vertex> tempVTX ;
                while (tempEdge != null)
                {
                    tempVTX = FindVtx(tempEdge.Value.destVtx);
                    PreOrder(tempVTX,output);
                    tempEdge = tempEdge.Next;
                }
            }
        }
//中序遍历
        public void InOrder(LinkedListNode<Vertex> vtx, LinkedList<int> output)
        {
            if (vtx != null)
            {
                LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
                LinkedListNode<Vertex> tempVtx;
                if (tempEdge != null)
                {
                    tempVtx = FindVtx(tempEdge.Value.destVtx);
                    InOrder(tempVtx, output);
                    tempEdge = tempEdge.Next;
                }
                output.AddLast(vtx.Value.vtx);
                while (tempEdge != null)
                {
                    tempVtx = FindVtx(tempEdge.Value.destVtx);
                    InOrder(tempVtx, output);
                    tempEdge = tempEdge.Next;
                }
            }
        }
//后序遍历
        public void PostOrder(LinkedListNode<Vertex> vtx, LinkedList<int> output)
        {
            if (vtx != null)
            {
                LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
                LinkedListNode<Vertex> tempVtx;
                while (tempEdge != null)
                {
                    tempVtx = FindVtx(tempEdge.Value.destVtx);
                    PostOrder(tempVtx, output);
                    tempEdge = tempEdge.Next;
                }
                output.AddLast(vtx.Value.vtx);
            }
        }
//按层遍历
        public void LevelOrder(LinkedList<int> output)
        {
            LinkedListNode<Vertex> tempVtx = VtxList.First;
            LinkedListNode<EdgeLink> tempEdge;
            Queue<int> outqueue = new Queue<int>();
            if (tempVtx != null)
                outqueue.Enqueue(tempVtx.Value.vtx);
            while (outqueue.Count != 0)
            {
                int i=outqueue.Dequeue();
                tempVtx = FindVtx(i);
                output.AddLast(i);
                tempEdge = tempVtx.Value.list.First;
                while (tempEdge != null)
                {
                    outqueue.Enqueue(tempEdge.Value.destVtx);
                    tempEdge = tempEdge.Next;
                }
            }
        }
        public string TreeToStr()
        {
            string s = "digraph g{\n";
            s += "\tsize = \"10, 10\";\n";
            s += "\tnode [color=lightblue2, style=filled];\n";
            string temp1 = "\"";
            string temp2 = "->";
            string temp3 = ";\n";
            LinkedListNode<Vertex> tempVtx = VtxList.First;
            LinkedListNode<EdgeLink> tempEdge;
            while (tempVtx != null)
            {
                tempEdge = tempVtx.Value.list.First;
                while (tempEdge != null)
                {
                    s += temp1;
                    s += tempVtx.Value.vtx;
                    s += temp1;
                    s += temp2;
                    s += temp1;
                    s += tempEdge.Value.destVtx;
                    s += temp1;
                    s += temp3;
                    tempEdge = tempEdge.Next;
                }
                tempVtx = tempVtx.Next;
            }
            s += "}\n\n";
            return s;
        }
        public void TreeToJPG(string name)
        {
            string strname = "";
            strname += name;
            string dotname = "";
            dotname += name;
            dotname += ".dot";
            string jpgname = "";
            jpgname += name;
            jpgname += ".jpg";
            string dotname2 = dotname;
            StreamWriter fp;
            fp = File.CreateText(dotname2);
            string s = TreeToStr();
            fp.WriteLine(s);
            fp.Close();

            string command = "dot -Tjpg -o ";
            command += jpgname;
            command += " ";
            command += dotname;

            Process p = new Process();
            p.StartInfo.FileName = "cmd.exe";

            p.StartInfo.UseShellExecute = false;
            p.StartInfo.RedirectStandardInput = true;
            p.StartInfo.RedirectStandardOutput = true;
            p.StartInfo.RedirectStandardError = true;
            p.StartInfo.CreateNoWindow = true;

            p.Start();
            p.StandardInput.WriteLine(command);
            p.StandardInput.WriteLine("exit");
            p.StandardOutput.ReadToEnd();
            p.Close();

        }
//以下两个函数是将遍历输出的节点链表，输出到dot和jpg文件中
        public string OutputToStr(LinkedList<int> output)
        {
            string s = "digraph g{\n";
            s += "\tsize = \"10, 10\";\n";
            s += "\tnode [color=lightblue2, style=filled];\n";
            string temp1 = "\"";
            string temp2 = "->";
            string temp3 = ";\n";
            LinkedListNode<int> tempLink = output.First;
            LinkedListNode<int> tempLinkNext;
            if ((tempLink != null) && (tempLink.Next == null))
            {
                s += temp1;
                s += tempLink.Value;
                s += temp1;
                s += temp3;
                s += "}\n\n";
                return s;
            }
            while (tempLink != null)
            {
                tempLinkNext = tempLink.Next;
                if (tempLinkNext != null)
                {
                    s += temp1;
                    s += tempLink.Value;
                    s += temp1;
                    s += temp2;
                    s += temp1;
                    s += tempLinkNext.Value;
                    s += temp1;
                    s += temp3;
                }
                tempLink=tempLink.Next;
            }
            s += "}\n\n";
            return s;
        }
        public void OutputToJPG(string name,LinkedList<int> output)
        {
            string strname = "";
            strname += name;
            string dotname = "";
            dotname += name;
            dotname += ".dot";
            string jpgname = "";
            jpgname += name;
            jpgname += ".jpg";
            string dotname2 = dotname;
            StreamWriter fp;
            fp = File.CreateText(dotname2);
            string s = OutputToStr(output);
            fp.WriteLine(s);
            fp.Close();

            string command = "dot -Tjpg -o ";
            command += jpgname;
            command += " ";
            command += dotname;

            Process p = new Process();
            p.StartInfo.FileName = "cmd.exe";

            p.StartInfo.UseShellExecute = false;
            p.StartInfo.RedirectStandardInput = true;
            p.StartInfo.RedirectStandardOutput = true;
            p.StartInfo.RedirectStandardError = true;
            p.StartInfo.CreateNoWindow = true;

            p.Start();
            p.StandardInput.WriteLine(command);
            p.StandardInput.WriteLine("exit");
            p.StandardOutput.ReadToEnd();
            p.Close();
        }
    }
}