BinaryTree(1)

2018-01-08 阅读

由于基础比较差，什么设计模式，数据结构，操作系统。。。均没有学过，着实让人着急。没办法，只能耐着性子慢慢来。把遇到的东西一点一点搞懂。本篇就来一点提升内功的，数据结构中的二叉树，注意，不是二叉查找树，后面我还会练习二叉查找树。

1. 二叉树？

看一下wiki上的说明

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

意思是说二叉树是一种数据结构，每个节点最多有两个子节点，也就是左右两个子节点。当然，也有三叉树，四叉树。。。n叉树，只是二叉树我们最常用。


特点：
1、每个结点最多有两颗子树，结点的度最大为2，所以树的度也是2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。


种类：
1、满二叉树
2、完全二叉树
3、非完全二叉树

这里不给出具体的定义：满二叉树很好理解，完全二叉树主要要学会跟满二叉树对比，就可以判断出是否是完全二叉树，除了完全二叉树之外的数，都是非完全二叉树。

搜了下，二叉树的各种性质，看的有点头大。我就以简单的用法入手，看代码中怎么实现简单的定义与使用，下面就来看代码。对于二叉树的定义相对比较简单，设置左右节点即可。

public class TreeNode<T>{

    private T data;
    private TreeNode left;
    private TreeNode right;

}

2. 二叉树基本算法

(1) 查找最大深度

/**
	 * 获取最大深度
	 * @param root
	 * @return
	 */
	public int getMaxDepth(TreeNode<T> root){

		if (root == null) {
			return 0;
		}
		int left = getMaxDepth(root.left);
		int right = getMaxDepth(root.right);

		return 1 + Math.max(left, right);
	}

(2) 查找最小深度

/**
	 * 获取最小深度
	 * @param root
	 * @return
	 */
	public int getMinDepth(TreeNode<T> root) {

		if (root == null) {
			return 0;
		}

		if (root.left == null && root.right == null) {
			return 1;
		}
		return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;
	}

(3) 获取二叉树节点总数

/**
	 * 获取节点总数
	 * @param root
	 * @return
	 */
	public int totalNodes(TreeNode<T> root){
		if (root == null) {
			return 0;
		}
		int left = totalNodes(root.left);
		int right = totalNodes(root.right);

		return left + right + 1;
	}

(4) 获取叶子节点总数

/**
	 * 获取所有叶子节点
	 * @param root
	 * @return
	 */
	public int totalChildNodes(TreeNode<T> root){

		if (root == null) {
			return 0;
		}
		if (root.left == null && root.right == null) {
			return 1;
		}
		return totalChildNodes(root.left) + totalChildNodes(root.right);
	}

(5) 获取K层节点数

/**
	 * 获取K层节点数
	 * @param root
	 * @param k
	 * @return
	 */
	public int getLevelKNodes(TreeNode<T> root,int k){

		if (root == null || k < 1) {
			return 0;
		}
		if (k == 1) {
			return 1;
		}
		int left = getLevelKNodes(root.left, k-1);
		int right = getLevelKNodes(root.right, k-1);
		return left + right;
	}

(6) 层次遍历，每一层从左向右遍历

要点：

1.利用队列添加每一层节点，进行遍历

2.如果当前节点存在子节点，加到队列尾部，下次循环遍历取出

/**
	 * 层次遍历，每一层从左向右遍历
	 * @param root
	 * @return
	 */
	public List<List<T>> printTreeNodes(TreeNode<T> root) {

		List<List<T>> result = new ArrayList<List<T>>();
		if (root == null) {
			return result;
		}
		LinkedList<TreeNode<T>> linkedList = new LinkedList<TreeNode<T>>();
		linkedList.add(root);

		while (!linkedList.isEmpty()) {

			//用于装每一层的节点值
			ArrayList<T> row = new ArrayList<T>();

			//遍历每一层
			int size = linkedList.size();
			for (int i = 0; i < size; i++) {
				TreeNode<T> node = linkedList.removeFirst();
				row.add(node.getData());

				if (node.left != null) {
					linkedList.add(node.left);
				}
				if (node.right != null) {
					linkedList.add(node.right);
				}
			}
			result.add(row);
		}

		return result;
	}

(7) 计算二叉树最大宽度

要点：

过程同层次遍历类似，遍历每一层时，比较每一层的最大宽度，作为二叉树的最大宽度

/**
	 * 计算二叉树的最大宽度，通过使用队列计算，每一层的节点数即为每一层的宽度取出最大的一层的宽度
	 * @param root
	 * @return
	 */
	public int getBinaryTreeWidth(TreeNode<T> root){
		if (root == null) {
			return 0;
		}
		LinkedList<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
		queue.add(root);
		int width = 1;

		while (!queue.isEmpty()) {
			int size = queue.size();
			if (width < size) {
				width = size;
			}
			for (int i = 0; i < size; i++) {

				TreeNode<T> currentNode = queue.removeFirst();
				if (currentNode.left != null) {
					queue.add(currentNode.left);
				}
				if (currentNode.right != null) {
					queue.add(currentNode.right);
				}
			}
		}
		return width;
}

(8) 判断两个二叉树是否相同

/**
	 * 判断两个二叉树是否相同
	 * @param root1
	 * @param root2
	 * @return
	 */
	@SuppressWarnings("null")
	public boolean isSameTreeNode(TreeNode<T> root1,TreeNode<T> root2){

		if (root1 == null && root2 == null) {
			return true;
		}
		else if(root1 != null || root2 != null){
			return false;
		}
		else if (root1.data != root2.data) {
			return false;
		}

		boolean left = isSameTreeNode(root1.left, root2.left);
		boolean right = isSameTreeNode(root1.right, root2.right);
		return left && right;
	}

(9) 前序遍历（递归）

/**
	 * 前序遍历
	 * @param root
	 * @return
	 */
	public List<T> preOrder(TreeNode<T> root){

		List<T> list = new ArrayList<T>();
		if (root == null) {
			return list;
		}
		preOder(list, root);
		return list;
	}

	private void preOder(List<T> list,TreeNode<T> root){

		if (root == null) {
			return;
		}
		list.add(root.getData());
		preOder(list, root.left);
		preOder(list, root.right);

	}

(10) 后序遍历（递归）

/**
 * 后序遍历
 * @param root
 * @return
 */
public List<T> postOrder(TreeNode<T> root){

  List<T> list = new ArrayList<T>();
  if (root == null) {
    return list;
  }
  postOder(list, root);
  return list;
}

private void postOder(List<T> list,TreeNode<T> root){

  if (root == null) {
    return;
  }

  postOder(list, root.left);
  postOder(list, root.right);
  list.add(root.getData());

}

(11) 中序遍历（递归）

/**
 * 中序遍历
 * @param root
 * @return
 */
public List<T> InOrder(TreeNode<T> root){

  List<T> list = new ArrayList<T>();
  if (root == null) {
    return list;
  }
  InOder(list, root);
  return list;
}

private void InOder(List<T> list,TreeNode<T> root){

  if (root == null) {
    return;
  }

  InOder(list, root.left);
  list.add(root.getData());
  InOder(list, root.right);

}