樹
1.樹、二叉樹
2.二叉查找樹
3.平衡二叉樹、紅黑樹
4.遞歸樹

一、樹

1.樹的常用概念
根節(jié)點(diǎn)、葉子節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)，還有節(jié)點(diǎn)的高度、深度以及層數(shù)，樹的高度。

2.概念解釋
節(jié)點(diǎn)：樹中的每個元素稱為節(jié)點(diǎn)
父子關(guān)系：相鄰兩節(jié)點(diǎn)的連線，稱為父子關(guān)系
根節(jié)點(diǎn)：沒有父節(jié)點(diǎn)的節(jié)點(diǎn)
葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)
父節(jié)點(diǎn)：指向子節(jié)點(diǎn)的節(jié)點(diǎn)
子節(jié)點(diǎn)：被父節(jié)點(diǎn)指向的節(jié)點(diǎn)
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的多個節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)關(guān)系
節(jié)點(diǎn)的高度：節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長路徑所包含的邊數(shù)
節(jié)點(diǎn)的深度：根節(jié)點(diǎn)到節(jié)點(diǎn)的路徑所包含的邊數(shù)
節(jié)點(diǎn)的層數(shù)：節(jié)點(diǎn)的深度+1（根節(jié)點(diǎn)的層數(shù)是1）
樹的高度：等于根節(jié)點(diǎn)的高度

二、二叉樹

1.概念
①什么是二叉樹？
每個節(jié)點(diǎn)最多只有2個子節(jié)點(diǎn)的樹，這兩個節(jié)點(diǎn)分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
②什么是滿二叉樹？
有一種二叉樹，除了葉子節(jié)點(diǎn)外，每個節(jié)點(diǎn)都有左右兩個子節(jié)點(diǎn)，這種二叉樹叫做滿二叉樹。
③什么是完全二叉樹？
有一種二叉樹，葉子節(jié)點(diǎn)都在最底下兩層，最后一層葉子節(jié)都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)個數(shù)都要達(dá)到最大，這種二叉樹叫做完全二叉樹。

2.完全二叉樹的存儲
①鏈?zhǔn)酱鎯?br /> 每個節(jié)點(diǎn)由3個字段，其中一個存儲數(shù)據(jù)，另外兩個是指向左右子節(jié)點(diǎn)的指針。我們只要拎住根節(jié)點(diǎn)，就可以通過左右子節(jié)點(diǎn)的指針，把整棵樹都串起來。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種方式實現(xiàn)的。
②順序存儲
用數(shù)組來存儲，對于完全二叉樹，如果節(jié)點(diǎn)X存儲在數(shù)組中的下標(biāo)為i，那么它的左子節(jié)點(diǎn)的存儲下標(biāo)為2i，右子節(jié)點(diǎn)的下標(biāo)為2i+1，反過來，下標(biāo)i/2位置存儲的就是該節(jié)點(diǎn)的父節(jié)點(diǎn)。注意，根節(jié)點(diǎn)存儲在下標(biāo)為1的位置。完全二叉樹用數(shù)組來存儲時最省內(nèi)存的方式。
3.二叉樹的遍歷
①前序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先打印這個節(jié)點(diǎn)，然后再打印它的左子樹，最后打印它的右子樹。
②中序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后再打印它的本身，最后打印它的右子樹。
③后序遍歷：對于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹，然后再打印它的右子樹，最后打印它本身。
前序遍歷的遞推公式：
preOrder? = print r->preOrder(r->left)->preOrder(r->right)
中序遍歷的遞推公式：
inOrder? = inOrder(r->left)->print r->inOrder(r->right)
后序遍歷的遞推公式：N
postOrder? = postOrder(r->left)->postOrder(r->right)->print r
時間復(fù)雜度：3種遍歷方式中，每個節(jié)點(diǎn)最多會被訪問2次，所以時間復(fù)雜度是O(n)。

三、二叉查找樹

二叉查找樹要求，在樹中的任意一個節(jié)點(diǎn)，其左子樹中的每個節(jié)點(diǎn)的值，都要小于這個節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)的值都大于這個節(jié)點(diǎn)的值.

1. 查找操作:

public class BinarySearchTree {private Node tree;public Node find(int data) {Node p = tree;while (p != null) {if (data < p.data) p = p.left;else if (data > p.data) p = p.right;else return p;}return null;}public static class Node {private int data;private Node left;private Node right;public Node(int data) {this.data = data;}} }

先取根節(jié)點(diǎn)，如果它等于我們要查找的數(shù)據(jù)，那就返回。
如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值小，那就在左子樹中遞歸查找。
如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值大，那就在右子樹遞歸查找.

2. 插入操作：

如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大，并且節(jié)點(diǎn)的右子樹為空，就將數(shù)據(jù)直接插到右子節(jié)點(diǎn)的位置。
如果不為空，就再遞歸遍歷右子樹，查找插入位置。
如果要插入的數(shù)據(jù)比節(jié)點(diǎn)數(shù)值小，并且節(jié)點(diǎn)的左子樹為空，就將數(shù)據(jù)插入到左子節(jié)點(diǎn)的位置
如果不為空，就再遞歸遍歷左子樹，查找插入位置。

