网站建设全,南宁微网站开发,网站建站建设上海黔文信息科技有限公司30,中国建筑师网官网树是一种非线性的数据结构#xff0c;以分层的方式存储数据。 二叉树#xff1a;查找非常快#xff0c;而且二叉树添加或者删除元素也非常快。 形象的可以描述为组织结构图#xff0c;用来描述一个组织的结构。树是由边连接的点组成。树的一些基本概念#xff1a; … 树是一种非线性的数据结构以分层的方式存储数据。 二叉树查找非常快而且二叉树添加或者删除元素也非常快。 形象的可以描述为组织结构图用来描述一个组织的结构。树是由边连接的点组成。树的一些基本概念 根节点一棵树最上面的节点。 父节点一个节点下面连接多个节点该节点是父节点。 子节点父节点下面的节点。一个节点可以有01或者多个子节点 叶子节点没有任何子节点的节点。 路径从一个节点到另一个节点的这一组边。 树的遍历以某种特定顺序访问树中所有的节点。 树的分层根节点是0层它的子节点是第一层以此类推。 树的深度书的层数就是深度。 键每个节点都有一个与之相关的值。 二叉树和二叉查找树 二叉树一种特殊的树子节点不超过两个将子树节点的个数限定为2可以写出高效的程序在树中插入、查找、删除数据。 左右节点父节点的两个子节点。 二叉查找树是一种特殊的二叉树相对较小的节点存在左节点较大的存在右节点。这一特性是的查找的效率很高。 1、实现二叉查找树 又节点组成定义的第一个对象是Node,和链表的Node对象相似。 Node对象既能保存保存数据也能保存和其他节点链接left,right,show()用来显示保存在节点中的数据。 function Node(data,left,right) {this.data data;this.left left;this.right right;//this.show show;}Node.prototype.show function() {return this.data;}; 二叉树的创建binary search tree 二叉树的创建binary search tree该类只有一个数据成员表示二叉树查找树根节点的Node对象初始化null;BST有一个insert()方法用来插入新节点有点复杂首先创建一个Node对象将对象传入该数据中。检查BST是否有根结点如果没有则是新树该节点是根节点。否则待插入节点不是根节点需要遍历BST找到插入的适当位置。该过程类似与遍历链表。用一个变量存储当前结点一层层地遍历BST。进入BST以后下一步就是决定将节点放在什么地方找到正确的插入点。 1设置根节点为当前节点。 2如果待插入节点保存的数据小于当前节点则设置新的当前节点为原节点的左节点反之4 3如果当前节点的左节点为null就将新的节点插入这个位置退出循环反之执行下一次循环。 4设置新的当前节点为原节点的右节点。 5如果当前节点的右节点为null就将新的节点插入这个位置推出循环反之执行下一次循环 function BST() {this.root null;//this.insert insert;this.preOrder preOrder;//先序遍历this.inOrder inOrder;//中序遍历this.postOrder postOrder;//后序遍历
}BST.prototype.insert function(data) {var _node new Node(data,null,null);if(this.root null) {this.root _node;}else{var _current this.root;var _parent;while(true) {_parent _current;if(data _current.data) {_current _current.left;if(_current null) {_parent.left _node;break;}}else{_current _current.right;if(_current null) {_parent.right _node;break;}}}}}; 2、遍历二叉树 方式先序中序后序。都是以根为参照访问 先序先访问根节点再以升序的方式访问左子树和右子树。 中序以升序的方式访问左中右的次序。 后序先访问叶子节点从左子树到右子树再到根节点。 //先序遍历preOrderfunction preOrder (node) {if(!(node null)) {console.log(node.show());preOrder(node.left);preOrder(node.right);}}//test...var bst new BST();bst.insert(23);bst.insert(45);bst.insert(16);bst.insert(37);bst.insert(3);bst.insert(99);bst.insert(22);preOrder(bst.root);//中序遍历inOrderfunction inOrder (node) {if(!(node null)) {inOrder(node.left);console.log(node.show());inOrder(node.right);}}console.log(--------------------);inOrder(bst.root);//后序遍历inOrderfunction postOrder (node) {if(!(node null)) {postOrder(node.left);postOrder(node.right);console.log(node.show());}}console.log(--------------------);postOrder(bst.root); //完整代码 ~(function() {function Node(data,left,right) {this.data data;this.left left;this.right right;//this.show show;}Node.prototype.show function() {return this.data;};function BST() {this.root null;//this.insert insert;this.preOrder preOrder;//先序遍历this.inOrder inOrder;//中序遍历this.postOrder postOrder;//后序遍历
}BST.prototype.insert function(data) {var _node new Node(data,null,null);if(this.root null) {this.root _node;}else{var _current this.root;var _parent;while(true) {_parent _current;if(data _current.data) {_current _current.left;if(_current null) {_parent.left _node;break;}}else{_current _current.right;if(_current null) {_parent.right _node;break;}}}}};//先序遍历preOrderfunction preOrder (node) {if(!(node null)) {console.log(node.show());preOrder(node.left);preOrder(node.right);}}//中序遍历inOrderfunction inOrder (node) {if(!(node null)) {inOrder(node.left);console.log(node.show());inOrder(node.right);}}//后序遍历inOrderfunction postOrder (node) {if(!(node null)) {postOrder(node.left);postOrder(node.right);console.log(node.show());}}})(); 3、二叉树上的查找 1查找最小值2查找最大值3查找给定值。 最大最小值的查找比较简单只要遍历到最左最右即可。 BST.prototype.getMin function() {var _current this.root;while(!(_current.left null)) {_current _current.left;}return _current.data;};BST.prototype.getMax function () {var _current this.root;while(!(_current.right null)) {_current _current.right;}return _current.data;};console.log(-----------);console.log( bst.getMin() );console.log( bst.getMax() ); 查找给定值find(); 需要比较该值和当前节点上的值的大小。通过比较大小确定左遍历还是右遍历。 BST.prototype.find function(data) {var _current this.root;while(_current ! null) {if(_current.data data) {return _current;}else if(data _current.data) {_current _current.left;}else{_current _current.right;}}return null;//没找到返回null};console.log(-----------);console.log( bst.find(99) ); 4、删除二叉查找树上的节点 删除操作相对复杂分为三种情况 1删除叶子节点没有子节点的节点2删除只有一个子节点3删除包含两个子节点 删除时要删除数据和删除节点。算法具体过程先判断当前节点是否包含待删除的数据如果包含则删除该节点。如果不包含则比较当前节点上的数据和待删除的数据(删除根节点)。如果不包含则比较当前节点的数据和待删除的数据。如果待删除数据小于当前节点上的数据则移至当前结点的左子树节点继续比较如果大于当前节点上的数据则移至当前节点的右子节点继续比较。叶子节只需要将从父节点指向它的链接指向null;删除节点只包含一个子节点原本只想他的节点就的做些调整使其指向它的子节点。删除包含两个子节点一种是查找待删除节点左子树上的最大值要么查找其右子树上的最小值。这个过程有两个方法完成一个删除数据remove();一个删除节点removeNode(); 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) {if(node.left null node.right null) {//叶子节点return null;}if(node.left null) {//没有左子树return node.right;}if(node.right null) {//没有右子树return node.left;}//有两个子节点的节点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);return node;}else {node.right removeNode(node.right,data);return node;}}//bst.remove(3);preOrder(bst.root);//console.log( bst.show() ); 转载于:https://www.cnblogs.com/intelwisd/p/7755534.html
