二叉樹的遍歷

二叉樹的遍歷什么是樹是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合樹相關(guān)的概念空集合也是樹，稱為空樹?？諛渲袥]有結(jié)點。結(jié)點的度：一個結(jié)點含有的子結(jié)點的個數(shù)稱為該結(jié)點的度；葉結(jié)點或終端結(jié)點：度為0的結(jié)點稱為葉結(jié)點；非終端結(jié)點或分支結(jié)點：度不為0的結(jié)點；雙親結(jié)點或父結(jié)點：若一個結(jié)點含有子結(jié)點，則這個結(jié)點稱為其子結(jié)點的父結(jié)點；孩子結(jié)點或子結(jié)點：一個結(jié)點含有的子樹的根結(jié)點稱為該結(jié)點的子結(jié)點；兄弟結(jié)點：具有相同父結(jié)點的結(jié)點互稱為兄弟結(jié)點；樹的度：一棵樹中，最大的結(jié)點的度稱為樹的度；結(jié)點的層次：從根開始定義起，根為第1層，根的子結(jié)點為第2層，以此類推；樹的高度或深度：樹中結(jié)點的最大層次；堂兄弟結(jié)點：雙親在同一層的結(jié)點互為堂兄弟；結(jié)點的祖先：從根到該結(jié)點所經(jīng)分支上的所有結(jié)點；子孫：以某結(jié)點為根的子樹中任一結(jié)點都稱為該結(jié)點的子孫。二叉樹每個節(jié)點最多含有兩個子樹的樹稱為二叉樹

相關(guān)的“二叉樹”完全二叉樹滿二叉樹二叉樹的遍歷所謂遍歷是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。

訪問結(jié)點所做的操作依賴于具體的應用問題。通常二叉樹的遍歷根據(jù)根節(jié)點的遍歷次序分為：深度優(yōu)先遍歷先序（根）遍歷中序（根）遍歷后序（根）遍歷廣度優(yōu)先遍歷層次遍歷先序（根）遍歷

若二叉樹為空，則退出，否則進行下面操作訪問根節(jié)點遍歷左子樹遍歷右子樹口訣：根節(jié)點

左子樹

右子樹(根左右，NLR)

按照先序（根）遍歷地方式，遍歷二叉樹，則訪問順序為：

A、B、D、H、I、E、J、C、F、G中序（根）遍歷

若二叉樹為空，則退出，否則進行下面操作遍歷左子樹訪問根節(jié)點遍歷右子樹口訣：左子樹

根節(jié)點

右子樹（左根右，LNR）

按照中序（根）遍歷的方式，遍歷二叉樹，則訪問順序為：

H、D、I、B、J、E、A、F、C、G后序（根）遍歷

若二叉樹為空，則退出，否則進行下面操作遍歷左子樹遍歷右子樹訪問根節(jié)點口訣：左子樹

右子樹

根節(jié)點按照后序遍歷的方式，遍歷二叉樹，則訪問順序為：

H、I、D、J、E、B、F、G、C、A層次遍歷按照層次遍歷按照層次遍歷的方式，遍歷二叉樹，則訪問順序為：A、B、C、D、E、F、G、H、I、J代碼實現(xiàn)構(gòu)建樹：publicclassBinaryTreeNode{

privateStringdata;

privateBinaryTreeNodeleft;

privateBinaryTreeNoderight;

publicBinaryTreeNode(){}

publicBinaryTreeNode(Stringdata,BinaryTreeNodeleft,BinaryTreeNoderight){

super();

this.data=data;

this.left=left;

this.right