数据结构与算法JavaScript描述练习------第10章二叉树和二叉查找树

于 2024-10-14 15:14:52 发布
阅读量229 收藏
点赞数 1
分类专栏： JavaScript 文章标签： javascript 前端 开发语言
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/maxiumII/article/details/142913855
版权

1. 为 BST 类增加一个新方法，该方法返回 BST 中节点的个数。


function Node(data, left, right) {
	this.data = data;
	this.left = left;
	this.right = right;
	this.show = show;
}

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.size = size;
	this.edgeCount = edgeCount;
}

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 inOrder(node) {
	if (!(node === null)) {
		inOrder(node.left);
		console.log(node.show() + " ");
		inOrder(node.right);
	}
}

function preOrder(node) {
	if (!(node === null)) {
		console.log(node.show() + " ");
		preOrder(node.left);
		preOrder(node.right);
	}
}

function postOrder(node) {
	if (!(node === null)) {
		postOrder(node.left);
		postOrder(node.right);
		console.log(node.show() + " ");
	}
}

function getMin() { 
	var current = this.root;
	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 find(data) {
	var current = this.root;
	while (current !== null) {
		if (current.data === data) {
			return current;
		} else if (current.data > data) {
			current = current.left;
		} else {
			current = current.right;
		}
	}
	return null;
}

function remove(data) {
	this.root = removeNode(this.root, data);
}

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;
	}
}

function getSmallest(node) {
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

function size(node) {
	if (node === null) {
		return 0;
	}
	return 1 + size(node.left) + size(node.right);
}

2. 为 BST 类增加一个新方法，该方法返回 BST 中边的个数。


function Node(data, left, right) {
	this.data = data;
	this.left = left;
	this.right = right;
	this.show = show;
}

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.size = size;
	this.edgeCount = edgeCount;
}

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 inOrder(node) {
	if (!(node === null)) {
		inOrder(node.left);
		console.log(node.show() + " ");
		inOrder(node.right);
	}
}

function preOrder(node) {
	if (!(node === null)) {
		console.log(node.show() + " ");
		preOrder(node.left);
		preOrder(node.right);
	}
}

function postOrder(node) {
	if (!(node === null)) {
		postOrder(node.left);
		postOrder(node.right);
		console.log(node.show() + " ");
	}
}

function getMin() { 
	var current = this.root;
	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 find(data) {
	var current = this.root;
	while (current !== null) {
		if (current.data === data) {
			return current;
		} else if (current.data > data) {
			current = current.left;
		} else {
			current = current.right;
		}
	}
	return null;
}

function remove(data) {
	this.root = removeNode(this.root, data);
}

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;
	}
}

function getSmallest(node) {
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

function size(node) {
	if (node === null) {
		return 0;
	}
	return 1 + size(node.left) + size(node.right);
}

function edgeCount(node) {
	if (node === null) {
		return 0;
	}
	return size(node) - 1;
}

3. 为 BST 类增加一个新方法 max()，该方法返回 BST 中的最大值。

        同getMax()

4. 为 BST 类增加一个新方法 min()，该方法返回 BST 中的最小值。

        同getMin()

5. 写一段程序，读入一个较大的文本文件，并将其中的单词保存到 BST 中，显示每个单词 在文本中出现的次数。


function Node(data, left, right) {
	this.data = data;
	this.left = left;
	this.right = right;
	this.show = show;
}

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

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.size = size;
	this.edgeCount = edgeCount;
}

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.word < current.data.word) {
				current = current.left;
				if (current === 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);
		console.log(node.show() + " ");
		inOrder(node.right);
	}
}

function preOrder(node) {
	if (!(node === null)) {
		console.log(node.show() + " ");
		preOrder(node.left);
		preOrder(node.right);
	}
}

function postOrder(node) {
	if (!(node === null)) {
		postOrder(node.left);
		postOrder(node.right);
		console.log(node.show() + " ");
	}
}

function getMin() { 
	var current = this.root;
	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 find(data) {
	var current = this.root;
	while (current !== null) {
		if (current.data.word === data.word) {
			return current;
		} else if (current.data.word > data.word) {
			current = current.left;
		} else {
			current = current.right;
		}
	}
	return null;
}

function remove(data) {
	this.root = removeNode(this.root, data);
}

function removeNode(node, data) {
	if (node === null) {
		return null;
	}
	if (data.word === node.data.word) {
		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.word < node.data.word) {
		node.left = removeNode(node.left, data);
		return node;
	} else {
		node.right = removeNode(node.right, data);
		return node;
	}
}

function getSmallest(node) {
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

function size(node) {
	if (node === null) {
		return 0;
	}
	return 1 + size(node.left) + size(node.right);
}

function edgeCount(node) {
	if (node === null) {
		return 0;
	}
	return size(node) - 1;
}

function updateWordCount(word) {
	var node = bst.find({word: word, count: 0});
	if (node === null) {
		bst.insert({word: word, count: 1});
	} else {
		node.data.count++;
	}
}
function displayWordCounts(node) {
    if (node !== null) {
        displayWordCounts(node.left);
        console.log(node.data.word + ": " + node.data.count);
        displayWordCounts(node.right);
    }
}
var inputString = "This is a test string with some words and some repeated words and some unique words";
var words = inputString.split(/\s+/);
var bst = new BST();
words.forEach(function(word) {
	updateWordCount(word);
});
displayWordCounts(bst.root);

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值