二叉樹

• 二叉樹（binary tree）是一棵樹，其中每個(gè)節(jié)點(diǎn)都不能有多于兩個(gè)的子節(jié)點(diǎn)
• 二叉樹的一個(gè)性質(zhì)是一顆平均二叉樹的深度要比節(jié)點(diǎn)個(gè)數(shù)N小得多（重點(diǎn)），對(duì)二叉樹的分析得出其平均深度為O($\sqrt{N}$)，而對(duì)于特殊類型的二叉樹，即二叉查找樹（binary search tree）其深度的平均值是O(logN)。不過極端情況如下案例，深度可以達(dá)到N-1；

實(shí)現(xiàn)

• 因?yàn)橐粋€(gè)二叉樹節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，所有可以保存直接連接到他們的鏈。樹節(jié)點(diǎn)的聲明在結(jié)構(gòu)上類似雙向鏈表，在聲明中，節(jié)點(diǎn)就是element的信息加上兩個(gè)其他節(jié)點(diǎn)的引用（left和right）組成的結(jié)構(gòu)。

/*** 二叉樹節(jié)點(diǎn)對(duì)象定義** @author liaojiamin* @Date:Created in 15:24 2020/12/11*/ public class BinaryNode {private Object element;private BinaryNode left;private BinaryNode right;public BinaryNode(Object element, BinaryNode left, BinaryNode right) {this.element = element;this.left = left;this.right = right;}public Object getElement() {return element;}public void setElement(Object element) {this.element = element;}public BinaryNode getLeft() {return left;}public void setLeft(BinaryNode left) {this.left = left;}public BinaryNode getRight() {return right;}public void setRight(BinaryNode right) {this.right = right;} }

• 我們習(xí)慣在畫鏈表的時(shí)候，使用矩形標(biāo)識(shí)，當(dāng)我們表達(dá)樹的時(shí)候用圓圈，并用直線連接，因?yàn)樗麑?shí)際上是圖（graph）。當(dāng)涉及樹的時(shí)候，我們也不明顯的畫出null節(jié)點(diǎn)，因?yàn)榫哂蠳個(gè)節(jié)點(diǎn)的每一個(gè)二叉樹都需要N+1個(gè)null節(jié)點(diǎn)。
• 二叉樹有許多與搜索無關(guān)的引用，主要的是編譯器的設(shè)計(jì)領(lǐng)域。

案例：表達(dá)式樹

• 圖中線上一個(gè)表達(dá)式樹（expression tree）的案例，表達(dá)式樹的葉子是操作數(shù)，如常數(shù)或者變量名，而其他的節(jié)點(diǎn)是操作符。由于所有操作符都是二元的（+，-，，/），因此這棵樹正好可以被二叉樹標(biāo)識(shí)，雖然這是最簡(jiǎn)單情況，當(dāng)還是可以有可能含有多于兩個(gè)的子節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)也有可能只有一個(gè)兒子，如具有一目減運(yùn)算符的情形。我們將通過遞歸計(jì)算左子樹和右子樹所得到的的值應(yīng)用在根處的運(yùn)算符而計(jì)算出表達(dá)式書T的值。在本案例中，左子樹的值是無需計(jì)算，只有一個(gè)節(jié)點(diǎn)1， 右子樹的值（23-4）+5，因此整個(gè)表達(dá)式是1+2*3-4+5
• 我們通過遞歸經(jīng)過左節(jié)點(diǎn)，中節(jié)點(diǎn)，右節(jié)點(diǎn)的順序打印表達(dá)式，這種遍歷方式叫中序遍歷
• 另外一種遍歷策略，遞歸打印左節(jié)點(diǎn)，右節(jié)點(diǎn)，中節(jié)點(diǎn)，輸出為：123*4-5++，這種輸出策略稱為后順遍歷
• 第三種遍歷策略是先打印運(yùn)算符**（中節(jié)點(diǎn)），然后遞歸打印左子樹右子樹**，得到的結(jié)果：+1±*2345 ，這種遍歷方式叫前序遍歷

