遍歷二叉樹(數據結構)

數據結構——遍歷二叉樹主講人：修小草點擊播放即將開始主要內容：connectivism遍歷二叉樹問題遍歷二叉樹的方法復雜度分析習題與總結connectivism

按照某條搜索路徑訪問樹中的每一個結點，使得每個結點均被訪問一次，且僅被訪問一次。遍歷二叉樹問題：

遍歷對線性結構很容易解決；

遍歷對二叉樹則略微復雜。遍歷二叉樹問題connectivism遍歷二叉樹問題connectivism二叉樹遍歷的基本方法：從二叉樹的定義知，一棵二叉樹由三部分組成：根結點、左子樹和右子樹。若規定D，L，R分別代表“訪問根結點”、“遍歷根結點的左子樹”和“遍歷根結點的右子樹”，根據遍歷算法對訪問根結點處理的位置，遍歷整個二叉樹就有6種方案：

DLR、LDR、LRDDRL、RDL、RLD遍歷二叉樹的方法connectivism后（根）序遍歷中（根）序遍歷先（根）序遍歷基本方法3遍歷二叉樹的方法connectivismFirst先序遍歷二叉樹

先序遍歷的操作定義為：

若二叉樹為空，則空操作；否則1、訪問根結點；2、先序遍歷左子樹；3、先序遍歷右子樹。根、左、右遍歷二叉樹的方法connectivismFirst先序遍歷二叉樹遍歷二叉樹的方法

voidPreOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*先序遍歷二叉樹t，訪問操作為Visit()函數*/

{if(t!=NULL){Visit(t->data); PreOrder(t->leftChild,Visit); PreOrder(t->rightChild,Visit);}}connectivismFirst先序遍歷二叉樹遍歷二叉樹的方法先序序列：-+a*b–cd/ef前綴表示（波蘭式）前綴表示（波蘭式）connectivismSecond中序遍歷二叉樹

中序遍歷的操作定義為：若二叉樹為空，則空操作；否則1、中序遍歷左子樹；2、訪問根節點；3、中序遍歷右子樹。左、根、右遍歷二叉樹的方法connectivism遍歷二叉樹的方法Second中序遍歷二叉樹voidInOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*中序遍歷二叉樹t*/{if(t!=NULL) {InOrder(t->leftChild,Visit); Visit(t->data); InOrder(t->rightChild,Visit); }}connectivism遍歷二叉樹的方法中序序列：a+b*c–d–e/f中綴表示Second中序遍歷二叉樹connectivismThird后序遍歷二叉樹

后序遍歷的操作定義為：若二叉樹為空，則空操作；否則1、后序遍歷左子樹；2、后序遍歷右子樹；3、訪問根節點。左、右、根遍歷二叉樹的方法connectivismThird后序遍歷二叉樹遍歷二叉樹的方法voidPostOrder(BiTreeNode*t,voidVisit(DataTypeitem))/*后序遍歷二叉樹t*/{if(t!=NULL) {PostOrder(t->leftChild,Visit); PostOrder(t->rightChild,Visit); Visit(t->data); }}connectivism遍歷二叉樹的方法后序序列：abcd–*

+ef/-后綴表示（逆波蘭式）Third后序遍歷二叉樹connectivismFour層序遍歷二叉樹層序遍歷的要求是：按二叉樹的層序次序（即從根結點層至葉結點層），同一層中按先左子樹再右子樹的次序遍歷二叉樹。層序遍歷的特點：在所有未被訪問結點的集合中，排列在已訪問結點集合中最前面結點的左子樹的根結點將最先被訪問，然后是該結點的右子樹的根結點。這樣，如果把已訪問的結點放在一個隊列中，那么，所有未被訪問結點的訪問次序就可以由存放在隊列中的已訪問結點的出隊列次序決定。因此可以借助隊列實現二叉樹的層序遍歷。遍歷二叉樹的方法connectivism時間復雜度

遍歷二叉樹算法的基本思想是訪問結點，無論是哪一種方法，對含有n個結點的二叉樹，其時間復雜度均為O(n)。空間復雜度

遍歷二叉樹算法所需要的輔助空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n，則空間復雜度也為O(n)。復雜度分析connectivism習題已知一棵二叉樹的先序遍歷序列為：abdgcefh，中序遍歷序列為：dgbaechf，畫出該二叉樹，并寫出其后序遍歷序列。后序序列：gdbehfcaconnectivism中序遍歷二叉樹后序遍歷