樹和二叉樹
- 樹的基本概念
線性結構中的一個結點至多只有一個直接后繼，而樹形結構中一個結點可以有一個或多個直接后繼，因此，樹形結構可以表示更復雜的資料
(1) 樹的概念
- 1.1 樹的相關術語(重點)
(1) 結點的度：
樹上任一結點所擁有的子樹的數目稱為該結點的度
(2) 葉子:
(3) 樹的度:
一顆樹中所有結點的度的最大值稱為該樹的度
(4) 雙親結點:
父結點
(5) 結點的層次：
從根結點開始，根的層次為1，其余結點的層次為其雙親的層次加1
(6) 樹的高度：
一顆樹中所有結點層次數的最大值稱為該樹的高度(深度)
容易混淆的幾個概念：層次一般是指某個結點在當前數中的第xxx層；而高度是指樹的最大層次數，高度也稱為深度
- 二叉樹的基本概念
每個結點最多有2棵子樹(二叉樹的子樹有左子樹和右子樹之分)
(1) 二叉樹的5種基本形態(重點)
- 1.1 空樹，沒有任何結點
- 1.2 只有根
- 1.3 只有左子樹
- 1.4 只有右子樹
- 1.5 有左右子樹
(2) 二叉樹的基本運算
- 1.1 初始化：建立一顆空二叉樹
- 1.2 求雙親(父結點)
- 1.3 求左孩子和右孩子
- 1.4 建立一顆二叉樹
- 1.5 二叉樹的遍歷(先序、中序、后序、層次遍歷)(重點)
1.先序遍歷：中左右
2.中序遍歷：左中右
3.后序遍歷：左右中
(3) 二叉樹的性質(重點)
性質1： 二叉樹第i(i>=1)層上至多有2^(i-1)個結點
性質2： 深度為k(k>=1)的二叉樹至多有(2^k)-1個結點，注意是樹的總結點個數
深度計算示例：
深度為4的樹的最多有1 + 2 + 4 + 8個結點
性質3： 對任何一顆二叉樹，若度為0的結點(葉結點)個數為n0(0是下標),度數為2的結點個數為n2(2是下標)，則n0 = n2 + 1
- 滿二叉樹和完全二叉樹
-
1.1 滿二叉樹
深度為k(k >= 1)且有2^(k-1)個結點的二叉樹稱為滿二叉樹，滿二叉樹上的結點數已達到了二叉樹可以容納的最大值 -
1.2 完全二叉樹
完全二叉樹是在滿二叉樹上，從右到左，從下往上的去除結點，得到去除結點之后的樹(結點之間必須連續)，滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹 -
1.2.1 完全二叉樹的性質(其中[x]表示不大于x的最大整數)
性質1：含有n個結點的完全二叉樹的深度為[log? n] + 1
性質2：如果將一顆有n個結點的完全二叉樹按層編號(將二叉樹中的所有n個結點按第一層到最大層，每層從左到右的順序依次標記尾1，2，...n)，則對任一編號為i的結點A(1<=1<=n)有：
1. 若i = 1，則結點A是根：若i > 1，則A的雙親編號為[i / 2]
2. 若2*i>n，則結點A即無左孩子，也無右孩子；否則A的左孩子編號為2*i
3. 若2*i+1>n，則結點A無右孩子；否則，A的右孩子的編號為2*i+1
性質2表明完全二叉樹上的結點之間的父子關系可由它們編號之間的關系來表達，性質2是二叉樹順序存盤結構的基礎
-
紅黑樹(課外延伸,非考點)
3.1 概念
紅黑樹是一顆特征的二叉樹，具有平衡性質，查找的復雜度log(N)
3.2 性質
(1) 顏色由紅色和黑色組成
(2) 根結點都是黑色
(3) 兩個紅色的節點不相鄰
(4) 任一結點到葉子結點，有相同的高度
(5) 所有的葉子結點都是黑色的 -
B樹與B+樹(課外延伸，非考點)
-
二叉搜索樹(二叉查找樹)
搜索效率高，因為資料進行了排序,整個樹的父結點大于左子樹，小于又子樹 -
平衡二叉樹(課外延伸，非考點)
在二叉搜索樹的基礎上，具有自平衡功能，且左子樹與右子樹之間的高度差不超過1，它的左子樹和右子樹都是一顆平衡二叉樹
-
6.1 平衡二叉樹的不平衡的4種形態
(1) 全部往左偏
(2) 全部往又偏
(3) 往左偏 + 往又偏
(4) 往又偏 + 往左偏 -
6.2 平衡二叉樹的旋轉
旋轉時需要保證樹的順序,以某個結點為軸進行旋轉，旋轉到左邊或右邊
(1) 右旋
(2) 左旋
(3) 左右旋
先左旋，然后右旋
(4) 右左旋
先右旋,再左旋
注意：判斷是否是平衡二叉樹不能只判斷一部分是否平衡，而是要看整體的高度是否滿足要求
- 代碼實戰
package org.springcloud.order.test.arithmetic;
import lombok.Data;
/**
* 完全二叉樹的基本操作
*/
public class BinaryTree {
public static void main(String[] args) {
//陣列下標0不使用,目的是為了更好的利用公式
Integer [] arr = {null,20,18,30,0,19,29,31};
Node node = build(arr);
System.out.println(node);
middleTraversal(node);
}
/**
* 根據陣列構建完全二叉樹
* */
public static Node build(Integer [] arr){
validate(arr);
//遞回構建左右子樹
Node rootNode = new Node(arr[1]);
Node node = build(rootNode,arr,1);
return node;
}
public static Node build(Node node,Integer [] arr,int i){
if(2 * i <arr.length){
int leftIndex = 2 * i;
Node left = new Node(arr[leftIndex]);
node.setLeft(left);
build(left,arr,leftIndex);
int rightIndex = 2 * i + 1;
Node right = new Node(arr[rightIndex]);
node.setRight(right);
build(right,arr,rightIndex);
}
return node;
}
public static void validate(Integer [] arr){
Integer rootNode = arr[1];
if(rootNode == null){
throw new RuntimeException("沒有根結點");
}
if(rootNode <1){
throw new RuntimeException("結點值不能小于1");
}
}
/**
* 先序遍歷
*/
public static void prevTraversal(Node node){
if(node != null){
System.out.println(node.data);
prevTraversal(node.left);
prevTraversal(node.right);
}
}
/**
* 中序遍歷
* @param node
*/
public static void middleTraversal(Node node){
if(node != null){
middleTraversal(node.left);
System.out.println(node.data);
middleTraversal(node.right);
}
}
@Data
public static class Node{
public Node(Integer data){
this.data = https://www.cnblogs.com/xiaoquan66/p/data;
}
//資料域
private Integer data;
//雙親結點
private Node parent;
//左子樹
private Node left;
//右子樹
private Node right;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297024.html
標籤：其他