public void insert(int data) {if (tree == null) {tree = new Node(data);return;}Node p = tree;while (p != null) {if (data > p.data) {if (p.right == null) {p.right = new Node(data);return;}p = p.right;} else { // data < p.dataif (p.left == null) {p.left = new Node(data);return;}p = p.left;}} }

3. 刪除操作：
1）要刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們只需要直接將父節(jié)點(diǎn)中，指向要刪除節(jié)點(diǎn)的指針置為null, 比如圖中的刪除節(jié)點(diǎn)55.
2）要刪除的節(jié)點(diǎn)只有一個子節(jié)點(diǎn)(只有左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)),我們只需要更新父節(jié)點(diǎn)中，指向要刪除節(jié)點(diǎn)的指針，讓它指向要刪除節(jié)點(diǎn)的子節(jié)點(diǎn)就好了。
3）要刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，我們需要找到這個節(jié)點(diǎn)的右子樹中的最小節(jié)點(diǎn)，把他替換到要刪除的節(jié)點(diǎn)上。然后再刪除掉這個最小節(jié)點(diǎn)，因為最小節(jié)點(diǎn)肯定沒有左子節(jié)點(diǎn)(如果沒有左子結(jié)點(diǎn)，那就不是最小節(jié)點(diǎn)了).

public void delete(int data) {Node p = tree; // p指向要刪除的節(jié)點(diǎn)，初始化指向根節(jié)點(diǎn)Node pp = null; // pp記錄的是p的父節(jié)點(diǎn)while (p != null && p.data != data) {pp = p;if (data > p.data) p = p.right;else p = p.left;}if (p == null) return; // 沒有找到// 要刪除的節(jié)點(diǎn)有兩個子節(jié)點(diǎn)if (p.left != null && p.right != null) { // 查找右子樹中最小節(jié)點(diǎn)Node minP = p.right;Node minPP = p; // minPP表示minP的父節(jié)點(diǎn)while (minP.left != null) {minPP = minP;minP = minP.left;}p.data = minP.data; // 將minP的數(shù)據(jù)替換到p中p = minP; // 下面就變成了刪除minP了 先付好值，執(zhí)行最后刪除的語句pp = minPP;}// 刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者僅有一個子節(jié)點(diǎn)Node child; // p的子節(jié)點(diǎn)if (p.left != null) child = p.left;else if (p.right != null) child = p.right;else child = null;//執(zhí)行最后刪除的語句if (pp == null) tree = child; // 刪除的是根節(jié)點(diǎn)else if (pp.left == p) pp.left = child;else pp.right = child; }

二叉查找樹可以支持快速地查找最大節(jié)點(diǎn)和最小節(jié)點(diǎn)，前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn).
中序遍歷二叉查找樹，可以輸出有序的數(shù)據(jù)序列，時間復(fù)雜度是O(n),非常高效。

完全二叉樹的高度小于等于log2n
平衡二叉查找樹的高度接近logn.
插入，刪除，查找的時間復(fù)雜度比較穩(wěn)定，為O(logn).

四、 散列表 vs 二叉查找樹

1） 散列表是無序存儲的，要有序的話，需要先排序， 二叉查找樹，只需要中序遍歷，就可以在O(n)時間復(fù)雜度內(nèi)，輸出有序的數(shù)據(jù)序列。

散列表擴(kuò)容耗時多，遇到散列沖突時，性能不穩(wěn)定，常用的平衡二叉樹性能穩(wěn)定，時間復(fù)雜度穩(wěn)定在O(logn)

3）一般來說，散列表查找，刪除，插入操作的時間復(fù)雜度是常量級的。但因哈希沖突的存在，這個常量不一定比logn小，加上哈希函數(shù)的耗時，也就未必比平衡二叉查找樹的效率高.

散列表構(gòu)造比二叉查找樹要復(fù)雜，需要考慮的東西很多。比如散列函數(shù)的設(shè)計，沖突接近方法，擴(kuò)容，縮容等.
平衡二叉查找樹只需要考慮平衡性這個問題。

5）為了避免過多的散列沖突，散列表裝在因子不能太大，特別是基于開放尋址法接近沖突的散列表.

N、思考

1.二叉樹有哪幾種存儲方式？什么樣的二叉樹適合用數(shù)組來存儲？
①鏈?zhǔn)酱鎯?②順序存儲 完全二叉樹
2.給定一組數(shù)據(jù)，比如1，3，5，6，9，10.你來算算，可以構(gòu)建出多少種不同的二叉樹？
n！
3.我們講了三種二叉樹的遍歷方式，前、中、后序。實際上，還有另一種遍歷方式，也就是按層遍歷，你知道如何實現(xiàn)嗎？

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) return new ArrayList<>(0);List<List<Integer>> result = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);Queue<TreeNode> curLevelNodes = new LinkedList<TreeNode>();while (!queue.isEmpty()) {TreeNode node = queue.poll();curLevelNodes.offer(node);if (queue.isEmpty()) {List<Integer> list = new ArrayList<>(curLevelNodes.size());while (!curLevelNodes.isEmpty()) {TreeNode curNode = curLevelNodes.poll();list.add(curNode.val);if (curNode.left != null) {queue.offer(curNode.left);}if (curNode.right != null) {queue.offer(curNode.right);}}result.add(list);}}return result;}}

4.如何通過編程，求出一棵給定二叉樹的確切高度呢？

[Leetcode][第104題][JAVA][二叉樹的最大深度][遞歸][BFS]

筆記整理來源： 王爭 數(shù)據(jù)結(jié)構(gòu)與算法之美

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。