一. 二叉樹的遍歷
二叉樹的遍歷分為以下三種:?
前序遍歷: 訪問順序為? 根節(jié)點(diǎn)---->左子樹---->右子樹
中序遍歷: 訪問順序為? 左子樹---->根節(jié)點(diǎn)---->右子樹
后序遍歷:?訪問順序為? 左子樹---->右子樹---->根節(jié)點(diǎn)
接下來針對這3種遍歷方式進(jìn)行詳細(xì)介紹:
? ? ? ? (1) 前序遍歷
上圖前序遍歷順序為 1 2 3 4 5 6
? ? ? ? (2) 中序遍歷
上圖中序遍歷順序為3 2 1 5 4 6?
? ? ? ? (3) 后序遍歷
上圖后序遍歷順序為 3 2 5 6 4 1
? ? ? ? (4) 層序遍歷原理
? ? ? ? 除了前序遍歷,中序遍歷,后序遍歷外,還可以對二叉樹進(jìn)行層序遍歷. 設(shè)二叉樹的根節(jié)點(diǎn)所在層數(shù)為1, 層序遍歷就是從所在二叉樹的根節(jié)點(diǎn)出發(fā),首先訪問第一層的樹的根節(jié)點(diǎn),然后從左到右訪問第2層上的結(jié)點(diǎn),接著是第三層的結(jié)點(diǎn),以此類推,自上而下,自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷.?
上圖的層序遍歷為 1 2 4 3 5 6
?二. 二叉樹的基本操作
2.1 二叉樹的創(chuàng)建
二叉樹的存儲結(jié)構(gòu)分為: 順序存儲結(jié)構(gòu)和類似于鏈表的鏈?zhǔn)酱鎯?。二叉樹的鏈?zhǔn)酱鎯κ峭ㄟ^一個一個的結(jié)點(diǎn)引用起來的，常見的表示方式有二叉和三叉表示方式。在這里我們主要是使用二叉表示法來創(chuàng)建二叉樹。
static class TreeNode { //定義好三個屬性
public char val;
public TreeNode left; //左節(jié)點(diǎn)
public TreeNode right; //右節(jié)點(diǎn)
public TreeNode(char val) { //提供一個結(jié)點(diǎn)的構(gòu)造方法 new一個新結(jié)點(diǎn)的時候是不知道左右子樹的,所以不用構(gòu)造
this.val = val;
}
}2.2 二叉樹的創(chuàng)建代碼實現(xiàn)
以下圖二叉樹為例創(chuàng)建
//以窮舉的方式創(chuàng)建一棵二叉樹出來
public TreeNode creatTree() { //要返回樹的根節(jié)點(diǎn),所以返回類型是 TreeNode
TreeNode A = new TreeNode('A'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode B = new TreeNode('B'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode C = new TreeNode('C'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode D = new TreeNode('D'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode E = new TreeNode('E'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode F = new TreeNode('F'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode G = new TreeNode('G'); //創(chuàng)建一個結(jié)點(diǎn)賦值
TreeNode H = new TreeNode('H'); //創(chuàng)建一個結(jié)點(diǎn)賦值
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
E.right = H;
return A; //返回根節(jié)點(diǎn)
}2.3 二叉樹的基本操作（Java實現(xiàn)）
2.3.1 前序遍歷代碼實現(xiàn)（遞歸方式）
?由于二叉樹是遞歸定義的，所以二叉樹的遍歷一般也是采用遞歸的形式，當(dāng)然二叉樹也可以用非遞歸方式遍歷。這里文章用遞歸方式介紹。前序遍歷即采用先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹的順序。前序遍歷也是按照類似的方式遞歸遍歷，具體操作如下：
① 如果當(dāng)前節(jié)點(diǎn)值為空，返回；
②如果當(dāng)前節(jié)點(diǎn)值不為空，打印當(dāng)前節(jié)點(diǎn)值；遞歸遍歷左子樹；遞歸遍歷右子樹。
// 前序遍歷
void preOrder(TreeNode root) {
if (root == null) {
return; //空樹是不需要遍歷的
}
System.out.print(root.val + " ");
preOrder(root.left); //遞歸
preOrder(root.right);
}
?2.3.2 中序遍歷代碼實現(xiàn)
①如果當(dāng)前節(jié)點(diǎn)值為空，返回；
②遞歸遍歷左子樹；打印當(dāng)前節(jié)點(diǎn)的值；遞歸遍歷右子樹。
// 中序遍歷
void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}2.3.3 后序遍歷代碼實現(xiàn)
①如果當(dāng)前節(jié)點(diǎn)值為空，返回；
②遞歸遍歷左子樹；遞歸遍歷右子樹；打印當(dāng)前節(jié)點(diǎn)的值。
// 后序遍歷
void postOrder(TreeNode root) {
if (root == null) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}2.3.4 獲取樹中結(jié)點(diǎn)的個數(shù)
public static int nodeSize; //默認(rèn)為0
public int size(TreeNode root){
if(root == null){
return 0;
}
nodeSize++;
size(root.left); //遍歷左子樹
size(root.right); //遍歷右子樹
return nodeSize;
}子問題思路：?文章來源：http://www.zghlxwxcb.cn/news/detail-843325.html
public int size2(TreeNode root){
if(root == null){
return 0;
}
//左子樹的個數(shù)加上右子樹的結(jié)點(diǎn)個數(shù)加上根結(jié)點(diǎn)
int tmp = size2(root.left)+size2(root.right)+1;
return tmp;
}2.3.5 獲取葉子結(jié)點(diǎn)的個數(shù)
//獲取葉子結(jié)點(diǎn)個數(shù)
public static int leafSize;
public void getLeafNodeCount(TreeNode root){
if(root == null){
return;
}
if(root.left == null && root.right == null){
//如果沒有左右子樹就說明是葉子節(jié)點(diǎn)
leafSize++;
}
getLeafNodeCount(root.left); //遞歸遍歷左子樹
getLeafNodeCount(root.right); //遞歸遍歷右子樹
}?子問題思路：?root這棵樹有多少個葉子結(jié)點(diǎn) = 左子樹的葉子結(jié)點(diǎn) + 右子樹的葉子結(jié)點(diǎn)文章來源地址http://www.zghlxwxcb.cn/news/detail-843325.html
public int getLeafNodeCount2(TreeNode root){
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return 1;
}
return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
}2.3.6 獲取第K層結(jié)點(diǎn)的個數(shù)
public int getKLevelNodeCount(TreeNode root,int k){
if(root == null){
return 0;
}
if(k == 1){
return 1;
}else{
return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
}
}2.3.7 獲取樹的高度
//獲取樹的高度
//整棵樹的高度 = 左子樹的高度和右子樹的高度的最大值 + 1
public int getHeight(TreeNode root){
if(root == null){
return 0;
}
int hl = getHeight(root.left); //獲取左子樹的高度
int hr = getHeight(root.right); //獲取右子樹的高度
int max = hl>hr?hl:hr;
return max+1;
}2.3.8 檢測value的值是否存在
//尋找樹指定的元素
public TreeNode find(TreeNode root,int val){
if(root ==null){
return null;
}
if(root.val == val){ //先判斷根節(jié)點(diǎn)是不是我們要找的數(shù)據(jù)
return root;
}
TreeNode leftVal = find(root.left,val); //左子樹去找
if(leftVal != null){ //返回值不等于空說明找到了
return leftVal;
}
TreeNode rightVal = find(root.right,val); //右子樹去找
if(rightVal != null){ //返回值不等于空說明找到了
return rightVal;
}
//左右都走完沒找到返回空
return null;
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-樹的遍歷和基本操作(Java實現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
