"use?strict";
//????????-8-
//?????3?????????10
//??1?????6?????????14
//????4??7??????13
var?nodes?=?[8,?3,?10,?1,?6,?14,?4,?7,?13];
function?BinaryTree()?{
????//↓↓↓↓↓↓↓↓二叉樹創(chuàng)建↓↓↓↓↓↓↓↓
????var?Node?=?function?(key)?{
????????this.key?=?key;
????????this.left?=?null;
????????this.right?=?null
????};
????var?root?=?null;

????function?insertNode(node,?newNode)?{
????????if?(newNode.key?<?node.key)?{
????????????if?(node.left?===?null)
????????????????node.left?=?newNode;
????????????else
????????????????insertNode(node.left,?newNode);
????????}?else?{
????????????if?(node.right?===?null)
????????????????node.right?=?newNode;
????????????else
????????????????insertNode(node.right,?newNode);
????????}
????}

????this.insert?=?function?(key)?{
????????var?newNode?=?new?Node(key);
????????if?(root?===?null)
????????????root?=?newNode;
????????else
????????????insertNode(root,?newNode)
????};
????//↑↑↑↑↑↑↑↑二叉樹創(chuàng)建↑↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓前序遍歷的代碼實現(xiàn)↓↓↓↓↓↓↓↓
????function?preOrderTraverseNode(node,?callback)?{
????????if?(node)?{
????????????callback(node.key)
????????????preOrderTraverseNode(node.left,?callback)
????????????preOrderTraverseNode(node.right,?callback)
????????}
????}

????this.preOrderTraverse?=?function?(callback)?{
????????preOrderTraverseNode(root,?callback)
????}
????//↑↑↑↑↑↑↑↑前序遍歷的代碼實現(xiàn)↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓中序遍歷的代碼實現(xiàn)↓↓↓↓↓↓↓↓
????function?inOrderTraverseNode(node,?callback)?{
????????if?(node)?{
????????????inOrderTraverseNode(node.left,?callback)
????????????callback(node.key);
????????????inOrderTraverseNode(node.right,?callback)
????????}
????}

????this.inOrderTraverse?=?function?(callback)?{
????????inOrderTraverseNode(root,?callback)
????}
????//↑↑↑↑↑↑↑↑中序遍歷的代碼實現(xiàn)↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓后序遍歷的代碼實現(xiàn)↓↓↓↓↓↓↓↓
????function?postOrderTraverseNode(node,?callback)?{
????????if?(node)?{
????????????postOrderTraverseNode(node.left,?callback)
????????????postOrderTraverseNode(node.right,?callback)
????????????callback(node.key);
????????}
????}

????this.postOrderTraverse?=?function?(callback)?{
????????postOrderTraverseNode(root,?callback)
????}
????//↑↑↑↑↑↑↑↑后序遍歷的代碼實現(xiàn)↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓最小數(shù)↓↓↓↓↓↓↓↓
????function?minNode(node)?{
????????if?(node)?{
????????????while?(node?&&?node.left?!==?null)?{
????????????????node?=?node.left
????????????}
????????????return?node.key;
????????}
????????return?null
????}

????this.min?=?function?()?{
????????return?minNode(root)
????}
????//↑↑↑↑↑↑↑↑最小數(shù)↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓最大數(shù)↓↓↓↓↓↓↓↓
????function?maxNode(node)?{
????????if?(node)?{
????????????while?(node?&&?node.right)?{
????????????????node?=?node.right
????????????}
????????????return?node.key;
????????}
????????return?null
????}

????this.max?=?function?()?{
????????return?maxNode(root)
????}
????//↑↑↑↑↑↑↑↑最大數(shù)↑↑↑↑↑↑↑
????//↓↓↓↓↓↓↓↓查找↓↓↓↓↓↓↓↓
????function?searchNode(node,?key)?{
????????if?(node?===?null)
????????????return?false;
????????if?(key?<?node.key)
????????????return?searchNode(node.left,?key)
????????else?if?(key?>?node.key)
????????????return?searchNode(node.right,?key)
????????return?true
????}

????this.search?=?function?(key)?{
????????return?searchNode(root,?key)
????}
????//↑↑↑↑↑↑↑↑查找↑↑↑↑↑↑↑
????var?findMinNode?=?function?(node)?{
????????if?(node)?{
????????????while?(node?===?null?&&?node.left?!==?null)?{

????????????}
????????????return?node;
????????}
????????return?null
????};
????//↓↓↓↓↓↓↓↓二叉樹葉子節(jié)點的刪除原理↓↓↓↓↓↓↓↓
????function?removeNode(node,?key)?{
????????if?(node?===?null)
????????????return?null;
????????if?(key?<?node.key)?{
????????????node.left?=?removeNode(node.left,?key)
????????????return?node
????????}?else?if?(key?>?node.key)?{
????????????node.right?=?removeNode(node.right,?key)
????????????return?node
????????}?else?{
????????????if?(node.left?===?null?&&?node.right?===?null)?{
????????????????node?=?null;
????????????????return?node
????????????}else
????????????if?(node.left?===?null)?{
????????????????node?=?node.right;
????????????????return?node;
????????????}else?if?(node.right?===?null)?{
????????????????node?=?node.left;
????????????????return?node;
????????????}
????????????//左右兩個節(jié)點刪除
????????????var?aux?=?findMinNode(node.right);
????????????node.key?=?aux.key;
????????????node.right?=?removeNode(node.right,aux.key)
????????????return?node
????????}

????}

????this.remove?=?function?(key)?{
????????return?removeNode(root,?key)
????}
????//↑↑↑↑↑↑↑↑二叉樹葉子節(jié)點的刪除原理↑↑↑↑↑↑↑
}
var?binaryTree?=?new?BinaryTree();
nodes.forEach(function?(key)?{
????binaryTree.insert(key)
});
function?callback(key)?{
????console.log(key);
}
//?binaryTree.preOrderTraverse(callback);
//?binaryTree.inOrderTraverse(callback);
//?binaryTree.postOrderTraverse(callback);
//?console.log(nodes,?'最小數(shù):',?binaryTree.min());
//?console.log(nodes,?'最大數(shù):',?binaryTree.max());
binaryTree.remove(3)
binaryTree.inOrderTraverse(callback);