一、概念
- 樹：由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上蔗候，而葉朝下的。
- 二叉樹：每個結(jié)點至多只有二棵子樹埂软。
- 滿二叉樹：葉子節(jié)點都在同一層并且除葉子節(jié)點外的所有節(jié)點都有兩個子節(jié)點锈遥。
- 完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d（d>1）。除第d層外的所有節(jié)點構(gòu)成滿二叉樹所灸，且第d層所有節(jié)點從左向右連續(xù)地緊密排列丽惶，這樣的二叉樹被稱為完全二叉樹；
- 二叉查找樹(BST)：若任意節(jié)點的左子樹不空庆寺，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值蚊夫； 若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值懦尝； 任意節(jié)點的左知纷、右子樹也分別為二叉查找樹；
- 平衡二叉樹(AVL)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1陵霉，并且左右兩個子樹都是一棵平衡二叉樹琅轧，同時，平衡二叉樹必定是二叉搜索樹踊挠。
二乍桂、二叉樹性質(zhì)
- 在二叉樹中，第i層的結(jié)點總數(shù)不超過2^(i-1)效床；
- 深度為h的二叉樹最多有2h-1個結(jié)點(h>=1)睹酌，最少有h個結(jié)點；
- 對于任意一棵二叉樹剩檀，如果其葉結(jié)點數(shù)為N0憋沿，而度數(shù)為2的結(jié)點總數(shù)為N2， 則N0=N2+1沪猴；
- 具有n個結(jié)點的完全二叉樹的深度為int（log2n）+1
三辐啄、二叉樹常見算法題
class TreeNode {
TreeNode left;
TreeNode right;
int value;
public TreeNode(int v) {
value = v;
}
}
public class test {
/**
* 構(gòu)建完全二叉查找樹 4 2 6 1 3 5 7
*/
public static TreeNode getBinarySortTree() {
TreeNode root = new TreeNode(4);
TreeNode l = new TreeNode(2);
TreeNode r = new TreeNode(6);
TreeNode ll = new TreeNode(1);
TreeNode lr = new TreeNode(3);
TreeNode rl = new TreeNode(5);
TreeNode rr = new TreeNode(7);
root.left = l;
root.right = r;
l.left = ll;
l.right = lr;
r.left = rl;
r.right = rr;
return root;
}
/**
* 隨便構(gòu)建一棵二叉樹
*/
public static TreeNode getBinaryTree() {
TreeNode root = new TreeNode(4);
TreeNode l = new TreeNode(2);
TreeNode r = new TreeNode(6);
TreeNode lr = new TreeNode(3);
TreeNode rl = new TreeNode(5);
TreeNode rr = new TreeNode(7);
TreeNode lrl = new TreeNode(1);
root.left = l;
root.right = r;
l.right = lr;
r.left = rl;
r.right = rr;
lr.left = lrl;
return root;
}
/**
* 1 二叉樹的遍歷
*
* @param args
*/
// 前序遍歷： 根左右
//遞歸
public static void preOrder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.value);
preOrder(root.left);
preOrder(root.right);
}
//非遞歸
public static void preOrder2(TreeNode head) {
if (head == null) {
return;
}
//幾乎與層序遍歷一樣，除了隊列換成堆棧
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
head = stack.pop();
System.out.print(head.value + " ");
if (head.right != null)
stack.push(head.right);
if (head.left != null)
stack.push(head.left);
}
}
// 中序遍歷： 左根右
//遞歸
public static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.value);
inOrder(root.right);
}
//非遞歸
public static void midOrder2(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
// 當(dāng)前節(jié)點不為空, 將自己壓進(jìn)棧并將自己的左孩子作為當(dāng)前節(jié)點（壓入左邊界）
stack.push(head);
head = head.left;
} else {
// 當(dāng)前節(jié)點為空（沒有左孩子了）, 將棧頂元素彈出作為當(dāng)前節(jié)點, 并將當(dāng)前節(jié)點的右孩子壓進(jìn)棧
head = stack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
// 后序遍歷： 左右根
//遞歸
public static void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.value);
}
//非遞歸
public static void postOrder2(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();//借助輔助存儲實現(xiàn) 根右左运嗜，利用棧的特性輸出左右根
stack1.push(head);
while (!stack1.isEmpty()) {
head = stack1.pop();
stack2.push(head);
// 有左孩子就先壓入左孩子
if (head.left != null)
stack1.push(head.left);
// 有右孩子就后壓入右孩子
if (head.right != null)
stack1.push(head.right);
}
// 逆序打印 根 右 左 的結(jié)果壶辜，就是后序遍歷的結(jié)果
while (!stack2.isEmpty())
System.out.print(stack2.pop().value + " ");
}
// 層次遍歷
public static void levelOrder(TreeNode root) {
if (root == null) {
return;
}
// 這里借助隊列來實現(xiàn)
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.value);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
/**
* 2 二叉樹深度、葉子節(jié)點相關(guān)
*/
// 求二叉樹的深度
public static int getTreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
int left = getTreeDepth(root.left);
int right = getTreeDepth(root.right);
// 返回max是最大深度担租，min是最小深度
return Math.max(left, right) + 1;
}
// 深度為N的滿二叉樹砸民，葉子結(jié)點數(shù)為：2^n-1
public static int getLeafCount(int N) {
return (int) Math.pow(2, N - 1);
}
// 3 反轉(zhuǎn)二叉樹/求二叉樹的鏡像
public static void invertBanaryTree(TreeNode root) {
if (root == null) {
return;
}
invertBanaryTree(root.left);
invertBanaryTree(root.right);
TreeNode node = root.left;
root.left = root.right;
root.right = node;
}
/**
* 4 二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表
*/
// 用于儲存中序遍歷當(dāng)前的節(jié)點，作為中間變量翩活，將雙向指針鏈接起來
static TreeNode cur = null;
// 遞歸到最深層阱洪，返回雙向鏈表的頭
static TreeNode head = null;
public static TreeNode convertDoubleLinkedList(TreeNode root) {
if (root == null) {
return null;
}
convertDoubleLinkedList(root.left); // 左
// 中序遍歷在中間進(jìn)行處理
// left= 前驅(qū)， right=后繼
root.left = cur;
if (cur != null) {
cur.right = root;
}
// pre指向root
cur = root;
// 遞歸到最深處才將頭賦值菠镇，也就是雙向鏈表的頭
if (head == null) {
head = root;
}
convertDoubleLinkedList(root.right); // 右
return head;
}
// 5 二叉查找樹的第k個結(jié)點(給定一棵二叉搜索樹冗荸，請找出其中的第k小的結(jié)點)
static int count = 0;
public static TreeNode getKthNode(TreeNode root, int k) {
if (root == null) {
return null;
}
// 二叉搜索樹按照中序遍歷的順序打印出來正好就是從小到大順序排列，然后找到第k個結(jié)點就是結(jié)果利耍。
TreeNode left = getKthNode(root.left, k);
if (left != null) {
return left;
}
count++;
if (count == k) {
return root;
}
TreeNode right = getKthNode(root.right, k);
if (right != null) {
return right;
}
return null;
}
// 6 二叉樹中和為某個值的路徑
public static void findPath(TreeNode root, int k) {
if (root == null)
return;
Stack<Integer> stack = new Stack<Integer>();
findPath(root, k, stack);
}
public static void findPath(TreeNode root, int k, Stack<Integer> path) {
if (root == null)
return;
if (root.left == null && root.right == null) {
if (root.value == k) {
for (int i : path) {
System.out.print(i + ",");
}
// 還要加上當(dāng)前等于K的value
System.out.print(root.value);
}
} else {
path.push(root.value);
findPath(root.left, k - root.value, path);
findPath(root.right, k - root.value, path);
path.pop();
}
}
public static void main(String[] args) {
TreeNode root = getBinarySortTree();
TreeNode linkedList = convertDoubleLinkedList(root);
TreeNode tail = null;
while (linkedList != null) {
System.out.print(linkedList.value);
tail = linkedList;
linkedList = linkedList.right;
}
System.out.println("");
while (tail != null) {
System.out.print(tail.value);
tail = tail.left;
}
}
}
簡單寫了幾道高頻率出現(xiàn)的二叉樹算法題蚌本，用得比較多的算法思想還是遞歸盔粹，大部分用到的核心邏輯還是排序。
