封装数据结构-2

一、什么是二叉树

二叉树是指每个节点最多含有两个子树的树结构。

特点：

• 所有节点最多拥有两个子节点，即度不大于 2
• 左子树的键值小于根的键值，右子树的键值大于根的键值。

二、二叉树结构

每一个结点（除叶子结点外）都有左子树和右子树.

// 结点
var Node = function (key) {
  this.key = key;
  this.left = null;
  this.right = null;
};

三、遍历二叉树

• 先序遍历 （根 => 左结点 => 右结点）
• 中序遍历 （左结点 => 根 => 右结点）
• 后序遍历 （左结点 => 右结点 => 根）

根据上图：

• 先序遍历：ADBEFGC
• 中序遍历：DBEAFGC
• 后序遍历：DEBGFCA

代码封装:

// 中序遍历
function(node) {
	 if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
		//访问左子树
		inOrderTraverseNode(node.left);
		console.log(node.key)
		inOrderTraverseNode(node.right);
		}
		//如果为空，程序回溯，将结点的值输出
}

// 前序遍历
function(node) {
	if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
		console.log(node.key)
		//访问左子树
		preOrderTraverseNode(node.left);
		preOrderTraverseNode(node.right);
	}
			//如果为空，程序回溯，将结点的值输出
}

// 后序遍历
function(node) {
	if (node !== null) { // 判断参数（左孩子、右孩子、根结点）的值是否不为空
        //访问左子树
		postOrderTraverseNode(node.left);
		postOrderTraverseNode(node.right);
		console.log(node.key);
		}
	//如果为空，程序回溯，将结点的值输出
}

四、结点插入二叉树

根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值

比如：687234501 这串数字插入到二叉树中 代码封装：

// 插入到二叉树
var insertNode = function (node, newNode) {
  if (newNode.key < node.key) {
    //左子树
    if (node.left === null) {
      // 左孩子为空
      node.left = newNode;
    } else {
      // 再次与左孩子的左孩子的值进行比较
      insertNode(node.left, newNode);
    }
  } else {
    //右子树
    if (node.right === null) {
      node.right = newNode;
    } else {
      insertNode(node.right, newNode);
    }
  }
};
// 创建结点及判断该结点是否为根结点并插入到二叉树中
this.insert = function (key) {
  var newNode = new Node(key);
  if (root === null) {
    // 二叉树中根节点为空
    root = newNode;
  } else {
    insertNode(root, newNode);
  }
};

五、寻找二叉树的最大最小值

根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值

得：

• 最小值是二叉树最左边的叶子结点。
• 最大值是二叉树最右边的叶子结点。

代码封装：

// 最小值
function(node) {
	if (node) {
		while (node && node.left !== null) {
			node = node.left
		}
		return node.key
	}
	return null
}

// 最大值
function(node) {
	if (node) {
		while (node && node.right !== null) {
			node = node.right
		}
		return node.key
	}
	return null
}

六、寻找二叉树的特定值

根据二叉树的特点：左子树的键值小于根的键值，右子树的键值大于根的键值

得：

• 如果该值小于该结点则向左子树遍历。
• 如果该值大于该结点则向右子树遍历。
• 遍历到叶结点，还为找到该值，则该树没有改特定值。

代码封装：

var searchNode = function (node, key) {
  if (node === null) {
    return false;
  }
  if (key < node.key) {
    return searchNode(node.left, key);
  } else if (key > node.key) {
    return searchNode(node.right, key);
  } else {
    return true;
  }
};

七、删除结点并保持二叉树结构不变

1. 情况一：删除的结点是叶子结点：直接删除。
2. 情况二：该结点小于(大于)当前遍历结点的值，则继续遍历左子树(右子树)。
3. 情况三：结点刚好等于当前遍历结点值，此时还有分四种情况进行讨论（有左右子树，没有左子树，没有右子树，没有左右子树）
4. 没有左右子树情况下，直接删除（node =null return node），即第一种情况。
   • 没有左子树 将 删除结点的右子树 赋值给 上层结点 的左子树或者右子树。
   • 没有右子树 将 删除结点的左子树 赋值给 上层结点 的左子树或者右子树。
   • 有左右子树 （1）在该结点的右子树中查找到最小值结点，（2）更新要删除结点的值为最小值，（3）删除最小值结点

代码封装：

//找到最小值的结点
function(node) {
	if (node) {
		while (node && node.left !== null) {
			node = node.left;
		}
		return node
	}
	return null
}
//删除结点
function(node, key) {
	if (node === null) {
		return null;
	}

	if (key < node.key) {
		node.left = removeNode(node.left, key)
		return node;
	} else if (key > node.key) {
		node.right = removeNode(node.right, key)
	} else { //相等
		//没有左右子树，直接node 赋值为 null 返回null通过程序的回溯将node.left 或 node.right 赋值为 null
		if (node.left === null && node.right === null) {
			node = null;
			return node;
		}
		//没有左子树，将 删除结点的右子树 赋值给  上层结点 的左子树或者右子树
		if (node.left === null) {
			node = node.right;
			return node;
		}
		//没有右子树，将 删除结点的左子树 赋值给  上层结点 的左子树或者右子树
		if (node.right === null) {
			node = node.left;
			return node;
		}
		//结点包含左子树和右子树

		//在该结点的右子树中查找到最小值结点
		var aux = findMinNode(node.right);
		//更新要删除结点的值为最小值
		node.key = aux.key;
		//删除最小值结点
		node.right = removeNode(node.right, aux.key);
		return node;
	}
}

源码下载 (opens new window)