Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

update the second chapter exercises#16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
BubbleM wants to merge10 commits intooreillymedia:master
base:master
Choose a base branch
Loading
fromBubbleM:master
Open
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Binary file removed9781449364939_files.zip
View file
Open in desktop
Binary file not shown.
37 changes: 37 additions & 0 deletionsChapter1/test.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
// function factorial(number){
// if(number == 1){
// return number;
// }else{
// return number * factorial(number-1);
// }
// }
// print(factorial(5));

// function compare(num1, num2) {
// return num1 - num2;
// }
// var nums = [3,1,2,100,4,200];
// nums.sort(compare);
// print(nums); // 1,2,3,4,100,200


// Array.matrix = function(numrows,numcols,initial){
// var arr = [];
// for(var i=0;i<numrows;i++){
// var columns = [];
// for(var j=0;j<numcols;++j){
// columns[j]=initial;
// }
// arr[i]=columns;
// }
// return arr;
// }

// var nums = Array.matrix(5,5,[1,2,3]);
// print(nums);


var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];
print(grades[0][0]);
print(grades[0][1]);
print(grades[0][2]);
306 changes: 125 additions & 181 deletionsChapter10/bst.js
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,195 +1,139 @@
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
//二叉查找树：一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。
//实现二叉查找树
function Node(data,left,right){
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
this.show = show;
}

function show() {
return this.data;
function show(){
return this.data;
}

function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
this.preOrder = preOrder;
this.postOrder = postOrder;
this.getmin = getmin;
this.getmax = getmax;
this.find = find;
this.remove = remove;
this.removeNode = removeNode;
this.getSmallest = getSmallest;
function BST(){ //二叉查找树
this.root = null;//根节点 初始化为null，以此创建一个空节点
this.insert = insert;
this.inOrder = inOrder;
this.preOrder = preOrder;
this.postOrder = postOrder;
this.getMax = getMax;
this.getMin = getMin;
this.find = find;
this.update = update;
}

function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
}
else {
var current = this.root;
var parent;
while (true) {
parent = current;
if (data < current.data) {
current = current.left;
if (current == null) {
parent.left = n;
break;
}
}
else {
current = current.right;
if (current == null) {
parent.right = n;
break;
}
}
}
}
function insert(data){
var n = new Node(data,null,null);
if( this.root == null ){
this.root = n;
}else{
var current = this.root;//设根节点为当前节点
var parent;
while(true){
parent = current;
if(data < current.data){//如果带插入节点保存的数据小于当前节点
current = current.left;//设新的当前节点为原节点的左节点
if(current == null){//如果当前节点的左节点为null
parent.left = n;//将新的节点插入这个位置
break;//退出循环
}
}else{
current = current.right;
if(current == null){
parent.right = n;
break;
}
}
}
}
}

function inOrder(node){
if(!(node == null)){
inOrder(node.left);
putstr(node.show() + " ");
inOrder(node.right);
}
//中序遍历使用遍历的方式最容易实现。该方法需要以升序访问树中所有节点。 左 根 右
function inOrder(node){
if(!(node == null)){
inOrder(node.left);
putstr(node.show() + " ");
inOrder(node.right);
}
}

function preOrder(node){
if(!(node == null)){
putstr(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
//先序
function preOrder(node){
if(!(node == null)){
putstr(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}

function postOrder(node){
if(!(node == null)){
postOrder(node.left);
postOrder(node.right);
putstr(node.show() + " ");
}
//后序
function postOrder(node){
if(!(node == null)){
postOrder(node.left);
postOrder(node.right);
putstr(node.show() + " ");
}
}

function getmin() {
var current = this.root;
print("debug: " + current.data);
while (!(current.left == null)) {
current = current.left;
}
return current.data;
//查找最大值
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}

function getmax() {
var current = this.root;
while (!(current.right == null)) {
current = current.right;
}
return current.data;
}

function find(data) {
var current = this.root;
while (current.data != data) {
if (data < current.data) {
current = current.left;
}
else {
current = current.right;
}
if (current == null) {
return null;
}
}
return current;
//查找最小值
// 在BST上因为较小的值总是在左子节点上，查找最小值，只需要遍历左子树，直到找到最后一个节点
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}

function getSmallest(node) {
if (node.left == null) {
return node;
}
else {
return getSmallest(node.left);
}
//查找给定值
function find(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。
}

function remove(data) {
root = removeNode(this.root,data);
//从二叉查找树上删除节点
function remove(data){ //简单地接受待删除数据
root = removeNode(this.root,data);
}

function removeNode(node, data) {
if (node == null) {
return null;
}
if (data == node.data) {
// node has no children
if (node.left == null && node.right == null) {
return null;
}
// node has no left child
if (node.left == null) {
return node.right;
}
// node has no right child
if (node.right == null) {
return node.left;
}
// node has two children
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;
}
function removeNode(node,data){//删除节点
if(node == null){
return null;
}
if(data == node.data){ //判断当前节点是否包含待删除的数据
if(node.left == null && node.right == null){ //没有子节点的节点 叶子节点
return null;//只需将从父节点指向它的链接指向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;
}
}



var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
/*print("Inorder traversal: ");
inOrder(nums.root);
print("\n");
print("Preorder traversal: ");
preOrder(nums.root);
print("\n");
print("Postorder traversal: ");
postOrder(nums.root);
print("\n");
var min = nums.getmin();
print("The minimum value of the BST is: " + min);
var max = nums.getmax();
print("The maximum value of the BST is: " + max);
inOrder(nums.root);
print("\n");
putstr("Enter a value to search for: ");
var value = parseInt(readline());
var found = nums.find(value);
if (found != null) {
print("Found " + value + " in the BST.");
function update(data){
var grade = this.find(data);
grade.count++;
return grade;
}
else {
print(value + " was not found in the BST.");
}*/
inOrder(nums.root);
print("\n");
var num = parseInt(readline());
nums.remove(num);
inOrder(nums.root);
Loading
[8]ページ先頭
©2009-2025 Movatter.jp