Необходимо реализовать дерево и его обход в симметричном, прямом и обратном порядке - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток.C#.Необходимо реализовать дерево и его обход. В симметричном, прямом и обратном порядке. Подскажите пожалуйста как реализовать(хотя бы один из методов).. Рисунок дерева во вложении.

Решение задачи: «Необходимо реализовать дерево и его обход в симметричном, прямом и обратном порядке»

textual
Листинг программы
using System;
using System.Collections;
using System.Collections.Generic;
 
public class BinaryTree<T> : ICollection<T>
{
    protected class Node<TValue>
    {
        public TValue Value
        {
            get;
            set;
        }
        public Node<TValue> Left
        {
            get;
            set;
        }
        public Node<TValue> Right
        {
            get;
            set;
        }
 
        public Node(TValue value)
        {
            Value = value;
        }
    }
 
    protected Node<T> root;
    protected IComparer<T> comparer;
 
    public BinaryTree() : this(Comparer<T>.Default)
    {
    }
    public BinaryTree(IComparer<T> defaultComparer)
    {
        if (defaultComparer == null)
            throw new ArgumentNullException("Default comparer is null");
        comparer = defaultComparer;
    }
    public BinaryTree(IEnumerable<T> collection) : this(collection, Comparer<T>.Default)
    {
        
    }
    public BinaryTree(IEnumerable<T> collection, IComparer<T> defaultComparer) : this(defaultComparer)
    {
        AddRange(collection);
    }
 
    public T MinValue
    {
        get
        {
            if (root == null)
                throw new InvalidOperationException("Tree is empty");
            var current = root;
            while (current.Left != null)
                current = current.Left;
            return current.Value;
        }
    }
    public T MaxValue
    {
        get
        {
            if (root == null)
                throw new InvalidOperationException("Tree is empty");
            var current = root;
            while (current.Right != null)
                current = current.Right;
            return current.Value;
        }
    }
 
    public void AddRange(IEnumerable<T> collection)
    {
        foreach (var value in collection)
            Add(value);
    }
 
    public IEnumerable<T> Inorder()
    {
        if (root == null)
            yield break;
 
        var stack = new Stack<Node<T>>();
        var node = root;
 
        while (stack.Count > 0 || node != null) {
            if (node == null) {
                node = stack.Pop();
                yield return node.Value;
                node = node.Right;
            }
            else {
                stack.Push(node);
                node = node.Left;
            }
        }
    }
    public IEnumerable<T> Preorder()
    {
        if (root == null)
            yield break;
 
        var stack = new Stack<Node<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> Postorder()
    {
        if (root == null)
            yield break;
 
        var stack = new Stack<Node<T>>();
        var node = root;
 
        while (stack.Count > 0 || node != null) {
            if (node == null) {
                node = stack.Pop();
                if (stack.Count > 0 && node.Right == stack.Peek()) {
                    stack.Pop();
                    stack.Push(node);
                    node = node.Right;
                }
                else {
                    yield return node.Value;
                    node = null;
                }
            }
            else {
                if (node.Right != null)
                    stack.Push(node.Right);
                stack.Push(node);
                node = node.Left;
            }
        }
    }
    public IEnumerable<T> Levelorder()
    {
        if (root == null)
            yield break;
 
        var queue = new Queue<Node<T>>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            yield return node.Value;
            if (node.Left != null)
                queue.Enqueue(node.Left);
            if (node.Right != null)
                queue.Enqueue(node.Right);
        }
    }
 
    #region ICollection<T> Members
    public int Count
    {
        get;
        protected set;
    }
    public virtual void Add(T item)
    {
        var node = new Node<T>(item);
 
        if (root == null)
            root = node;
        else {
            Node<T> current = root, parent = null;
 
            while (current != null) {
                parent = current;
                if (comparer.Compare(item, current.Value) < 0)
                    current = current.Left;
                else
                    current = current.Right;
            }
 
            if (comparer.Compare(item, parent.Value) < 0)
                parent.Left = node;
            else
                parent.Right = node;
        }
        ++Count;
    }
    public virtual bool Remove(T item)
    {
        if (root == null)
            return false;
 
        Node<T> current = root, parent = null;
 
        int result;
        do {
            result = comparer.Compare(item, current.Value);
            if (result < 0) {
                parent = current;
                current = current.Left;
            }
            else if (result > 0) {
                parent = current;
                current = current.Right;
            }
            if (current == null)
                return false;
        }
        while (result != 0);
 
        if (current.Right == null) {
            if (current == root)
                root = current.Left;
            else {
                result = comparer.Compare(current.Value, parent.Value);
                if (result < 0)
                    parent.Left = current.Left;
                else
                    parent.Right = current.Left;
            }
        }
        else if (current.Right.Left == null) {
            current.Right.Left = current.Left;
            if (current == root)
                root = current.Right;
            else {
                result = comparer.Compare(current.Value, parent.Value);
                if (result < 0)
                    parent.Left = current.Right;
                else
                    parent.Right = current.Right;
            }
        }
        else {
            Node<T> min = current.Right.Left, prev = current.Right;
            while (min.Left != null) {
                prev = min;
                min = min.Left;
            }
            prev.Left = min.Right;
            min.Left = current.Left;
            min.Right = current.Right;
 
            if (current == root)
                root = min;
            else {
                result = comparer.Compare(current.Value, parent.Value);
                if (result < 0)
                    parent.Left = min;
                else
                    parent.Right = min;
            }
        }
        --Count;
        return true;
    }
    public void Clear()
    {
        root = null;
        Count = 0;
    }
    public void CopyTo(T[] array, int arrayIndex)
    {
        foreach (var value in this)
            array[arrayIndex++] = value;
    }
    public virtual bool IsReadOnly
    {
        get
        {
            return false;
        }
    }
    public bool Contains(T item)
    {
        var current = root;
        while (current != null) {
            var result = comparer.Compare(item, current.Value);
            if (result == 0)
                return true;
            if (result < 0)
                current = current.Left;
            else
                current = current.Right;
        }
        return false;
    }
    #endregion
 
    #region IEnumerable<T> Members
    public IEnumerator<T> GetEnumerator()
    {
        return Inorder().GetEnumerator();
    }
    #endregion
 
    #region IEnumerable Members
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
    #endregion
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4 из 5
Похожие ответы