深度优先搜索，无堆栈

本文关键字：堆栈 深度优先搜索 | 更新日期: 2023-09-27 18:20:47

我开始用堆栈编码为：

void Foo(TreeNode root)
    {
        Stack nodes = new Stack();
        nodes.Push(root);
        while (nodes.Count > 0)
        {
            TreeNode node = (TreeNode) nodes.Pop();
            Console.WriteLine(node.Text);
            for (int i = node.Nodes.Count - 1; i >= 0; i--)
                nodes.Push(node.Nodes[i]);
        }
    }

但是，没有堆栈我不知道，我应该做什么。

我试过了。这是正确的吗？有人能推荐我吗？

void Foo(TreeNode root)
{
   if(root == null) return;
    System.out.print(root.Value + "'t");
    root.state = State.Visited;
    //for every child
    for(Node n: root.getChild())
    {
        //if childs state is not visited then recurse
        if(n.state == State.Unvisited)
        {
            dfs(n);
        }
    }
}

深度优先搜索，无堆栈

使用：

Console.WriteLine(node.Text);
for (Int i = 0; i < node.Nodes.Count; i++)
    Foo(root.Nodes[i]);

namespace ConsoleApplication3
{
    using System.Collections.Generic;
    public class Tree
    {
        public int Value { get; set; }
        public List<Tree> TreeNode
        {
            get;
            set;
        }
        public Tree()
        {
            this.TreeNode = new List<Tree>();
        }
    }
    public class Program
    {
        public static void Main()
        {
            Program pro = new Program();
            Tree tree = new Tree();
            tree.TreeNode.Add(new Tree() { Value = 1 });
            tree.TreeNode.Add(new Tree() { Value = 2 });
            tree.TreeNode.Add(new Tree() { Value = 3 });
            tree.TreeNode.Add(new Tree() { Value = 4 });
            pro.DepthFirstSearch(2, tree);
        }
        private Tree DepthFirstSearch(int searchValue, Tree root)
        {
            if (searchValue == root.Value)
            {
                return root;
            }
            Tree treeFound = null;
            foreach (var tree in root.TreeNode)
            {
                treeFound = DepthFirstSearch(searchValue, tree);
                if (treeFound != null)
                {
                    break;
                }
            }
            return treeFound;
        }
    }
}
相关文章：