由于基礎(chǔ)比較差，什么設(shè)計(jì)模式，數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)。。。均沒有學(xué)過，著實(shí)讓人著急。沒辦法，只能耐著性子慢慢來。把遇到的東西一點(diǎn)一點(diǎn)搞懂。本篇就來一點(diǎn)提升內(nèi)功的，數(shù)據(jù)結(jié)構(gòu)中的二叉樹，注意，不是二叉查找樹，后面我還會練習(xí)二叉查找樹。
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.
意思是說二叉樹是一種數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，也就是左右兩個子節(jié)點(diǎn)。當(dāng)然，也有三叉樹，四叉樹。。。n叉樹，只是二叉樹我們最常用。
特點(diǎn)：
1、每個結(jié)點(diǎn)最多有兩顆子樹，結(jié)點(diǎn)的度最大為2，所以樹的度也是2。
2、左子樹和右子樹是有順序的，次序不能顛倒。
3、即使某結(jié)點(diǎn)只有一個子樹，也要區(qū)分左右子樹。
種類：
1、滿二叉樹
2、完全二叉樹
3、非完全二叉樹
這里不給出具體的定義：滿二叉樹很好理解，完全二叉樹主要要學(xué)會跟滿二叉樹對比，就可以判斷出是否是完全二叉樹，除了完全二叉樹之外的數(shù)，都是非完全二叉樹。
搜了下，二叉樹的各種性質(zhì)，看的有點(diǎn)頭大。我就以簡單的用法入手，看代碼中怎么實(shí)現(xiàn)簡單的定義與使用，下面就來看代碼。
對于二叉樹的定義相對比較簡單，設(shè)置左右節(jié)點(diǎn)即可。
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) 獲取二叉樹節(jié)點(diǎn)總數(shù)
/**
* 獲取節(jié)點(diǎn)總數(shù)
* @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) 獲取葉子節(jié)點(diǎn)總數(shù)
/**
* 獲取所有葉子節(jié)點(diǎn)
* @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層節(jié)點(diǎn)數(shù)
/**
* 獲取K層節(jié)點(diǎn)數(shù)
* @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) 層次遍歷，每一層從左向右遍歷
要點(diǎn)：
1.利用隊(duì)列添加每一層節(jié)點(diǎn)，進(jìn)行遍歷
2.如果當(dāng)前節(jié)點(diǎn)存在子節(jié)點(diǎn)，加到隊(duì)列尾部，下次循環(huán)遍歷取出
/**
* 層次遍歷，每一層從左向右遍歷
* @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()) {
//用于裝每一層的節(jié)點(diǎn)值
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) 計(jì)算二叉樹最大寬度
要點(diǎn)：
過程同層次遍歷類似，遍歷每一層時，比較每一層的最大寬度，作為二叉樹的最大寬度
/**
* 計(jì)算二叉樹的最大寬度，通過使用隊(duì)列計(jì)算，每一層的節(jié)點(diǎn)數(shù)即為每一層的寬度取出最大的一層的寬度
* @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);
}
總結(jié)
上面的算法使用基本上采用遞歸的方式，遞歸的思想在編程中還是很重要的，要注意慢慢培養(yǎng)，另外，要想很好的理解遞歸的過程，需要學(xué)習(xí)一下棧幀的概念，可以閱讀《深入理解計(jì)算機(jī)系統(tǒng)》這本書，下篇將對二叉樹其他算法進(jìn)行練習(xí)，敬請期待！
