c \ # 이 진 트 리 생 성과 여러 가지 문제

최근 에 이 진 트 리 를 배 웠 습 니 다. 인터넷 에 있 는 신 들 이 제공 하 는 방법 과 결합 하여 c \ # 이 진 트 리 를 만 드 는 방법 과 다른 방법 을 썼 습 니 다.
감사 하 다.http://blog.csdn.net/luckyxiaoqiang/article/details/7518888#comments Walking In The Wind 블 로그 에서 많은 것 을 배 웠 습 니 다.
이 진 트 리 의 구조:

 	public class Node
        {
            public object Value { get; set; }
            public Node Node_left { get; set; }
            public Node Node_right { get; set; }

            public Node(object value, Node lchild, Node rchild)
            {
                Value = value;
                Node_left = lchild;
                Node_right = rchild;
            }
            public Node(object val)
            {
                Value = val;
                Node_left = null;
                Node_right = null;
            }
            public Node()
            {
                Value = null;
                Node_left = null;
                Node_right = null;
            }
        }

이 진 트 리 를 만 드 는 방법 은 확장 할 수 있 습 니 다. 예 를 들 어 응용 할 때 문자열 을 입력 하여 이 진 트 리 를 만 드 는 등 입 니 다.

	public void BinaryTree(Node node)
        {
            //   value  ，                 
            //       ***--**
            if (node.Value == null || String.IsNullOrEmpty(node.Value.ToString()))
                return;
            node.Node_left = new Node();
            BinaryTree(node.Node_left);
            if (node.Node_left.Value == null)
                node.Node_left = null;
            node.Node_right = new Node();
            BinaryTree(node.Node_right);
            if (node.Node_right.Value == null)
                node.Node_right = null;
        }

앞 순 서 를 편력 하 다.

        //    
        public void FirstTraversal(Node node)
        {
            if (node.Value == null)
                return;
            Console.WriteLine(node.Value);
            FirstTraversal(node.Node_left);
            FirstTraversal(node.Node_right);
        }

중간 순서 로 옮 겨 다 닌 다.

        //    
        public void MiddleTraversal(Node node)
        {
            if (node.Value == null)
                return;
            MiddleTraversal(node.Node_left);
            Console.WriteLine(node.Value);
            MiddleTraversal(node.Node_right);
        }

뒤 순 서 를 옮 겨 다 닌 다.

        //    
        public void LastTraversal(Node node)
        {
            if (node.Value == null)
                return;
            LastTraversal(node.Node_left);
            LastTraversal(node.Node_right);
            Console.WriteLine(node.Value);
        }

여러 단계 로 편력 하 다.

        //    
        public void LevelTraversal(Node node)
        {
            Queue

다른 면접 에서 겪 을 문제
1. 이 진 트 리 노드 개수 구하 기
2. 이 진 트 리 깊이 구하 기
3. 이 진 트 리 K 층 노드 개수 구하 기
4. 잎 사 귀 노드 개수
5. 두 갈래 나무의 구조 가 동일 한 지 판단 하기
6. 이 진 트 리 가 밸 런 스 이 진 트 리 인지 판단
7. 이 진 트 리 의 거울
8. 완전 이 진 트 리 인지 아 닌 지 판단 하기

        //          
        public int GetNodeNum(Node node)
        {
            if (node.Value == null)
                return 0;
            return GetNodeNum(node.Node_left) + GetNodeNum(node.Node_right) + 1;
        }

        //       
        public int GetNodeDepth(Node node)
        {
            if (node.Value == null)
                return 0;
            int leftDepth = GetNodeNum(node.Node_left);
            int rightDepth = GetNodeNum(node.Node_right);
            int depth = leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);//include current node, so +1
            return depth;
        }

        //     K      
        public int GetNodeNumOnLevel(Node node, int k)
        {
            if (node == null || k < 1)
                return 0;
            if (k == 1)
                return 1;
            int leftNum = GetNodeNumOnLevel(node.Node_left, k - 1);
            int rightNum = GetNodeNumOnLevel(node.Node_right, k - 1);
            return (leftNum + rightNum);
        }

        //            
        public int GetLeafNodeNum(Node node)
        {
            if (node == null)
                return 0;
            if (node.Node_left == null && node.Node_right == null)
                return 1;
            int numleft = GetLeafNodeNum(node.Node_left);
            int numright = GetLeafNodeNum(node.Node_right);
            return (numleft + numright);
        }

        //             
        public bool AreSameStruct(Node n1, Node n2)
        {
            if (n1 == null && n2 == null)
                return true;
            else if (n1 == null || n2 == null)
                return false;
            bool leftsame = AreSameStruct(n1.Node_left, n2.Node_left);
            bool rightsame = AreSameStruct(n1.Node_right, n2.Node_right);
            return (leftsame && rightsame);
        }

        //             
        public bool BalanceTree(Node node, out int height)
        {
            if (node == null)
            {
                height = 0;
                return true;
            }
            int heightleft = 0;
            bool resultleft = BalanceTree(node.Node_left, out heightleft);
            int heightright = 0;
            bool resultright = BalanceTree(node.Node_right, out heightright);
            if (resultleft && resultright && Math.Abs(heightleft - heightright) < 1)
            {
                height = Math.Max(heightleft, heightright) + 1;
                return true;
            }
            else
            {
                height = Math.Max(heightleft, heightright) + 1; ;
                return false;
            }
        }

        //       
        public Node TreeMirror(Node node)
        {
            if (node == null)
                return null;
            Node leftnode = TreeMirror(node.Node_left);
            Node rightnode = TreeMirror(node.Node_right);
            node.Node_left = rightnode;
            node.Node_right = leftnode;
            return node;
        }

        //             
        public bool IsCompleteBinaryTree(Node node)
        {
            if (node == null)
                return false;
            Queue