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

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

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

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

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

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

先序遍歷的操作定義為：

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

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

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

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

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

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

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

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