flash on 2012-10-28

/**
 * Copyright innmu ( http://wonderfl.net/user/innmu )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/809T
 */

package
{
    public class BinaryTree
    {
        public var rootNode:Node;
 
        public function BinaryTree(rootNode:Node = null)
        {
            this.rootNode = rootNode;
        }
 
        public function searchNode(value:int):Node
        {
            var curNode:Node = rootNode;
            while (curNode)
            {
                if (value == curNode.value)
                {
                    return curNode;
                }
                else if (value < curNode.value)
                {
                    curNode = curNode.left;
                }
                else
                {
                    curNode = curNode.right;
                }
            }
 
            return null;
        }
 
        public function insertNode(value:int):Node
        {
            var curNode:Node = rootNode;
            var parentNode:Node = null;
            var isLeftChild:Boolean;
            while (curNode)
            {
                if (value == curNode.value)
                {
                    return null;
                }
                else if (value < curNode.value)
                {
                    parentNode = curNode;
                    curNode = curNode.left;
                    isLeftChild = true;
                }
                else
                {
                    parentNode = curNode;
                    curNode = curNode.right;
                    isLeftChild = false;
                }
            }
 
            var newNode:Node = new Node(value);
            if (parentNode == null)
            {
                rootNode = newNode;
            }
            else if (isLeftChild)
            {
                parentNode.left = newNode;
            }
            else
            {
                parentNode.right = newNode;
            }
 
            return newNode;
        }
 
        public function removeNode(value:int):Boolean
        {
            var curNode:Node = rootNode;
            var parentNode:Node = null;
            var isLeftChild:Boolean = false;
 
            while (curNode)
            {
                if (value == curNode.value)
                {
                    var childNode:Node = null;
                    if (curNode.left && curNode.right)
                    {
                        childNode = removeMinNode(curNode.right, curNode);
                        childNode.right = curNode.right;
                        childNode.left = curNode.left;
                    }
                    else if (curNode.left)
                    {
                        childNode = curNode.left;
                    }
                    else if (curNode.right)
                    {
                        childNode = curNode.right;
                    }
 
                    if (parentNode == null)
                    {
                        rootNode = childNode;
                    }
                    else if (isLeftChild)
                    {
                        parentNode.left = childNode;
                    }
                    else
                    {
                        parentNode.right = childNode;
                    }
 
                    return true;
                }
                else if (value < curNode.value)
                {
                    parentNode = curNode;
                    isLeftChild = true;
                    curNode = curNode.left;
                }
                else
                {
                    parentNode = curNode;
                    isLeftChild = false;
                    curNode = curNode.right;
                }
            }
 
            return false;
        }
 
        public function removeMinNode(rootNode:Node, rootParentNode:Node):Node
        {
            var curNode:Node = rootNode;
            var leftFlag:Boolean = false;
            while (curNode.left)
            {
                rootParentNode = curNode;
                curNode = curNode.left;
                leftFlag = true;
            }
 
            if (leftFlag)
            {
                rootParentNode.left = curNode.right;
            }
            else
            {
                rootParentNode.right = curNode.right;
            }
 
            return curNode;
        }
    }
}