當前位置:趣味科普網>經驗>

後序遍歷二叉樹

經驗 閱讀(3.19W)

後序遍歷二叉樹

後序遍歷是二叉樹遍歷的一種,也叫做後根遍歷、後序周遊,可記做左右根。後序遍歷有遞迴演算法和非遞迴演算法兩種。在二叉樹中,先左後右再根。巧記:左右根。序遍歷的非遞迴演算法是三種順序中最複雜的,原因在於,後序遍歷是先訪問左、右子樹,再訪問根節點,而在非遞迴演算法中,利用棧回退到時,並不知道是從左子樹回退到根節點,還是從右子樹回退到根節點,如果從左子樹回退到根節點,此時就應該去訪問右子樹,而如果從右子樹回退到根節點,此時就應該訪問根節點。所以相比前序和後序,必須得在壓棧時新增資訊,以便在退棧時可以知道是從左子樹返