深入学习二叉树和二叉查找树

Scroll Down

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构,以分层的方式存储数据。

树被用来存储具有层级关系的数据,比如文件系统中的文件。

树还可以用来存储有序列表。

树的定义

树是由一组以边连接的节点组成。公司的组织结构图就是一个树的例子。

image.png
组织结构图就是一种树


一棵树最上面的节点成为根节点。如果一个节点下面连接着多个节点,那么该节点称为父节点,它下面的节点称为子节点。一个节点可以有0个,1个或者多个子节点。没有任何子节点的节点称为叶子节点。下图展示了一些树的术语。

image.png


沿着一组特定的边,可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径。以特定的顺序访问树中所有的节点称为树的遍历。


树可以分为几个层次,根节点是第0层,它的子节点是第1层,子节点的子节点是第2层,以此类推。树中任何一层的节点都可以看成是子树的根,该子树包含根节点的子节点,子节点的子节点等。我们定义树的层数就是树的深度。


节点的高度:节点到叶子节点的最长路径(边树)。
节点的深度:根节点到这个节点所经历的边的个数。
节点的层数:节点的深度+1。
节点的高度:根节点的高度。


下面举个例子来看:


image.png


每一个节点都有一个与之关联的值,该值有时被称为键。


二叉树是一种特殊的树。它的子节点不超过2个。二叉树具有一些特殊的计算性质,使得在它之上的一些操作异常高效。

二叉树和二叉查找树

一个父节点的两个子节点分别称为左节点和右节点。左节点包含一组特定的值,右节点包含一组特定的值。

下图展示了一颗二叉树:
image.png


当考虑某种特殊的二叉树,比如二叉查找树时,确定子节点非常重要。二叉查找树是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中。这一特性使得查找的效率很高,对于数值和非数值的数据,比如单词和字符串,也是如此。


我们来看下图中的树:


image.png


编号2的二叉树中,叶子节点全在最底层,除了叶子节点以外的每个节点都有左右两个子节点,这种二叉树叫做满二叉树


编号3的二叉树中,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其它层的节点个数都达到最大,这种二叉树叫做完全二叉树




实现二叉查找树(BST)

定义 Node 对象。

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

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

现在可以创建一个 BST 类来表示二叉查找树。我们让类只包含一个数据成员:一个表示二叉查找树根节点的 Node 对象。该类的构造函数将根节点初始化为 null ,以此创建一个空节点。

BST 首先要有一个 insert() 方法,用来向树中插入新节点。首先要创建一个 Node 对象,将数据传入该对象保存。
其次,检查 BST 是否有根节点,如果没有,则这是棵新树,该节点就是根节点,这个方法到此也就结束了;否则,进入下一步。

如果待插入节点不是根节点,那么就准备遍历 BST ,找到插入的适当位置。该过程类似遍历链表。用一个节点保存当前节点,一层层地遍历 BST 。

进入 BST 以后,下一步就需要确定将该节点放在什么位置。找到正确的插入点时,会跳出循环。

查找正确的插入点的算法如下:

  1. 设根节点为当前节点;
  2. 如果待插入的节点小于当前节点,则设新的当前节点为原节点的左节点;反之,执行第四步;
  3. 如果当前节点的左节点为 null ,就将新的节点插入这个位置,退出循环;反之,继续执行下一次循环;
  4. 设新的当前节点为原节点的右节点;
  5. 如果当前节点的右节点为 null ,就将新的节点插入该位置,退出循环;反之,继续执行下一次循环。

image.png

function BST() {
	this.root = null;
	this.insert = insert;
  
	function insert(data) {
		var n = new Node(data, null, null);
		if(this.root == null) {
			this.root = n;
		}else {
			var currentNode = this.root;
			var parent;
			while(true) {
				parent = currentNode;
				if(data < currentNode.data) {
					currentNode = currentNode.left;
					if(currentNode == null) {
						parent.left = n;
						break;
					}
				}else {
					currentNode = currentNode.right;
					if(currentNode.data == null) {
						parent.right = n;
						break;
					}
				}
			}
		}
	}
  
}

另外一个写法,其实思路是一样的,但是上面的稍微简洁一些。(代码思路来自王争老师的《数据结构与算法之美 》)

function insert(data) {
		var node = new Node(data, null, null);
		if(this.root == null) {
			this.root = node;
		}else {
			p = this.root;
			while(p !== null) {
				if(data < p.data) {
					if(p.left == null) {
						p.left = node;
						return;
					}
					p = p.left;
				}else {
					if(p.right == null) {
						p.right = node;
						return;
					}
					p = p.right;
				}
			}
		}
	}

遍历二叉查找树

有三种遍历二叉树的方法:中序、先序、后序。

中序遍历按照节点上的键值,以升序访问 BST 上的所有节点。
先序遍历先访问根节点,然后以同样的方式访问左子树和右子树。
后序遍历先访问叶子节点,从左子树到右子树,再到根节点。

