keyNode.rchild.preNode = tempNode;
                        tempNode.lchild.preNode = keyNode;
                        keyNode.preNode = tempNode;
                        if (keyNode == root)
                        {
                            tempNode.preNode = null;
                            root = tempNode;
                            root.rchild.lchild = null;
                            root.BF = 0;
                            root.lchild.BF = 0;
                            root.rchild.BF = -1;
                        }
                        else
                        {
                            tempNode.preNode = ptrParent;
                            keyNode = tempNode;
                            keyNode.rchild.lchild = null;
                            keyNode.BF = 0;
                            keyNode.lchild.BF = 0;
                            keyNode.rchild.BF = -1;
                        }
                    }
                    else  //RL(R)
                    {
                        Node tempNode = newNode.preNode;
                        tempNode.lchild = keyNode;
                        keyNode.rchild.lchild = tempNode.rchild;
                        tempNode.rchild = keyNode.rchild;
                        keyNode.preNode = tempNode;
                        tempNode.rchild.preNode = keyNode.rchild;
                        keyNode.rchild.preNode = tempNode;
                        if (root == keyNode)
                        {
                            tempNode.preNode = null;
                            root = tempNode;
                            root.lchild.rchild = null;
                            root.BF = 0;
                            root.lchild.BF = 1;
                            root.rchild.BF = 0;
                        }
                        else
                        {
                            tempNode.preNode = ptrParent;
                            keyNode = tempNode;
                            keyNode.lchild.rchild = null;
                            keyNode.BF = 0;
                            keyNode.lchild.BF = 1;
                            keyNode.rchild.BF = 0;
                        }
                    }
                }
            }
            Console.WriteLine("\nAfter:");
            traverse();
        }
        public void find(int Data, ref Node parent, ref Node current)
        {
            index = 0;
            current = root;
            parent = current;
            while ((current != null) && (current.data != Data))
            {
                parent = current;
                if (Data < current.data)
                {
                    current = current.lchild;
                    array[index++] = 1;
                }
                else
                {
                    current = current.rchild;
                    array[index++] = -1;
                }
            }
            array[index] = 0;
        }
        public void traverse()
        {
            Console.Write("InOrder :");
            inOrder(root);
            Console.WriteLine("\nPreOrder:");
            preOrder(root);
            //Console.WriteLine("index:{0}", index + 1);
            //for (int i = 0; i <= index; i++)
            //    Console.Write("{0}  ", array[i]);
        }
        public void inOrder(Node ptr)
        {
            if (root == null)
            {
                Console.WriteLine("The tree is empty!");
                return;
            }
            if (ptr != null)
            {
                inOrder(ptr.lchild);
                Console.Write("{0}  ", ptr.data);
                inOrder(ptr.rchild);
            }
        }
        public void preOrder(Node ptr)
        {
            if (root == null)
            {
                Console.WriteLine("The tree is empty!");
                return;
            }
            if (ptr != null)
            {
                Console.WriteLine("{0}  -   {1}", ptr.data,ptr.BF );
                preOrder(ptr.lchild);
                preOrder(ptr.rchild);
            }
        }
        public void delete()
        {
            Node parent = null, currentNode = null;
            Node delNode=new Node();
            Console.WriteLine("請輸入你要刪除的數:");
            delNode.data  = Convert.ToInt32(Console.ReadLine());
            find(delNode.data , ref parent, ref currentNode);
            int getInfo = delNode.data;
            if (currentNode == null)
            {
                Console.WriteLine("沒有你要刪除的數！");
                return;
            }
            else
            {
                //當要刪除的數是一個葉節點，則有三種情況：
                //1.如果要刪除的數是根節點，則直接將根節點賦值為null
                if ((currentNode.lchild == null) && (currentNode.rchild == null))
                {
                    if (getInfo == root.data)
                    {
                        root = null;
                    }
                    //2.如果要刪除的數是某個父節點的左孩子，將父節點的左指針指向null
                    //3.如果要刪除的數是某個父節點的右孩子，將父節點的右指針指向null
                    if (parent.lchild == currentNode)
                        parent.lchild = null;
                    else
                        parent.rchild = null;
                }
                //當要刪除的節點有孩子時,有二種情況:
                else
                {
                    //(1)有兩個孩子
                    if ((currentNode.lchild != null) & (currentNode.rchild != null))
                    {
                        //從要刪除的節點的右節點開始,查找最左邊的元素,它可以用來替代待刪除節點的位置
                        Node leftMost = currentNode;
                        Node lParent = null;
                        while (leftMost.lchild != null)
                        {
                            lParent = leftMost;
                            leftMost = leftMost.lchild;
                        }
                        currentNode.data = leftMost.data;
                        lParent.lchild = null;
                    }
                    //(2)只有一個孩子
                    else
                    {
                        //有左孩子
                        if (currentNode.lchild != null)
                        {
                            if (parent.lchild == currentNode)
                                parent.lchild = currentNode.lchild;
                            else if (parent.rchild == currentNode)
                                parent.rchild = currentNode.lchild;
                            if (getInfo == root.data)
                            {
                                root = currentNode.lchild;
                            }
                        }
                        //有右孩子
                        else
                        {
                            if (parent.lchild == currentNode)
                                parent.lchild = currentNode.rchild;
                            else if (parent.rchild == currentNode)
                                parent.rchild = currentNode.rchild;
                            if (getInfo == root.data)
                            {
                                root = currentNode.rchild;
                            }
                        }
                    }
                }
            }
            Node ptr = parent;
            int i = index - 1;
            while (ptr != null)
            {
                ptr.BF -= array[i--];
                if (ptr.BF == 0)
                {
                    Console.WriteLine("It is a balanced tree !");
                    return;
                }
                else if ((ptr.BF != 0) && (ptr.BF != 1) && (ptr.BF != -1))
                {
                    Console.WriteLine("Not balanced !");
                    balance(ptr, delNode );
                    return;
                }
                ptr = ptr.preNode;
            }
            Console.WriteLine("It is a balanced tree!");
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            BalancedTree bt = new BalancedTree();
            Console.WriteLine("1.insert");
            Console.WriteLine("2.delete");
            Console.WriteLine("3.traverse");
            Console.WriteLine("4.exit");

            while (true)
            {
                Console.Write("\nYour choice:");
                int choice = Convert.ToInt32(Console.ReadLine());
                switch (choice)
                {
                    case 1:
                        {
                            bt.insert();
                            break;
                        }
                    case 2:
                        {
                            bt.delete();
                            break;
                        }
                    case 3:
                        {
                            bt.traverse();
                            break;
                        }
                    case 4:
                        {
                            System.Environment.Exit(0);
                            break;
                        }
                }
            }
        }
    }
}