树:以分层的方式存储数据;节点:根节点,子节点,父节点,叶子节点(没有任何子节点的节点);层:根节点开始0层;
二叉树:每个节点子节点不超过两个;查找快(比链表),添加,删除快(比数组);
BST:二叉树查找:
- 设置根节点为当前节点;
- 如果要插入的节点小于当前节点,则设置其左节点为新的当前节点;大于的话选右节点;
- 如果如果选择的节点为null,则将要插入的节点放在这个位置,退出;否则继续向下查找;
实现的基本代码:
function Node (data,left,right) { this.data = data; this.show = show;
this.left = left;
this.right = right;
} function show() { console.log(this.data); } function BST() { this.root = root; this.insert = insert; } function insert(data) { var n = new Node(data,null,null); if(this.root === null) { this.root = n; } else { var currNode = this.root,parent; while(true) { parent = currNode;
if(data == currNode.data) {
break;
} else if(data < currNode.data) { currNode = currNode.left; if(currNode === null) { parent.left = n; break; } } else { currNode = currNode.right; if(currNode === null) { parent.right = n; break; } } } } }
遍历查找:(名字即为要查找的节点的输出顺序)
- 中序遍历:升序遍历要查找的节点及其子孙节点;
//10,22,30,56,77,81,92
function inOrder(node) { if(!(node == null)) { inOrder(node.left); node.show(); inOrder(node.right); } }
操作:demo:
- 先序遍历:先输出要查找的节点,然后从左边的子节点开始依照先左后右输出;
//50,10,5,15,70,60,80
function preOrder(node) { if(!(node == null)) { node.show(); preOrder(node.left); preOrder(node.right); } }
操作:demo:
- 后序遍历:从要查找的节点的左节点最左边的子孙节点开始,按照左右各一次的顺序输出直到其左子节点;然后从其右节点的最左边的子孙节点开始;最后输出要查找的节点;
//3,22,16,37,99,45,23
function postOrder(node) { if(!(node == null)) { postOrder(node.left); postOrder(node.right); node.show(); } }
在二叉树上查找:
- 最大值:即遍历右子树
function getMax() { var currNode = this.root; while(!(currNode.right == null)) { currNode = currNode.right; } console.log(currNode.data);
return currNode; }
- 最小值:即遍历左子树
function getMin() { var currNode = this.root; while(!(currNode.left == null)) { currNode = currNode.left; } console.log(currNode.data);
return currNode; }
- 查找给定值:
function find(data) { var currNode = this.root; while(currNode != null) { if(currNode.data === data) { return currNode; } else if(data < currNode.data) { currNode = currNode.left; } else { currNode = currNode.right; } } return null; }
操作:demo:
- 删除节点:
- 先判断,如果当前节点包括则删除节点;如果不包括,则比较大小向下一层查找;
- 删除节点的时候,如果是叶子节点,则将其父节点指向它的引用指向null;
- 如果只包含一个子节点,则将其父节点指向它的引用指向这个子节点;
- 如果包含两个子节点,那么可以
- 查找待删节点的左子树的最大值;
- 查找待删节点的右子树的最小值;(这里选这种)
- 找到最小值之后,会用这个最小值创建一个一个临时节点,并将临时节点值复制到待删节点,最后删除临时节点;//等价于取小最小值节点替换掉待删节点;
function remove(data) { root = removeNode(this.root,data); } function getSmallest(node) { if (node.left == null) { return node; } else { return getSmallest(node.left); } } function removeNode(node,data) { if(node == null) { return null; } if(data === node.data) { //not child node; if(node.left == null && node.right == null) { return null; } //not left child node; if(node.left == null) { return node.right; } //not right child node; if(node.right == null) { return node.left; } //all have var tempNode = getSmallest(node.right); node.data = tempNode.data; node.right = removeNode(node.right,tempNode.data); return node; } else if(data < node.data) { node.left = removeNode(node.left,data);//set parent.left null to delete this node; return node; } else { node.right = removeNode(node.right,data); return node; } }
操作:demo:
- 计数:可以给Node添加this.count = 1;在添加数值的时候,虽然相同的数值不会重复加入,但可以记录其被添加的次数;