在這里先說明一下，結點和節(jié)點其實一樣的，無須關注這個。
一、樹型結構
1. 概念：樹是一種非線性的數據結構，它是由n個有限節(jié)點組成一個具有層次關系的集合。
如上圖所示，把此種數據結構稱作樹是因為它看起來像一個倒掛的樹。
?2. 特點
- 有一個特殊的節(jié)點，稱為根節(jié)點，它是唯一沒有前驅節(jié)點的節(jié)點。
- 除根節(jié)點以外，其余節(jié)點被分為P個互不相交的集合；每一個集合又是一個與樹類似的子樹。每個子樹只有一個前驅，可以任意個后繼（有限個）?！?/li>
- 子樹之間是不能有交集的，否則就不是樹型結構。
- 樹是遞歸定義的。
3. 基本重要概念
- 節(jié)點的度：一個節(jié)點含有子樹的個數（其實就是一個節(jié)點下邊連線的條數）。
- 樹的度：一棵樹中，所有節(jié)點度的最大值。
- 葉子節(jié)點（終端節(jié)點）：度為0的節(jié)點（其實就是下邊沒連線的節(jié)點）。
- 雙親結點（父節(jié)點）：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為子節(jié)點的父節(jié)點（就是某個節(jié)點它上邊連線的節(jié)點）。
- 孩子節(jié)點（子節(jié)點）：一個節(jié)點含有的子樹的根節(jié)點就稱為該節(jié)點的子節(jié)點（也就是一個節(jié)點下邊連線的節(jié)點）。
- 根節(jié)點：一棵樹中，沒有雙親結點的節(jié)點（其實就是最上面的節(jié)點）。
- 節(jié)點的層次：從根開始定義，跟為第一層，根的子節(jié)點為第二層，以此類推。
- 樹的高度（樹的深度）：樹中節(jié)點的最大層次。
- 非終端節(jié)點（分支節(jié)點）：度不為0的節(jié)點（也就是下邊還有連線的節(jié)點）。
- 兄弟節(jié)點：具有相同父節(jié)點的節(jié)點（也就是某幾個節(jié)點上邊連線連到的是同一個節(jié)點，那么這幾個節(jié)點就是兄弟節(jié)點）。
- 堂兄弟節(jié)點：雙親在同一層的節(jié)點。
- 節(jié)點的祖先：從根到該結點所經分支上的所有結點。
- 子孫：以某節(jié)點為根的子樹中任一結點都稱為該節(jié)點的子孫。
- 森林：有m棵互不相交的樹組成的集合稱為森林<注意m是大于等于0的>
二、二叉樹
（1） 概念
一顆二叉樹是節(jié)點的一個有限集合：該集合可能為空；可能是由一個根節(jié)點加上兩棵分別稱為左子樹和右子樹的二叉樹組成
通過以上幾張圖片，可以看出二叉樹的一些特點。
樹的度不能超過2；樹是有左樹和右樹之分的。
（2） 特殊樹
1. 滿二叉樹：一棵樹中，每層次的結點都達到了最大值。
2. 完全二叉樹：一棵樹中，結點從最后一層最后一個開始依次減少就稱為完全二叉樹。
滿二叉樹是一種特殊的完全二叉樹。
?
（3）性質
1. 若規(guī)定根節(jié)點的層數是1，則一棵樹的結點總數是：（2的n次方）減1。
2. 若規(guī)定根節(jié)點的層數是1，則一棵樹某層的結點書是：2的（n-1）次方。
3. 對任意一棵二叉樹，如果其葉結點個數為n0，度為0的非葉節(jié)點個數為n2，則有n0 = n2 +1。
對上述結果進行推斷：如果有一個二叉樹，假設其結點的總數n，葉子節(jié)點的個數為n0，度為1的結點個數為n1，度為2的結點個數為n2，可得公式 n = n2 + n1 + n0
節(jié)點的總數為n，因此其邊的數量就是n-1，根據二叉樹的圖想象一下，其葉子節(jié)點下邊的連線數量是為0的，度為1的節(jié)點下邊的連線數量是為1的，度為2的節(jié)點其下邊的連線數量是為2的，因此可得公式 n - 1 = 2 * n2 + n1
根據上述公式就可得到結果。
4. 求對具有n個節(jié)點的完全二叉樹的層次：log下以2為底，以n+1為真數向上取整。
5. 對于具有n個節(jié)點的完全二叉樹，如果按照從上至下，從左至右的順序對所有節(jié)點從0開始編號，那么對于序號為 i 的節(jié)點有：
- 對于 i 節(jié)點的左孩子是：2 i + 1，如果（2i+1）< n，那么無左孩子。
- 對于 i 節(jié)點的右孩子是：2 i + 2，如果（2i+2）< n，那么無右孩子。
- 對于 i = 0，那么其是根節(jié)點。
- 對于 i 節(jié)點的雙親結點是：（i -?1）/ 2。
6. 對于完全二叉樹，如果其有奇數個節(jié)點：那么其度為1的節(jié)點不存在；如果其有偶數個節(jié)點，那么其度為1的節(jié)點有且只有一個。?
7. 對于二叉樹性質的一些題目：
- 某二叉樹中共有399個節(jié)點，其中有199個度為2的節(jié)點，則該二叉樹中的葉子節(jié)點數為（）? ? ?此題直接根據公式 n0 = n2 + 1 直接可得：n0 = 200。
- 在具有2n個節(jié)點的完全二叉樹中，葉子節(jié)點個數為（）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 此題也很簡單，直接根據性質6可得：其度為1的節(jié)點是1，然后根據?n0 = n2 + 1 得出結論，其結果是 n + 1。
- 一個具有767個節(jié)點的完全二叉樹，其葉子節(jié)點個數為（）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 根據題目得無度為1的節(jié)點，因此 n0 + n2 = n0 + n0 - 1 = 767，得結果是384。
- 一棵完全二叉樹的節(jié)點個數為531個，那么這棵樹的高度是（）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?直接根據公式就求出結論再向上取整可得：log 2 （531 + 1）= 10。
（4）二叉樹存儲
順序存儲和鏈表的鏈式存儲都是二叉樹的存儲結構；下邊的代碼都以孩子表示法來寫。
//孩子表示法中存儲的是數據域，左孩子與右孩子的結點。
public class TreeNode {
int val; //數據域
TreeNode left; //左孩子的引用
TreeNode right; //右孩子的引用
}
//孩子雙親表示法中存儲的是數據域，左孩子，右孩子與當前節(jié)點的根節(jié)點。
public class TreeNode {
int val; //數據域
TreeNode left; //左孩子的引用
TreeNode right; //右孩子的引用
TreeNode parent; //當前節(jié)點的根節(jié)點
}（5）二叉樹的遍歷
1. 前序遍歷：根、左子樹、右子樹
2. 中序遍歷：左子樹、根、右子樹
3. 后序遍歷：左子樹、右子樹、根
如圖所示，當遍歷完 1 ，也就是根之后；會向左子樹走，也就是遍歷 2 ，而 2 也是子樹的根；經過子樹的根之后，再往左子樹走，遍歷到 3 ，3 也是一棵子樹的根；再往 3 的左樹走，發(fā)現不存在；這時就會向右子樹走；發(fā)現右子樹不存在，就會返回到 3；而3相當于是 2 的左子樹，因此會向 2 的右子樹走，而右子樹也不存在；這時就會返回 1 ；再向 1 的右子樹走....
上述是前序遍歷，對于中序和后序遍歷就不過多贅述，接下來就是樹中的一些基本操作。文章來源：http://www.zghlxwxcb.cn/news/detail-466299.html
（6）二叉樹的基本操作
在這些基本操作之前，先構建一個節(jié)點以及一個模擬一棵樹來測試數據文章來源地址http://www.zghlxwxcb.cn/news/detail-466299.html
public class My_BinaryTree {
//構建一個節(jié)點
public static class TreeNode{
public int val;//數據域
public TreeNode left;//左孩子
public TreeNode right;//右孩子
public TreeNode(int val){
this.val = val;
}
}
//構建一棵樹
public TreeNode createTree() {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(3);
TreeNode d = new TreeNode(4);
TreeNode e = new TreeNode(5);
TreeNode f = new TreeNode(6);
TreeNode g = new TreeNode(7);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
return a;
}
}-
前序遍歷的遞歸操作和非遞歸操作
//遞歸的前序遍歷
public void preOrder(TreeNode root) {
if(root == null) {
return ;
}
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
//非遞歸的前序遍歷
public void preOrder(TreeNode root) {
if(root == null){
return ;
}
//非遞歸的前序遍歷利用棧來做，后進先出
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
System.out.print(cur.val + " ");
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
}-
中序遍歷的遞歸操作和非遞歸操作
//遞歸的中序遍歷
public void inorder(TreeNode root) {
if(root == null) {
return ;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
//非遞歸的中序遍歷
public void inorder(TreeNode root) {
if(root == null) {
return ;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
System.out.print(top.val + " ");
cur = top.right;
}
}-
后序遍歷的遞歸與非遞歸操作
//遞歸的后序遍歷
public void postOrder(TreeNode root) {
if(root == null) {
return ;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
//非遞歸的后序遍歷
public void postOrder(TreeNode root) {
if(root == null) {
return ;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur =cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || top.right == pre) {
System.out.print(top.val + " ");
stack.pop();
pre = top;
}else {
cur = top.right;
}
}
}-
層序遍歷
//層序遍歷
public void levelOrder(TreeNode root) {
Deque<TreeNode> queue = new LinkedList<>();
if(root == null) {
return ;
}
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val +" ");
if(cur.left != null) {
queue.offer(cur.left);
}
if(cur.right != null) {
queue.offer(cur.right);
}
}
}-
?獲取樹中結點的個數
//獲取樹中節(jié)點的個數
//第一種方法
public int size(TreeNode root) {
if(root == null) {
return 0;
}
int leftSize = size(root.left);
int rightSize = size(root.right);
return leftSize+rightSize+1;
}
//第二種方法
public int nodeSize = 0;
public void size(TreeNode root) {
if(root == null) {
return ;
}
nodeSize++;
size(root.left);
size(root.right);
}-
獲取樹中葉子節(jié)點的個數
// 獲取葉子節(jié)點的個數
//第一種方法
public int getLeafNodeCount(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
int leftLeaf = getLeafNodeCount(root.left);
int rightLeaf = getLeafNodeCount(root.right);
return leftLeaf + rightLeaf;
}
//第二種方法
private int leafNodeSize = 0;
public void getLeafNodeCount(TreeNode root) {
if(root == null) {
return ;
}
if(root.left == null || root.right == null) {
leafNodeSize++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
}-
獲取第k層結點的個數
// 獲取第K層節(jié)點的個數
public int getKLevelNodeCount(TreeNode root,int k) {
if(root == null) {
return 0;
}
if(k == 1) {
return 1;
}
int leftLeveNode = getKLevelNodeCount(root.left,k-1);
int rightLeveNode = getKLevelNodeCount(root.right,k-1);
return leftLeveNode + rightLeveNode;
}-
獲取二叉樹的高度
// 檢測值為value的元素是否存在
TreeNode find(TreeNode root, int val) {
if(root == null) {
return null;
}
if(root.val == val) {
return root;
}
TreeNode leftFind = find(root.left,val);
if(leftFind != null) {
return leftFind;
}
TreeNode rightFind = find(root.right,val);
if(rightFind != null) {
return rightFind;
}
return null;
}-
判斷一棵樹是不是完全二叉樹
// 判斷一棵樹是不是完全二叉樹
public boolean isCompleteTree(TreeNode root) {
if(root == null) {
return true;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while(!queue.isEmpty()) {
TreeNode cur = queue.poll();
if(cur != null) {
return false;
}
}
return true;
}三、oj題
1.?144. 二叉樹的前序遍歷 - 力扣（LeetCode）
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
//非遞歸的前序遍歷利用棧來做，后進先出
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
list.add(cur.val);
//System.out.print(cur.val + " ");
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
cur = top.right;
}
return list;
}2.?94. 二叉樹的中序遍歷 - 力扣（LeetCode）
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode top = stack.pop();
list.add(top.val);
//System.out.print(top.val + " ");
cur = top.right;
}
return list;
}3.?145. 二叉樹的后序遍歷 - 力扣（LeetCode）
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) {
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null || !stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur =cur.left;
}
TreeNode top = stack.peek();
if(top.right == null || top.right == pre) {
//System.out.print(top + " ");
list.add(top.val);
stack.pop();
pre = top;
}else {
cur = top.right;
}
}
return list;
}4.?102. 二叉樹的層序遍歷 - 力扣（LeetCode）
//層序遍歷（）
public List<List<Integer>> levelOrder(TreeNode root) {
//先把需要返回的定義好
List<List<Integer>> list = new ArrayList<>();
if(root == null) {
return list;
}
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
//返回大數組中的小數組
List<Integer> cur = new ArrayList<>();
while(size != 0) {
TreeNode top = queue.poll();
cur.add(top.val);
if(top.left != null) {
queue.offer(top.left);
}
if(top.right != null) {
queue.offer(top.right);
}
size--;
}
list.add(cur);
}
return list;
}5.?100. 相同的樹 - 力扣（LeetCode）
//判斷兩棵樹是否相同
//條件：不僅兩棵樹的結構相同，其值也得相同
public boolean isSameTree(TreeNode p, TreeNode q) {
//首先判斷是不是兩棵樹的結構是否不相同：不相同就返回false
if((p == null && q != null)||(p != null && q == null)) {
return false;
}
//結構相同，然后判斷是否為空，空也算值相同
if(p == null && q == null) {
return true;
}
//再判斷其值是否相同
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}?6.?572. 另一棵樹的子樹 - 力扣（LeetCode）
//判斷一棵樹是不是另一棵樹的子樹
public boolean isSameTree(TreeNode p, TreeNode q) {
//首先判斷是不是兩棵樹的結構是否不相同：不相同就返回false
if((p == null && q != null)||(p != null && q == null)) {
return false;
}
//結構相同，然后判斷是否為空，空也算值相同
if(p == null && q == null) {
return true;
}
//再判斷其值是否相同
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
//判斷q樹是不是p樹的子樹
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//利用了兩棵樹是不是相同來做
if(isSameTree(root,subRoot)) {
return true;
}
if(root == null) {
return false;
}
if(isSubtree(root.left,subRoot)) {
return true;
}
if(isSubtree(root.right,subRoot)) {
return true;
}
return false;
}?7.?226. 翻轉二叉樹 - 力扣（LeetCode）
//翻轉二叉樹
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode swap = root.left;
root.left = root.right;
root.right = swap;
invertTree(root.left);
invertTree(root.right);
return root;
}?8.?110. 平衡二叉樹 - 力扣（LeetCode）
// 獲取二叉樹的高度
public int getHeight(TreeNode root) {
if(root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
//求是不是平衡樹，運用了求二叉樹高度的方法
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
int size = getHeight(root.left) - getHeight(root.right);
if(size > 1 || size < -1) {
return false;
}
boolean leftBalance = isBalanced(root.left);
boolean rightBalance = isBalanced(root.right);
return leftBalance && rightBalance;
}?9.?101. 對稱二叉樹 - 力扣（LeetCode）
//對于對稱二叉樹的求解：其實歸根結底就是先將二叉樹的左右子樹翻轉
//判斷左右子樹是否相等即可
//不過需要使用到另外兩個方法，因此需要對代碼熟練掌握才可以將此題完整做出
//判斷兩棵樹是否相同
//條件：不僅兩棵樹的結構相同，其值也得相同
public boolean isSameTree(TreeNode p, TreeNode q) {
//首先判斷是不是兩棵樹的結構是否不相同：不相同就返回false
if((p == null && q != null)||(p != null && q == null)) {
return false;
}
//結構相同，然后判斷是否為空，空也算值相同
if(p == null && q == null) {
return true;
}
//再判斷其值是否相同
if(p.val != q.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
//翻轉二叉樹
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode swap = root.left;
root.left = root.right;
root.right = swap;
invertTree(root.left);
invertTree(root.right);
return root;
}
//對稱二叉樹
public boolean isSymmetric(TreeNode root) {
if(root == null || (root.left == null && root.right == null)) {
return true;
}
invertTree(root.right);
return isSameTree(root.left,root.right);
}10.??二叉樹遍歷_?？皖}霸_?？途W (nowcoder.com)
import java.util.Scanner;
// 注意類名必須為 Main, 不要有任何 package xxx 信息
//構建一棵樹
class TreeNode {
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val) {
this.val = val;
}
}
public class Main {
//主函數
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的區(qū)別
while (in.hasNextLine()) { // 注意 while 處理多個 case
String s = in.nextLine();
TreeNode root = createTree(s);
inorder(root);
}
}
public static int i = 0;
//根據前序遍歷創(chuàng)建一棵樹
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
i++;
}
return root;
}
//中序遍歷
public static void inorder(TreeNode root) {
if(root == null) {
return ;
}
inorder(root.left);
System.out.print(root.val + " ");
inorder(root.right);
}
}11.?236. 二叉樹的最近公共祖先 - 力扣（LeetCode）
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
if(root == p || root == q) {
return root;
}
TreeNode leftRet = lowestCommonAncestor(root.left,p,q);
TreeNode rightRet = lowestCommonAncestor(root.right,p,q);
if(leftRet != null && rightRet != null) {
return root;
}else if(leftRet != null) {
return leftRet;
}else if(rightRet != null) {
return rightRet;
}
return null;
}
12. 105. 從前序與中序遍歷序列構造二叉樹 - 力扣（LeetCode）
13. 106. 從中序與后序遍歷序列構造二叉樹 - 力扣（LeetCode）
14. 606. 根據二叉樹創(chuàng)建字符串 - 力扣（LeetCode）
還有剩余的三道題，各位可以去試一下！
到了這里，關于數據結構之二叉樹（Java）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
