0

Hi guys help me please. I wrote the code for a binary search tree, but for some reason I'm wildly stupid in post-traverse and searching. Can someone help with writing a postorder and search. Thank you and sorry for bad english. Thank you very much again.

I don't show you my Remove and Contains method because it does not important. If you want to see them , i can show it.

My BinaryTreeNode class

public class BinaryTreeNode<T> : IComparable<T>
    where T : IComparable
{
    public BinaryTreeNode(T value)
    {
        Value = value;
    }

    public BinaryTreeNode<T> Left { get; set; }
    public BinaryTreeNode<T> Right { get; set; }
    public T Value { get; }

    public int CompareTo(T other)
    {
        return Value.CompareTo(other);
    }

    public IEnumerator<T> GetEnumerator()
    {
        var leftEnumerable = (IEnumerable<T>) Left ?? new T[0];
        var rightEnumerable = (IEnumerable<T>) Right ?? new T[0];

        return leftEnumerable.Concat(new[] {Value})
            .Concat(rightEnumerable)
            .GetEnumerator();
    }
}

My BinaryTree class :

 public class BinaryTree<T>
    where T : IComparable
{
    private BinaryTreeNode<T> _head;

    public int Count { get; private set; }


    public void Add(T value)
    {
        if (_head == null)
            _head = new BinaryTreeNode<T>(value);
        else
            AddTo(_head, value);

        Count++;
    }

    private void AddTo(BinaryTreeNode<T> node, T value)
    {
        if (value.CompareTo(node.Value) < 0)
        {
            if (node.Left == null)
                node.Left = new BinaryTreeNode<T>(value);
            else
                AddTo(node.Left, value);
        }
        else
        {
            if (node.Right == null)
                node.Right = new BinaryTreeNode<T>(value);
            else
                AddTo(node.Right, value);
        }
    }

    public IEnumerable<T> Preorder(BinaryTreeNode<T> root)
    {
        var stack = new Stack<BinaryTreeNode<T>>();
        stack.Push(root);

        while (stack.Count > 0)
        {
            var node = stack.Pop();
            yield return node.Value;
            if (node.Right != null)
                stack.Push(node.Right);
            if (node.Left != null)
                stack.Push(node.Left);
        }
    }

    public IEnumerable<T> InOrder(BinaryTreeNode<T> root)
    {
        var stack = new Stack<BinaryTreeNode<T>>();
        while (root != null)
        {
            while (root.Left != null)
            {
                stack.Push(root);
                root = root.Left;
            }

            yield return root.Value;

            while (root.Right == null && stack.Count > 0)
            {
                root = stack.Pop();
                yield return root.Value;
            }

            root = root.Right;
        }
    }


    public IEnumerator<T> GetEnumerator()
    {
        return _head.GetEnumerator();
    }

    public void Clear()
    {
        _head = null;
        Count = 0;
    }
}
  • There's a good discussion of iterative postorder traversal here: https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/. Searching is basically a pre-order traversal, but at each node you only visit one child: the left child if the thing you're searching for is less than the node's value, and the right node if the thing you're searching for is larger. If you can insert into the tree, you should be able to search. – Jim Mischel Jul 31 '18 at 17:16
  • Also see https://stackoverflow.com/questions/1294701/post-order-traversal-of-binary-tree-without-recursion (potential duplicate) – Jim Mischel Jul 31 '18 at 17:19
  • thank you very much for answers @JimMischel – Tetsua Keito Jul 31 '18 at 18:26

0 Answers0