文章目錄
1. 樹形結(jié)構(gòu)
1.1 概念
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)?掠河，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合曙博。把它叫做樹是因為它看起來像一棵倒掛的樹碍脏，也就是說它是根朝上仿野，而葉朝下的?塞栅。它具有以下的特點：
有一個特殊的節(jié)點，稱為根節(jié)點趁俊，根節(jié)點沒有前驅(qū)節(jié)點
除根節(jié)點外域仇，其余節(jié)點被分成M(M > 0)個互不相交的集合T1、T2寺擂、…Tm暇务，其中每一個集合 Ti (1 <= i<= m) 又是一棵與樹類似的子樹。每棵子樹的根節(jié)點有且只有一個前驅(qū)怔软，可以有0個或多個后繼
樹是遞歸定義的垦细。
節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度； 如上圖：A的為6
樹的度：一棵樹中挡逼，最大的節(jié)點的度稱為樹的度括改； 如上圖：樹的度為6
葉子節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點； 如上圖：B家坎、C嘱能、H吝梅、I…等節(jié)點為葉節(jié)點
雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點惹骂； 如上圖：A是B的父節(jié)點孩
子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點苏携； 如上圖：B是A的孩子節(jié)點
根結(jié)點：一棵樹中，沒有雙親結(jié)點的結(jié)點对粪；如上圖：A
節(jié)點的層次：從根開始定義起右冻，根為第1層，根的子節(jié)點為第2層著拭，以此類推纱扭；
樹的高度或深度：樹中節(jié)點的最大層次； 如上圖：樹的高度為4
非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點茫死； 如上圖：D跪但、E、F峦萎、G…等節(jié)點為分支節(jié)點
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點； 如上圖：B忆首、C是兄弟節(jié)點
堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟爱榔；如上圖：H、I互為兄弟節(jié)點
節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點糙及；如上圖：A是所有節(jié)點的祖先
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫详幽。如上圖：所有節(jié)點都是A的子孫
森林：由m（m>=0）棵互不相交的樹的集合稱為森林
1.2 樹的表示形式
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了浸锨，實際中樹有很多種表示方式唇聘，如：雙親表示法，孩子表示法柱搜、孩子兄弟表示法等等迟郎。我們這里就簡單的了解其中最常用的孩子兄弟表示法?。
classNode{
intvalue;// 樹中存儲的數(shù)據(jù)NodefirstChild;// 第一個孩子引用NodenextBrother;// 下一個兄弟引用}
1.3 樹的應(yīng)用
文件系統(tǒng)管理（目錄和文件）
2. 二叉樹
2.1 概念
一棵二叉樹是結(jié)點的一個有限集合聪蘸，該集合或者為空宪肖，或者是由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉
樹組成。
二叉樹的特點：
1. 每個結(jié)點最多有兩棵子樹健爬，即二叉樹不存在度大于 2 的結(jié)點控乾。
2. 二叉樹的子樹有左右之分，其子樹的次序不能顛倒娜遵，因此二叉樹是有序樹蜕衡。
2.2 二叉樹的基本形態(tài)
一般二叉樹都是由以下幾個基本形態(tài)結(jié)合而形成的。
2.3 兩種特殊的二叉樹
滿二叉樹?: 一個二叉樹设拟，如果每一個層的結(jié)點數(shù)都達(dá)到最大值慨仿，則這個二叉樹就是滿二叉樹鸽扁。也就是說，如果一個二叉樹的層數(shù)為K镶骗，且結(jié)點總數(shù)是 桶现，則它就是滿二叉樹。
完全二叉樹?: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)鼎姊，完全二叉樹是由滿二叉樹而引出來的骡和。對于深度為K的，有n個結(jié)點的二叉樹相寇，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹慰于。 要注意的是滿二叉樹是一種特殊的完全二叉樹。
2.4 二叉樹的性質(zhì)
若規(guī)定根節(jié)點的層數(shù)為1?唤衫，則一棵非空二叉樹的第i層上最多有 2i-1?(i>0)個結(jié)點
若規(guī)定只有根節(jié)點的二叉樹的深度為1?婆赠，則深度為K的二叉樹的最大結(jié)點數(shù)是 2k?-1(k>=0)
對任何一棵二叉樹, 如果其葉結(jié)點個數(shù)為 n0, 度為2的非葉結(jié)點個數(shù)為 n2,則有n0＝n2＋1
具有n個結(jié)點的完全二叉樹的深度k為 log2?(n+1) 上取整
對于具有n個結(jié)點的完全二叉樹?，如果按照從上至下從左至右的順序?qū)λ泄?jié)點從0開始編號?佳励，則對于序號為i的結(jié)點有?：
若i>0休里，雙親序號：(i-1)/2；i=0赃承，i為根節(jié)點編號妙黍，無雙親節(jié)點
若2i+1<n，左孩子序號：2i+1瞧剖，否則無左孩子
若2i+2<n拭嫁，右孩子序號：2i+2，否則無右孩子
比如：假設(shè)一棵完全二叉樹中總共有1000個?節(jié)點抓于，則該二叉樹中500個葉子節(jié)點做粤，500個非葉子節(jié)點，1個節(jié)點只有左孩子捉撮，0個只有右孩子怕品。
2.5 二叉樹的存儲
二叉樹的存儲結(jié)構(gòu)分為：順序存儲和類似于鏈表的鏈?zhǔn)酱鎯Α?/p>
順序存儲 存儲的是完全二叉樹
二叉樹的鏈?zhǔn)酱鎯κ峭ㄟ^一個一個的節(jié)點引用起來的，常見的表示方式有二叉和三叉表示方式呕缭，具體如下：
// 孩子表示法class Node {
intval;// 數(shù)據(jù)域Nodeleft;// 左孩子的引用堵泽，常常代表左孩子為根的整棵左子樹Noderight;// 右孩子的引用，常常代表右孩子為根的整棵右子樹}// 孩子雙親表示法class Node {
intval;// 數(shù)據(jù)域Nodeleft;// 左孩子的引用恢总，常常代表左孩子為根的整棵左子樹Noderight;// 右孩子的引用迎罗，常常代表右孩子為根的整棵右子樹Nodeparent;// 當(dāng)前節(jié)點的根節(jié)點}
2.6 二叉樹的遍歷
如果N代表根節(jié)點，L代表根節(jié)點的左子樹片仿，R代表根節(jié)點的右子樹纹安，則根據(jù)遍歷根節(jié)點的先后次序有以下遍歷方式：
NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點—>根的左子樹—>根的右子樹。
LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節(jié)點—>根的右子樹。
LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節(jié)點厢岂。?
2.7 二叉樹的基本操作
第一步: 首先這里我們用窮舉法先來創(chuàng)建一個二叉樹來測試這些操作.
packageBinaryTree;class TreeNode{
publiccharval;publicTreeNodeleft;publicTreeNoderight;public TreeNode(char val){
this.val=val;}}publicclass BinaryTree {
public TreeNode createTree() {
TreeNodeA=newTreeNode('A');TreeNodeB=newTreeNode('B');TreeNodeC=newTreeNode('C');TreeNodeD=newTreeNode('D');TreeNodeE=newTreeNode('E');TreeNodeF=newTreeNode('F');TreeNodeG=newTreeNode('G');TreeNodeH=newTreeNode('H');A.left=B;A.right=C;B.left=D;B.right=E;E.right=H;C.left=F;C.right=G;returnA;}}
此時的二叉樹圖形如圖:
第二步: 用代碼實現(xiàn)3種遍歷二叉樹的方法.
// 前序遍歷voidpreOrderTraversal(TreeNoderoot){
if(root==null){
return;}System.out.print(root.val+" ");preOrderTraversal(root.left);preOrderTraversal(root.right);}// 中序遍歷voidinOrderTraversal(TreeNoderoot){
if(root==null){
return;}inOrderTraversal(root.left);System.out.print(root.val+" ");inOrderTraversal(root.right);}// 后序遍歷voidpostOrderTraversal(TreeNoderoot){
if(root==null){
return;}postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val+" ");}
第三步: 兩種方法求結(jié)點個數(shù)
// 遍歷思路-求結(jié)點個數(shù)staticintsize=0;void getSize1(TreeNode root){
if(root==null){
return;}size++;getSize1(root.left);getSize1(root.right);}// 子問題思路-求結(jié)點個數(shù)int getSize2(TreeNode root){
if(root==null){
return0;}returngetSize2(root.left)+getSize2(root.right)+1;}
第四步: 兩種方法求葉子結(jié)點的個數(shù)
// 遍歷思路-求葉子結(jié)點個數(shù)staticintleafSize=0;void getLeafSize1(TreeNode root){
if(root==null){
return;}if(root.left==null&&root.right==null){
leafSize++;}getLeafSize1(root.left);getLeafSize1(root.right);}// 子問題思路-求葉子結(jié)點個數(shù)int getLeafSize2(TreeNode root){
if(root==null){
return0;}if(root.left==null&&root.right==null){
return1;}returngetLeafSize2(root.left)+getLeafSize2(root.right);}
第五步: 求第 k 層結(jié)點個數(shù)
intgetKLevelSize(TreeNoderoot,intk){
if(root==null){
return0;}if(k==1){
return1;}returngetKLevelSize(root.left,k-1)+getKLevelSize(root.right,k-1);}
第六步: 查找val所在的位置
// 查找 val 所在結(jié)點光督，沒有找到返回 null// 按照 根 -> 左子樹 -> 右子樹的順序進(jìn)行查找// 一旦找到，立即返回塔粒，不需要繼續(xù)在其他位置查找TreeNodefind(TreeNoderoot,charval){
if(root==null){
returnnull;}if(root.val==val){
returnroot;}TreeNoderet=find(root.left,val);if(ret!=null){
returnret;}ret=find(root.right,val);if(ret!=null){
returnret;}returnnull;}
第七步: 獲取二叉樹的高度
// 獲取二叉樹的高度int getHeight(TreeNode root){
if(root==null){
return0;}intleftHeight=getHeight(root.left);intrightHeight=getHeight(root.right);returnleftHeight>rightHeight?leftHeight+1:rightHeight+1;}
第八步: 運行測試結(jié)果
publicstaticvoidmain(String[]args){
BinaryTreebinaryTree=newBinaryTree();TreeNoderoot=binaryTree.createTree();System.out.print("前序遍歷結(jié)果:? ");binaryTree.preOrderTraversal(root);System.out.println();System.out.print("中序遍歷結(jié)果:? ");binaryTree.inOrderTraversal(root);System.out.println();System.out.print("后序遍歷結(jié)果:? ");binaryTree.postOrderTraversal(root);System.out.println();binaryTree.getSize1(root);System.out.println("結(jié)點數(shù): "+BinaryTree.size);intret=binaryTree.getSize2(root);System.out.println("結(jié)點數(shù): "+ret);binaryTree.getLeafSize1(root);System.out.println("葉子節(jié)點數(shù): "+BinaryTree.leafSize);intret1=binaryTree.getLeafSize2(root);System.out.println("葉子節(jié)點數(shù): "+ret1);intret2=binaryTree.getKLevelSize(root,3);System.out.println("求k層節(jié)點數(shù): "+ret2);TreeNodeb=binaryTree.find(root,'H');System.out.println(b.val);System.out.println("求二叉樹的深度: "+binaryTree.getHeight(root));}
運行結(jié)果:
2.8 層序遍歷
設(shè)二叉樹的根節(jié)點所在層數(shù)為1结借，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點卒茬，然后從左到右訪問第2層上的節(jié)點船老，接著是第三層的節(jié)點，以此類推圃酵，自上而下柳畔，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷。
a) 層序遍歷代碼實現(xiàn):
// 層序遍歷void levelOrderTraversal(TreeNode root){
if(root==null)return;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){
TreeNodetop=queue.poll();System.out.print(top.val+" ");if(top.left!=null)queue.offer(top.left);if(top.right!=null)queue.offer(top.right);}System.out.println();}
b) 判斷一棵樹是不是完全二叉樹
方法一思路:
1. 將樹按照層序遍歷的方法,放入隊列中,不同的是將左右節(jié)點都放入隊列中,不論節(jié)點是否為空都放入
2. 循環(huán)取出隊首元素,如果隊首為null就結(jié)束循環(huán).
3. 如果此時隊列不為空.
①隊列還有節(jié)點,那么就不是完全二叉樹
②隊列全是null,那么就是完全二叉樹.
4. 循環(huán)結(jié)束那么就是true;
代碼實現(xiàn):
boolean isCompleteTree(TreeNode root) {
if(root==null)returntrue;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){
TreeNodetop=queue.poll();//左子樹 和 右子樹 都放入隊列(不論是不是null)if(top!=null){
queue.offer(top.left);queue.offer(top.right);}else{
//如果隊首為空就跳出循環(huán)break;}}//如果隊不為空,說明是因為break結(jié)束的循環(huán).那么就需要判斷隊里的元素while(!queue.isEmpty()){
TreeNodecur=queue.peek();//如果隊首為空,就出隊if(cur==null){
queue.poll();}else{
//遇到不為空的節(jié)點就表示不是完全二叉樹.returnfalse;}}//隊空既為true;returntrue;}
方法二思路:
1. 觀察完全二叉樹的圖形我們可以看出來,每個節(jié)點要么有2個子節(jié)點,要么沒有節(jié)點,要么就只有一個左節(jié)點沒有右節(jié)點.
2. 遍歷判斷
①如果左子樹和右子樹都不為空,就入隊.
②如果左子樹存在 右子樹不存在,那么進(jìn)行第二個判斷.
③如果左子樹不存在 右子樹存在,那么直接false
④如果左子樹右子樹都不存在,那么也進(jìn)入第二個判斷.
3. 第二個判斷,判斷是否接下來的左子樹和右子樹都為空,如果不為空,就是false;一直為空就是true;
代碼實現(xiàn):
boolean isCompleteTree1(TreeNode root) {
Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);booleanisComplete=true;while(!queue.isEmpty()){
TreeNodetop=queue.poll();if(isComplete){
//1.都不為空 入隊if(top.left!=null&&top.right!=null){
queue.offer(top.left);queue.offer(top.right);}elseif(top.left!=null&&top.right==null){
//2.左子樹不為空,右子樹為空,進(jìn)入第二個判斷isComplete=false;queue.offer(top.left);}elseif(top.left==null&&top.right!=null){
//3.左子樹為空,右子樹不為空,不符合完全二叉樹概念falsereturnfalse;}else{
//4.左右子樹都為空,進(jìn)入第二個判斷isComplete=false;}}else{
//第2判斷//如果后面的節(jié)點還有子樹,那就不符合完全二叉樹概念 falseif(top.left!=null||top.right!=null){
returnfalse;}}}//循環(huán)遍歷結(jié)束,那就是滿足條件,返回true;returntrue;}
2.9 前中后序的非遞歸實現(xiàn)
①前序遍歷 (非遞歸)
// 前序遍歷voidpreOrderTraversal(TreeNoderoot){
if(root==null)return;TreeNodecur=root;Stack<TreeNode>stack=newStack<>();while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);System.out.print(cur.val+" ");cur=cur.left;}TreeNodetop=stack.pop();cur=top.right;}}
②中序遍歷 (非遞歸)
// 中序遍歷voidinOrderTraversal(TreeNoderoot){
if(root==null)return;Stack<TreeNode>stack=newStack<>();TreeNodecur=root;while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);cur=cur.left;}TreeNodetop=stack.pop();System.out.print(top.val+" ");cur=top.right;}}
③后序遍歷 (非遞歸)
// 后序遍歷voidpostOrderTraversal(TreeNoderoot){
if(root==null)return;TreeNodecur=root;TreeNodepre=null;//用來指向上一個被打印的元素Stack<TreeNode>stack=newStack<>();while(cur!=null||!stack.empty()){
while(cur!=null){
stack.push(cur);cur=cur.left;}cur=stack.peek();if(cur.right==null||pre==cur.right){
stack.pop();System.out.print(cur.val+" ");pre=cur;cur=null;}else{
cur=cur.right;}}}
