0331 이진트리

Binary Tree

preorder 부모노드를 먼저 순회하고,

다음 왼쪽 서브 트리를,

마지막으로 오른쪽 서브트리를 순회

배열에 이진 트리를 저장하는 방식은 기본적으로 트리 레벨 순으로 왼쪽>오른쪽으로 저장

A[0] = 루트, A[1] = A의 왼쪽 자식, A[2] = A 자식의 오른쪽 형제

public class BinaryTreeArray
    {
        private string[] arr;
        public string Root
        {
            get
            {
                return this.arr[0];
            }
            set 
            {
                this.arr[0] = value;
            }
        }
        public BinaryTreeArray(int capacity) 
        {
            this.arr = new string[capacity];
        }
        public void SetLeft(int parentIndex, string data) 
        {
            int leftIndex = (parentIndex*2) + 1;
            this.arr[leftIndex] = data;
        }
        //왼쪽 요소 가져오기
        public string GetLeft(int parentIndex) 
        {
            int leftIndex = (parentIndex * 2) + 1;
            return this.arr[leftIndex];
        }

        public void SetRight(int parentIndex, string data) 
        {
            int rightIndex = (parentIndex * 2) + 2;
            this.arr[rightIndex] = data;
        }
        //오른쪽 요소 가져오기
        public string GetRight(int parentIndex)
        {
            int rightIndex = (parentIndex * 2) + 2;
            return this.arr[rightIndex];
        }

        //부모 요소 가져오기
        public string GetParent(int childIndex) 
        {
            if (childIndex == 0) return null;
            int parentIndex = (childIndex - 1) / 2;
            return this.arr[parentIndex];
        }

        public void Print() 
        {
            for (int i = 0; i < arr.Length; i++) 
            {
                Console.Write("{0}",this.arr[i] ?? "-");
            }
            Console.WriteLine();
        }
        //?? null이 아닌 경우 왼쪽 피연산자의 값을 반환한다

        
    }
}

public class App
    {
        public App()
        {
            BinaryTreeArray binaryTree = new BinaryTreeArray(7);
            binaryTree.Root = "A";
            binaryTree.SetLeft(0, "B");
            binaryTree.SetRight(0, "C");
            binaryTree.SetLeft(1, "D");
            binaryTree.SetLeft(2, "F");

            binaryTree.Print();
            var parent = binaryTree.GetParent(5);
            Console.WriteLine(parent);
            var left = binaryTree.GetLeft(2);
            Console.WriteLine(left);
        } 

    }

 

 

1. 전위 순회 (Preorder)
ABDEC1. 전위 순회 (Preorder)
ABDECF
2. 중위 순회 (Inorder)
DBEAFC
3. 후위 순회 (Postorder)
DEBFCA

public class BinaryNode
    {
        public BinaryNode left;
        public BinaryNode right;
        public string data;
        public BinaryNode(string data) 
        {
            this.data = data;
        }
    }

public class BinaryTree
    {
        public BinaryNode root;
        public BinaryTree(string data) 
        {
            this.root = new BinaryNode(data);
        }
        public void PreorderTraversal()
        {
            this.PreorderTraversalImpl(this.root);
        }

        public void PreorderTraversalImpl(BinaryNode node)
        {
            if (node == null) return;
            Console.WriteLine("{0}", node.data);
            this.PreorderTraversalImpl(node.left);
            this.PreorderTraversalImpl(node.right);

        }
        //중위 순회
        public void InorderTraversal()
        {
            this.InorderTraversalImpl(this.root);
        }
        public void InorderTraversalImpl(BinaryNode node)
        {
            if (node == null) return;
            this.InorderTraversalImpl(node.left);
            Console.WriteLine("{0}", node.data);
            this.InorderTraversalImpl(node.right);
        }
        //후위순회
        public void PostorederTraversal()
        {
            this.PostorederTraversalImpl(this.root);
        }
        public void PostorederTraversalImpl(BinaryNode node)
        {
            if (node == null) return;
            this.PostorederTraversalImpl(node.left);
            this.PostorederTraversalImpl(node.right);
            Console.WriteLine("{0}", node.data);
        }
    }

public class App
    {
        public App()
        {
            BinaryTree tree = new BinaryTree("A");
            tree.root.left = new BinaryNode("B");
            tree.root.right = new BinaryNode("C");
            tree.root.left.left = new BinaryNode("D");
            tree.root.left.right = new BinaryNode("E");

            Console.WriteLine("전위순회");
            tree.PreorderTraversal();
            Console.WriteLine("중위순회");
            tree.InorderTraversal();
            Console.WriteLine("후위순회");
            tree.PostorederTraversal();
        } 

    }

 

4. Preorder Iterative

public void PreorderIterative() 
        {
            //스택을 만든다.
            var stack = new Stack<BinaryNode>();
            //루트를 넣는다.
            stack.Push(this.root);
            //스택에 요소가 있다면 반복한다.
            while (stack.Count > 0) 
            {
                var node = stack.Pop();
                Console.WriteLine("{0}", node.data);
                //오른쪽에 넣는다.
                if (node.right != null) 
                {
                    stack.Push(node.right);
                }
                //왼쪽에 넣는다.
                if (node.left != null) 
                {
                    stack.Push(node.left);
                }
            }
        }