Home   Cover Cover Cover Cover
 

Iterieren über einen Binärbaum

A04.cs
//==========================================================
// Iterating over a binary tree
//==========================================================

using System;
using System.Collections.Generic;

//----------------------------------------------------------
// class Node
//----------------------------------------------------------
class Node {
  public int val;
  public Node left;
  public Node right;
  public Node(int v) { val = v; }
  
  // returns the values in the left subtree, the root, and
  // the values in the right subtree
  public IEnumerator<int> GetEnumerator() {
    if (left != null)
      foreach (int x in left) yield return x;
    yield return val;
    if (right != null)
      foreach (int x in right) yield return x;
  }
}

//----------------------------------------------------------
// class Tree
//----------------------------------------------------------
class Tree {
  Node root = null;
  
  // adds a number to the tree
  public void Add(int val) {
    Node p = root, father = null;
    while (p != null) {
      father = p;
      if (val < p.val) p = p.left; else p = p.right;
    }
    Node n = new Node(val);
    if (root == null) root = n;
    else if (val < father.val) father.left = n;
    else father.right = n;
  }
  
  // returns an iterator of the root node
  public IEnumerator<int> GetEnumerator() {
    if (root == null)
      return new EmptyTree().GetEnumerator();
    else
      return root.GetEnumerator();
  }
  
}

// auxiliary class: allows "iteration" over an empty tree
class EmptyTree {
  public IEnumerator<int> GetEnumerator() {
    yield break;
  }
}

//----------------------------------------------------------
// test program
//----------------------------------------------------------
class Test {
  
  public static void Main() {
    Tree tree = new Tree();
    tree.Add(17);
    tree.Add(6);
    tree.Add(12);
    tree.Add(9);
    tree.Add(4);
    tree.Add(21);
    
    foreach (int x in tree) Console.WriteLine(x);
  }
}