先序遍历是指,对于树中的任意节点来说,先打印这个节点,然后在打印它的左子树,最后打印它的右子树。
中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后打印它自己,最后打印它的右子树。
后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后打印它的右子树,最后打印它自己。

image.png


中序遍历的代码如下:

function inOrder(node) {
		if(!(node == null)) {
			this.inOrder(node.left);
			console.log(node.show());
			this.inOrder(node.right);
		}
	}

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
bst.inOrder(bst.root); // 16 17 19 34 35 36

下图展示中序遍历的访问路径:
image.png

先序遍历的代码如下:

function perOrder(node) {
		if(!(node == null)) {
			console.log(node.show());
			this.perOrder(node.left);
			this.perOrder(node.right);
		}
}

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)
console.log('先序遍历');
bst.perOrder(bst.root); // 17 16 19 34 35 36

下图展示先序遍历的访问路径:

image.png

后序遍历的代码:

var bst = new BST();
bst.insert(17)
bst.insert(19)
bst.insert(16)
bst.insert(34)
bst.insert(35)
bst.insert(36)

console.log('后序遍历');
bst.postOrder(bst.root); // 16 36 35 34 19 17

下图展示后序遍历的访问路径:

image.png

在二叉树上进行查找

对 BST 通常有以下三种类型的查找:

  • 查找给定值
  • 查找最大值
  • 查找最小值

查找最小值和最大值

因为较小的值总在左节点上,在 BST 上查找最小值,只需要遍历左子树,知道找到最后一个节点即可。

function getMin() {
		let currentNode = this.root;
		while(currentNode.left != null) {
			currentNode = currentNode.left;
		}
		return currentNode.data;
	}

在BST 上查找最大值,只需要遍历右子树,知道找到最后一个节点即可。

function getMax() {
		let currentNode = this.root;
		while(currentNode.right != null) {
			currentNode = currentNode.right;
		}
		return currentNode.data;
	}

查找给定值

在 BST 上查找给定的值,需要比较该值和当前节点值的大小。通过比较,就能确定如果给定值不在当前节点上,该向左遍历还是向右遍历。

image.png

function find(data) {
		var currentNode = this.root;
		while(currentNode != null) {
			if(currentNode.data == data) {
				return currentNode;
			}else if(currentNode.data < data) {
				currentNode = currentNode.right;
			}else {
				currentNode = currentNode.left;
			}
		}
		return null;
	}

如果找到给定值,该方法返回保存该值的方法;如果没找到,该方法返回 null。

从二叉树上删除节点

从 BST 上删除节点的操作最复杂,其复杂程度取决于删除哪个节点。如果删除没有子节点的节点,那么非常简单。如果节点只有一个子节点,就变得稍微复杂了。如果节点有两个子节点,是最复杂的。

分三种情况来处理:

  • 如果要删除的节点没有子节点,我们只需要将父节点中,指向要删除的节点的指针置为 null。比如图中删除节点55。
  • 如果要删除的节点只有一个子节点(左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中删除节点13。
  • 如果要删除的节点有两个子节点,我们需要找到这个节点右子树中的最小节点,把它替换到要删除节点上,然后再删除这个最小节点,因为最小节点中肯定没有左子节点,我们可以用这两个规则来进行删除操作,比如图中删除节点18。

image.png

function deleteNode(data) {
		var p = this.root; // p指向删除的节点,初始化为根节点
		var pp = null; // pp记录P的父节点
		while(p != null && p.data != data) {
			pp = p;
			if(data > p.data) {
				p = p.right;
			}else {
				p = p.left;
			}
		}
		if(p == null) return; // 没有找到

		if(p.left != null && p.right != null) { // 要删除的节点有两个子节点
			// 查找右子树中的最小节点
			var minP = p.right;
			var minPP = p; // minPP表示minP的父节点
			while(minP.left != null) {
				pnode = minP;
				minP = p.left;
			}
			p.data = minP.data; // 将minP的数据替换到p中
			p = minP; //下面就变成删除minP了
			pp = minP;

		}
		// 删除节点是叶子节点或者只有一个子节点
		var childNode = null;
		if(p.left != null) {
			childNode = p.left;
		}else if(p.right != null) {
			childNode = p.right;
		}else {
			chiildNode = null;
		}
		if(pp == null) {
			p = chiildNode; // 删除的是根节点
		}else if(pp.left == p) {
			pp.left = childNode;
		}else {
			pp.right = childNode;
		}
	}

实际上,关于二叉树的删除操作,还有个非常简单、取巧的方法,就是单纯地将已删除的节点标记为“已删除”,但并不是真正的删除。这样原本要删除的元素还存储在内存中,比较浪费内存空间,但是删除操作简单了很多,也没有增加插入和查找的代码实现的难度。

其他

二叉查找树还有一个重要的特性,就是中序遍历二叉查找树,可以输入有序的数据序列,时间复杂度是O(n),非常高效。因此二叉查找树也被叫做二叉排序树。

原文:https://github.com/maixiaojie/maixiaojie.github.io/issues/51