二叉树先遍历c#版本

常用遍历方法:

  • void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树
  • void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树
  • void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
  • void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右

先明白入参和出参,可以在ide中测试 。

以下采用迭代和递归两种实现方法 。

定义树节点

   public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

输入1,null, 2, 3 , 数据结构如下

TreeNode node3 = new TreeNode(3);
TreeNode node2 = new TreeNode(2);
node2.left = node3;
TreeNode node1 = new TreeNode(1);
node1.right = node2;

方法实现1

采用迭代方法实现 ,先把node加入堆栈, 然后whild循环判断 ,如果有值的情况下,让节点出栈,出时加入返回的list列表, 然后再循环节点的左右节点,重新再加入栈,然后再出栈,加入列表,一直到堆栈列表为空。返回lint列表

public static IList<int> PreorderTraversal2(TreeNode root)
{
    var list = new List<int>();
    if (root == null) return null;

    Stack<TreeNode> snodes=new Stack<TreeNode>();
    snodes.Push(root);
    while(snodes.Any())
    {
        TreeNode node = snodes.Pop();
        list.Add(node.val);
        if(node.right!=null) snodes.Push(node.right);
        if (node.left != null) snodes.Push(node.left);
    }
    return list;
}

方法实现2

采用递归方法 ,利用yield特性返回节点值 。

 public static IList<int> PreorderTraversal(TreeNode root)
 {
     var list = new List<int>();
     if (root != null)
         list = PreorderTraversalHelper(root).ToList();

     return list;
 }

private static IEnumerable<int> PreorderTraversalHelper(TreeNode node)
{
    yield return node.val;
    if (node.left != null)
        foreach (var nod in PreorderTraversalHelper(node.left))
            yield return nod;
    if (node.right != null)
        foreach (var nod in PreorderTraversalHelper(node.right))
            yield return nod;
}

测试调用与输入输出

public static IList<int> PreorderTraversal2(TreeNode root)
{
    var list = new List<int>();
    if (root == null) return null;

    Stack<TreeNode> snodes=new Stack<TreeNode>();
    snodes.Push(root);
    while(snodes.Any())
    {
        TreeNode node = snodes.Pop();
        list.Add(node.val);
        if(node.right!=null) snodes.Push(node.right);
        if (node.left != null) snodes.Push(node.left);
    }
    return list;
}

本文由 hcb 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论