二叉樹的種類：

滿二叉樹：樹的所有節(jié)點(diǎn)都是滿，即都有左右孩子。

這棵二叉樹為滿二叉樹，也可以說深度為k，有2^k-1個(gè)節(jié)點(diǎn)的二叉樹。

完全二叉樹：完全二叉樹的定義如下：在完全二叉樹中，除了最底層節(jié)點(diǎn)可能沒填滿外，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層，則該層包含 1~?2^(h-1) ?個(gè)節(jié)點(diǎn)。

?二叉搜索樹：二叉搜索樹是一顆排序樹。

• 若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
• 若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
• 它的左、右子樹也分別為二叉排序樹

?平衡二叉搜索樹：又被稱為AVL（Adelson-Velsky and?Landis）樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。

二叉樹的存儲(chǔ)方式：

二叉樹可以鏈?zhǔn)酱鎯?chǔ)，也可以順序存儲(chǔ)。

那么鏈?zhǔn)酱鎯?chǔ)方式就用指針， 順序存儲(chǔ)的方式就是用數(shù)組。

鏈?zhǔn)酱鎯?chǔ)：使用鏈表

?順序存儲(chǔ)：使用數(shù)組的方式

查找節(jié)點(diǎn)：如果父節(jié)點(diǎn)的數(shù)組下標(biāo)是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用鏈?zhǔn)奖硎镜亩鏄?#xff0c;更有利于我們理解，所以一般我們都是用鏈?zhǔn)酱鎯?chǔ)二叉樹。

二叉樹的遍歷方式：

二叉樹主要有兩種遍歷方式：

1. 深度優(yōu)先遍歷：先往深走，遇到葉子節(jié)點(diǎn)再往回走。
2. 廣度優(yōu)先遍歷：一層一層的去遍歷。

那么從深度優(yōu)先遍歷和廣度優(yōu)先遍歷進(jìn)一步拓展，才有如下遍歷方式：

• 深度優(yōu)先遍歷
  • 前序遍歷（遞歸法，迭代法）
  • 中序遍歷（遞歸法，迭代法）
  • 后序遍歷（遞歸法，迭代法）
• 廣度優(yōu)先遍歷
  • 層次遍歷（迭代法）

前中后遍歷其實(shí)就是看根節(jié)點(diǎn)的位置。在中間就是中序；在前面就前序；在后面就是后序遍歷。

• 前序遍歷：中左右
• 中序遍歷：左中右
• 后序遍歷：左右中

二叉樹的定義：

java的定義：

public class TreeNode {int value;TreeNode left;TreeNode right;//無參數(shù)構(gòu)造器：TreeNode(){}TreeNode(int value){this.value=value;}//有參數(shù)構(gòu)造器：public TreeNode(int value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}

python的定義：

class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None

C++的定義：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};