遍歷二叉樹(數(shù)據(jù)結(jié)構(gòu))

數(shù)據(jù)結(jié)構(gòu)——遍歷二叉樹主講人：修小草點擊播放即將開始主要內(nèi)容：connectivism遍歷二叉樹問題遍歷二叉樹的方法復(fù)雜度分析習(xí)題與總結(jié)connectivism

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

遍歷對線性結(jié)構(gòu)很容易解決；

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

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

先序遍歷的操作定義為：

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

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

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

中序遍歷的操作定義為：若二叉樹為空，則空操作；否則1、中序遍歷左子樹；2、訪問根節(jié)點；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、訪問根節(jié)點。左、右、根遍歷二叉樹的方法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層序遍歷二叉樹層序遍歷的要求是：按二叉樹的層序次序（即從根結(jié)點層至葉結(jié)點層），同一層中按先左子樹再右子樹的次序遍歷二叉樹。層序遍歷的特點：在所有未被訪問結(jié)點的集合中，排列在已訪問結(jié)點集合中最前面結(jié)點的左子樹的根結(jié)點將最先被訪問，然后是該結(jié)點的右子樹的根結(jié)點。這樣，如果把已訪問的結(jié)點放在一個隊列中，那么，所有未被訪問結(jié)點的訪問次序就可以由存放在隊列中的已訪問結(jié)點的出隊列次序決定。因此可以借助隊列實現(xiàn)二叉樹的層序遍歷。遍歷二叉樹的方法connectivism時間復(fù)雜度

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

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