Output binary tree (inorder traversal iterative) doesn't work

57 Views Asked by At

I need to output tree. But this output is incorrect. My tree is: `

 public class ElTree
    {
        public int L;
        public string inf;
        public bool PR;
        public ElTree(string inf)
        {
            this.inf = inf;
            this.PR = false;
            this.L = -1;
        }
    }

`

Class Tree is (Here other methods that I do with Tree, the method that output Tree in in the end. I`ve also tried to do output with recursion and it work correctly, so method Add() works correctly. But I have a task to do output in iterative way). For example, when I add tree lake "k"-root, "r"-right elem, "l"-left elem then my recursive method output "lkr" but iterative method output just "ll":

`

public class Tree
    {
        public ElTree[] T;
        public int Coun { get { return _count; } }
        private int _count;
        public Tree(string inf)
        {
            ElTree temp = new ElTree(inf);
            T = new ElTree[1];
            T[T.Length-1] = temp;
        }
        public int Find(int V, string inf)
        {
            if (V == T.Length) return -1;
            if (V != -1)
            {
                if (T[V].inf == inf) return V;
                int temp = Find(T[V].L, inf);
                if (temp != -1) 
                    return temp;
                return temp = Find(V + 1, inf);
            }
            return -1;
        }
        public bool Empty()
        {
            if (Coun == 0)
            {
                return true;
            }
            else
                return false;
        }
 public bool Add(int i, string inf, char s)
        {
            ElTree temp = new ElTree(inf);
            switch (s)
            {
                case 'L':
                    if (T[i].L == -1)
                    {
                        Array.Resize(ref T, T.Length + 1);
                        T[T.Length - 1] = temp;
                        T[i].L = T.Length - 1;
                        _count++;
                        return true;
                    }
                    else return false;
                case 'R':
                    if (!T[i].PR)
                    {
                        Array.Resize(ref T, T.Length + 1);
                        T[T.Length - 1] = temp;
                        T[i].PR = true;
                        _count++;
                        return true;
                    }
                    else return false;
            }
            return false;
        }
        public void TreeInStringit(int i, ref string s)//iterative output
        {
            Stack<int> stack = new Stack<int>();
            //int i = 0;
            stack.Push(i);
            do
            {
                while (T[i].L != -1 && i < T.Length)
                {
                    i = T[i].L;
                    stack.Push(i);
                }
                s += T[i].inf;
                while (T[i].PR && i < T.Length)
                {
                    i++;
                    stack.Push(i);
                }
                if (stack.Count != 0) stack.Pop();
            } while (stack.Count != 0);
        }
 public void String(int V, ref string s)//recursive output
        {
            ElTree temp = T[V];
            if (temp.L != -1)
                String(temp.L, ref s);
            s += temp.inf;
            if (temp.PR)
                String(V+1, ref s);
        }

`

When I add tree like root with two elements (one on left side and one on right) it output left side of tree 2 times. But I need output all tree.

0

There are 0 best solutions below