二元樹前序遍歷

2019-10-16 22:02:41

二元樹前序遍歷的步驟如下:

  1. 存取根節點
  2. 以前序遍歷左子樹
  3. 以前序遍歷右子樹

演算法

第1步:重複第2步到第4步,同時TREE!= NULL
第2步:寫入 TREE -> DATA
第3步:PREORDER(TREE -> LEFT)
第4步:PREORDER(TREE -> RIGHT)
      [迴圈結束]
第5步:結束

C語言實現的函式

void pre_order(struct treenode *tree)  
{
    if(tree != NULL)  
    {  
        printf("%d",tree→ root);  
        pre-order(tree→ left);  
        pre-order(tree→ right);  
    }  
}

範例
使用先序遍歷方式遍歷以下二元樹 -

  • 使用的遍歷方案是前序遍歷,因此,要列印的第一個元素是18
  • 遞回遍歷左子樹。 左子樹的根節點是211,列印它並向左移動。
  • 左邊是空的,因此列印右側子項並移動到根的右側子樹。
  • 因此,20是根的右子樹,列印它並向左移動。 由於左子樹是空的,因此向右移動並列印那裡存在的唯一元素,即190
  • 最後,列印順序為:18,211,90,20,190