博客

二叉树

理论知识

树是一种

非线性

的数据结构，它是由n（n>=0）个有限结点组成的一个

具有层次关系的集合

。

• 树的特点：
  • 子树不相交（相交变成了图）
  • 除了根节点以外，其他节点有且只有一个父节点

特殊的二叉树

1. 满二叉树
   
   如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。即每层节点都达到了最大值，则这棵二叉树就是满二叉树。（度：一个节点拥有子树的数目称为节点的度）
2. 完全二叉树
   
   深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树

二叉树的性质

1. 二叉树的第i层上至多有2^(i -1)（i≥1）个节点
2. 深度为h的二叉树中至多含有2^h -1个节点
3. 若在任意一棵二叉树中，有n0个叶子节点（即n0个度为0的结点），有n2个度为2的节点，则必有n0=n2+1
4. 具有n个节点的满二叉树深为log2 n +1

树的遍历

中序遍历实现

// 中序遍历就是根中间遍历（左 根 右）
// 1. 递归实现
/*
root为二叉树的根节点
array默认是空数组，遍历之后的结果
*/
function inorderTraversal(root,array=[]){
	if(root){
		inorderTraversal(root.left,array);
		array.push(root.val);
		inorderTraversal(root.right,array);
	}
	return array;
}
// 2. 迭代实现（进阶）
function inorderTraversal(root){
	const result = [];
	const stack = [];
	let current = root;
	while(current || stack.length > 0){
		while(current){
			stack.push(current);
			current = current.left;
		}
		current = stack.pop();
		result.push(current.val);
		current = current.right
	}
	return result
}

先序遍历实现

// 根 左 右
// 1. 递归实现
function preorderTraversal(root,array=[]){
	if(root){
		array.push(root.val)
		preorderTraversal(root.left,array)
		preorderTraversal(root.right,array)
	}
	return array
}
// 2. 迭代实现
function preorderTraversal(root,array){
	const result = [];
	const stack = [];
	let current = root;
	while(current || stack.length > 0){
		while(current){
			result.push(current.val);
			stack.push(current);
			current = current.left;
		}
		current = stack.pop();
		current = current.right;
	}
	return result;
}

后序遍历实现

// 左 右 中
// 1. 递归实现
function postorderTraversal(root,array=[]){
	if(root){
		postorderTraversal(root.left,array);
		postorderTraversal(root.right,array);
		array.push(root.val);
	}
	return array;
}
// 2. 迭代实现
function postorderTraversal(root){
	const result = [];
	const stack = [];
	let current = root;
	while(current || stack.length>0){
		while(current){
			//这里的false用来标记该节点的右子树还未遍历
			stack.push([current,false]);
			current = current.left;
		}
		let [node,flag] = stack.pop()
		if(!flag){
			// 如果右子树还未遍历，就遍历右子树，并将该遍历的标志设为true
			stack.push([node,true])
			current = node.right
		}else{
			// 右子树已遍历，则该根节点的左右子树遍历结束，将该根节点push进去
			result.push(node.val)
		}
	}
}