求助：关于树的遍历

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.UI;
using System.Web.UI.WebControls;
using wssmax;
using System.Data;
using Mono.Cecil;
using Mono.Cecil.Cil;
using System.Collections;
using System.Globalization;namespace ShowTree
{
    public partial class _Default : System.Web.UI.Page
    {
        private DataTable tempDt = new DataTable();
        private int Step = 0;
        private Dictionary<string, OrgNode> nodes = new Dictionary<string, OrgNode>();
        private Dictionary<int, OrgNode> offsetOrgNodes = new Dictionary<int, OrgNode>();
        private MethodDefinition tempMethod;        protected void Page_Load(object sender, EventArgs e)
        {
            if (!IsPostBack)
            {
                tempDt = CreateTable();
                InitData();                if (tempMethod.Body.Instructions.Count > 0)
                    ParseInstructionByOpCodeFlowControl(tempMethod.Body.Instructions[0]);

                TraversalOrgChart();
                TraversalOrgChart();
                TraversalOrgChart();
            }
        }        private void InitData()
        {
            AssemblyDefinition asm = AssemblyDefinition.ReadAssembly("/BaiRong.BackgroundPages.dll");            foreach (TypeDefinition type in asm.MainModule.Types)
                if (type.Name == "BackgroundAdministrator")
                    foreach (MethodDefinition method in type.Methods)
                        if (method.Name == "GetDateTime")
                            foreach (Instruction ins in method.Body.Instructions)
                                tempMethod = method;
        }        /// <summary>
        /// 根据OpCodeFlowControl类别处理IL指令
        /// </summary>
        /// <param name="ins"></param>
        private void ParseInstructionByOpCodeFlowControl(Instruction ins) {            switch (ins.OpCode.FlowControl) {
                case FlowControl.Branch:
                    ParseOpCodeFlowControlOfBranch(ins);
                    break;
                case FlowControl.Cond_Branch:
                    ParseOpCodeFlowControlOfCond_Branch(ins);
                    break;
                case FlowControl.Next:
                    ParseOpCodeFlowControlOfNext(ins);
                    ParseInstructionByOpCodeFlowControl(ins.Next);
                    break;
                case FlowControl.Call:
                    ParseOpCodeFlowControlOfNext(ins);
                    ParseInstructionByOpCodeFlowControl(ins.Next);
                    break;
                case FlowControl.Return:
                    ParseOpCodeFlowControlOfNext(ins);
                    break;
                case FlowControl.Break:
                case FlowControl.Throw:
                case FlowControl.Meta:
                case FlowControl.Phi:
                    break;
            }
        }        private OrgNode ParseOpCodeFlowControlOfNext(Instruction ins) {
            OrgNode parentNode = new OrgNode();            int parentOffset = -1;
            if (ins.Previous != null)
                parentOffset = ins.Previous.Offset;            if (parentOffset == -1) {
                OrgNode node = new OrgNode();
                node.Text = ins.Offset.ToString();
                node.Description = parentOffset.ToString();                OrgChart1.Node = node;                offsetOrgNodes.Add(ins.Offset, node);
                parentNode = OrgChart1.Node;
            }

            OrgNode parentOrgNode = new OrgNode();
            if (offsetOrgNodes.TryGetValue(parentOffset, out parentOrgNode))
            {
                OrgNode node = new OrgNode();
                node.Text = ins.Offset.ToString();
                node.Description = parentOffset.ToString();                if(!parentOrgNode.Nodes.Contains(node))
                    parentOrgNode.Nodes.Add(node);                if (!offsetOrgNodes.TryGetValue(ins.Offset, out parentOrgNode))
                    offsetOrgNodes.Add(ins.Offset,node);
            }            return parentNode;
        }        private void ParseOpCodeFlowControlOfCall(Instruction ins) {
            ParseOpCodeFlowControlOfNext(ins);
            ParseInstructionByOpCodeFlowControl(ins.Next);
        }        private void ParseOpCodeFlowControlOfBranch(Instruction ins) {
            ParseOpCodeFlowControlOfNext(ins);            Instruction next;
            int next_offset = int.Parse(ins.Operand.ToString().Substring(3, 4), NumberStyles.HexNumber);            if (tempMethod.Body.OffsetInstructions.TryGetValue(next_offset, out next))
            {
                next.Previous = ins;
                ParseInstructionByOpCodeFlowControl(next);
            }
        }
        private void ParseOpCodeFlowControlOfCond_Branch(Instruction ins)
        {
            ParseOpCodeFlowControlOfNext(ins);            Instruction next;
            int next_offset = int.Parse(ins.Operand.ToString().Substring(3, 4), NumberStyles.HexNumber);            if (tempMethod.Body.OffsetInstructions.TryGetValue(next_offset, out next))
            {
                next.Previous = ins;
                ParseOpCodeFlowControlOfNext(next);
                //ParseOpCodeFlowControlOfNext(next.Next);

                //ParseInstructionByOpCodeFlowControl(next.Next);
            }            ParseInstructionByOpCodeFlowControl(ins.Next);            #region
            //switch (ins.OpCode.Code) {
            //    case Code.Brfalse_S:
            //    case Code.Brtrue_S:
            //    case Code.Beq_S:
            //    case Code.Bge_S:
            //    case Code.Bgt_S:
            //    case Code.Ble_S:
            //    case Code.Blt_S:
            //    case Code.Bne_Un_S:
            //    case Code.Bge_Un_S:
            //    case Code.Bgt_Un_S:
            //    case Code.Ble_Un_S:
            //    case Code.Blt_Un_S:
            //    case Code.Brfalse:
            //    case Code.Brtrue:
            //    case Code.Beq:
            //    case Code.Bge:
            //    case Code.Bgt:
            //    case Code.Ble:
            //    case Code.Blt:
            //    case Code.Bne_Un:
            //    case Code.Bge_Un:
            //    case Code.Bgt_Un:
            //    case Code.Ble_Un:
            //    case Code.Blt_Un:
            //    case Code.Switch:
            //        ParseCondBranchOfBrfalse_S(ins);
            //        break;
            //}
            #endregion
        }        private void TraversalOrgChart() {
            if (OrgChart1.Node.Nodes.Count > 0)
                TraversalOrgChartChildOrgNode(OrgChart1.Node);        }

private void TraversalOrgChartChildOrgNode(OrgNode orgNode) {
            foreach (OrgNode node in orgNode.Nodes) {
                if (node.Nodes.Count > 0)
                {
                    foreach (OrgNode child in node.Nodes)
                        TraversalOrgChartChildOrgNode(child);
                }
                else {
                    Instruction ins;
                    if (tempMethod.Body.OffsetInstructions.TryGetValue(int.Parse(node.Text), out ins))
                    {
                        if (ins.OpCode.Code!= Code.Ret)
                        {
                            offsetOrgNodes = new Dictionary<int, OrgNode>(); //初始化offsetOrgNodes
                            GetChildOrgNodes(node);                            ParseInstructionByOpCodeFlowControl(ins.Next);
                        }
                    }
                }
            }        }        private bool CheckHasChildOrgNode() {
            bool hasNode = false;            foreach (OrgNode node in OrgChart1.Node.Nodes)
            {
                if (node.Nodes.Count > 0)
                {
                    foreach (OrgNode child in node.Nodes)
                        TraversalOrgChartChildOrgNode(child);
                }
                else
                {
                    Instruction ins;
                    if (tempMethod.Body.OffsetInstructions.TryGetValue(int.Parse(node.Text), out ins))
                    {
                        if (ins.Next != null)
                        {
                            hasNode = true;
                            return hasNode;
                        }
                    }
                }
            }            return hasNode;
        }
        /// <summary>
        /// 根据包括本节点的树
        /// </summary>
        /// <param name="lastOrgNode"></param>
        private void GetChildOrgNodes(OrgNode lastOrgNode) {
            try
            {
                offsetOrgNodes.Add(int.Parse(lastOrgNode.Text), lastOrgNode);
            }
            catch(Exception ex) {
                throw new Exception(ex.Message+","+lastOrgNode.Description);
            }            if (lastOrgNode.Parent != null)
                GetChildOrgNodes((OrgNode)lastOrgNode.Parent);
        }
        /// <summary>
        /// 如果上一条指令的操作数为0，则跳转到指定位置，否则执行下一跳指令，奖下一指令的上一指令做一改变
        /// </summary>
        /// <param name="ins"></param>
        private void ParseCondBranchOfBrfalse_S(Instruction ins) {
            if (ins.Previous.OpCode.Code == Code.Ldc_I4_0)
            {
                Instruction next;
                int next_offset = int.Parse(ins.Operand.ToString().Substring(3, 4), System.Globalization.NumberStyles.HexNumber);
                if (tempMethod.Body.OffsetInstructions.TryGetValue(next_offset, out next))
                {
                    next.Previous = ins.Previous;
                    ParseInstructionByOpCodeFlowControl(next);
                }
            }
            else
            {
                Instruction next = ins.Previous;
                ParseInstructionByOpCodeFlowControl(next);
            }
        }        private void TreeOrgNodeTop()
        {
            OrgNode orgNode = new OrgNode();
            orgNode.Text = "0";
            orgNode.Description = "0,-1";            OrgChart1.Node = orgNode;
            nodes.Add("0,-1", orgNode);
        }        private void TreeOrgNodeChild(OrgNode parentOrgNode) {
            DataRow[] rows = tempDt.Select(string.Format("[Parent]={0}",parentOrgNode.Text));
            if (rows.Length > 0) {
            Label_1:
                for (int i = 0; i < rows.Length; i++) {
                    OrgNode orgNode = new OrgNode();
                    orgNode.Text = rows[i]["Offset"].ToString();
                    orgNode.Description = rows[i]["Parent"].ToString();
                                            var query = from OrgNode org in OrgChart1.Node.Nodes where int.Parse(org.Text) == int.Parse(orgNode.Text) select org;
                    foreach(OrgNode org in query)
                        goto Label_1;                    parentOrgNode.Nodes.Add(orgNode);                    Step++;
                    if (Step > 300)
                        return;                    TreeOrgNodeChild(orgNode);
                }
            }
        }        private DataTable CreateTable()
        {
            DataTable dt = new DataTable();            dt.Columns.Add(new DataColumn("Offset", Type.GetType("System.Int32")));
            dt.Columns.Add(new DataColumn("Parent", Type.GetType("System.Int32")));
            //dt.Constraints.Add("Offset",dt.Columns[0],false);            return dt;
        }        private void SwitchIns(Instruction ins, Instruction previous)
        {
            switch (ins.OpCode.FlowControl)
            {
                case FlowControl.Branch:
                case FlowControl.Cond_Branch:
                    HandleInlineBrTarget(ins, previous);
                    break;
                case FlowControl.Next:
                case FlowControl.Call:
                case FlowControl.Return:
                case FlowControl.Break:
                case FlowControl.Throw:
                case FlowControl.Meta:
                case FlowControl.Phi:
                    HandleNext(ins, previous);
                    break;
            }
        }        private void HandleInlineBrTarget(Instruction ins, Instruction previous)
        {
            DataRow dr = tempDt.NewRow();            dr["Offset"] = ins.Offset;
            dr["Parent"] = previous == null ? -1 : previous.Offset;            tempDt.Rows.Add(dr);            string parentKey = string.Empty;
            if (previous != null && previous.Previous != null)
                parentKey = previous.Offset.ToString() + "," + previous.Previous.Offset.ToString();            if (previous != null && previous.Previous == null)
                parentKey = "0,-1";            UptoOrgChart(dr,parentKey);            int next_offset = int.Parse(ins.Operand.ToString().Substring(3, 4), System.Globalization.NumberStyles.HexNumber);
            parentKey = dr["Offset"] + "," + dr["Parent"];            dr = tempDt.NewRow();
            dr["Offset"] = next_offset;
            dr["Parent"] = ins.Offset;            tempDt.Rows.Add(dr);            UptoOrgChart(dr,parentKey);
        }        private void HandleNext(Instruction ins, Instruction previous)
        {
            DataRow dr = tempDt.NewRow();            dr["Offset"] = ins.Offset;
            dr["Parent"] = previous == null ? -1 : previous.Offset;            tempDt.Rows.Add(dr);            string parentKey = string.Empty;
            if (previous != null && previous.Previous != null)
                parentKey = previous.Offset.ToString() + "," + previous.Previous.Offset.ToString();            if (previous != null && previous.Previous == null)
                parentKey = "0,-1";            UptoOrgChart(dr,parentKey);        }        private void UptoOrgChart(DataRow dr,string parentKey)
        {
            OrgNode orgNode = new OrgNode();
            orgNode.Text = dr["Offset"].ToString()+":"+parentKey;
            orgNode.Description = parentKey;            OrgNode parentOrgNode = new OrgNode();
            string key=dr["Offset"].ToString()+","+dr["Parent"].ToString();            if (dr["Offset"].ToString() == "0")
            {
                OrgChart1.Node = orgNode;
                nodes.Add("0,-1", orgNode);
                return;
            }            if (string.IsNullOrEmpty(parentKey))
            {
                parentKey = "0,-1";
            }            if (nodes.TryGetValue(parentKey, out parentOrgNode))
            {
                parentOrgNode.Nodes.Add(orgNode);                if (!nodes.TryGetValue(key, out parentOrgNode))
                    nodes.Add(key, orgNode);
            }
        }        private void GetParentOrgNode(DataRow dr,OrgNode orgNode,OrgNode parentOrgNode) {            foreach (OrgNode parent in parentOrgNode.Nodes)
            {
                var query = from OrgNode org in parent.Nodes where int.Parse(org.Text) == int.Parse(dr["Parent"].ToString()) select org;
                foreach (OrgNode org in query)
                {
                    Response.Write(org.Text + ",");                    org.Nodes.Add(orgNode);
                    return;
                }                foreach (OrgNode child in parent.Nodes) {
                    GetParentOrgNode(dr,orgNode,child);
                }
            }        }
    }
}上面两个贴子完整的代码，分作两部分了，代码过长发不了

只要各个节点都有parent信息，随便你怎么存都好用。

这里问题的关键是某个节点也许有多个父节点，也有可能多个子节点。我现在是想根据每一个不同的父节点和子节点得到所有的子树。fengyarongaa兄的冒泡算法不明白怎么用到这个地方，能否详细一点？
以前没有专业学过算法，只是有需要的时候才补充一下这方面的知识，见笑了哈

调试易

求助：关于树的遍历

解决方案 »