構(gòu)造表達(dá)式樹

• 我們先給出一種算法將后綴表達(dá)式轉(zhuǎn)表達(dá)式樹。我們已經(jīng)有了將中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法（見上一篇），因此我們能夠從這兩常見類型的輸入生成表達(dá)式樹。這里所描述的方法和后綴求職算法相似（上一篇），流程如下：
  • 我們遍歷表達(dá)式，如果是符合操作數(shù)（數(shù)字），就建立一個(gè)單節(jié)點(diǎn)樹并推入棧
  • 如果沒有符合是操作符（運(yùn)算符），那么將棧中彈出兩個(gè)樹T1，T2，（T1先出棧）
  • 將運(yùn)算符，T1，T2 組成一個(gè)新的數(shù)，改樹根節(jié)點(diǎn)是操作符，右節(jié)點(diǎn)是T1， 左節(jié)點(diǎn)是T2,
  • 將新數(shù)重新壓入棧
• 還是按上面的案例（1 2 3 * 4 - 5 + +）
• 動(dòng)圖展示整個(gè)數(shù)構(gòu)造過程
  

代碼實(shí)現(xiàn)

/*** 后綴表達(dá)式 轉(zhuǎn)表達(dá)式樹** @author liaojiamin* @Date:Created in 15:25 2020/12/11*/ public class PostfixExTOTreeEx {public static BinaryNode toTreeEx(String postfixEx) {MyStack<Object> number = new MyStack<>();String[] chars = postfixEx.split(" ");for (String s : chars) {if (s.matches("([1-9]\\d*\\.?\\d*)|(0\\.\\d*[1-9])")) {//數(shù)字number.push(s);}else if (s.matches("(\\*)|(\\/)|(\\+)|(\\-)")) {if (number.size() < 2) {return null;}BinaryNode binaryRight = null;Object right = number.pop();if(right instanceof BinaryNode){binaryRight = (BinaryNode) right;}else {binaryRight = new BinaryNode(right, null, null);}BinaryNode binaryLeft = null;Object left = number.pop();if(left instanceof BinaryNode){binaryLeft = (BinaryNode) left;}else {binaryLeft = new BinaryNode(left, null, null);}number.push(new BinaryNode(s, binaryLeft, binaryRight));}}return (BinaryNode) number.pop();}/*** 中序遍歷* @author: liaojiamin* @date: 18:15 2020/12/11*/public static void printMiddleFirstTree(BinaryNode binaryNode){if(binaryNode == null || binaryNode.getElement() == null){return;}printMiddleFirstTree(binaryNode.getLeft());System.out.print(binaryNode.getElement());printMiddleFirstTree(binaryNode.getRight());}/*** 前序遍歷* @author: liaojiamin* @date: 18:15 2020/12/11*/public static void printLeftFirstTree(BinaryNode binaryNode){if(binaryNode == null || binaryNode.getElement() == null){return;}System.out.print(binaryNode.getElement());printLeftFirstTree(binaryNode.getLeft());printLeftFirstTree(binaryNode.getRight());}/*** 后序遍歷* @author: liaojiamin* @date: 18:15 2020/12/11*/public static void printRightFirstTree(BinaryNode binaryNode){if(binaryNode == null || binaryNode.getElement() == null){return;}printRightFirstTree(binaryNode.getLeft());printRightFirstTree(binaryNode.getRight());System.out.print(binaryNode.getElement());}public static void main(String[] args) {BinaryNode binaryNode = toTreeEx("1 2 3 * 4 - 5 + +");printMiddleFirstTree(binaryNode);System.out.println();printLeftFirstTree(binaryNode);System.out.println();printRightFirstTree(binaryNode);}}

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–鏈表實(shí)現(xiàn)以及應(yīng)用
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–重建二叉樹

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--二叉树实现原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。