CoE KKU

เนื่องจากภายใน binary search tree มีสารสนเทศของลำดับการจัดเรียงค่าในโนดอยู่ในตัวมัน ดังนั้นการแสดงรายการที่เป็นการจัดเรียงลำดับจึงทำได้ง่าย ดังแสดงในรูปที่ 4.56 ซึ่งเป็น recursive procedure

routine นี้ใช้การท่องในทรีในแบบ inorder traversal (ในรูปแบบ recursive) วิธีการทั่วไปของการท่องไปในทรีในแบบ inorder traversal คือการประมวลผลตัวทรีย่อยซ้ายก่อน (left subtree) แล้วตามด้วยการประมวลผลตัวโนดนั้น ๆ และจึงตามด้วยการประมวลผลทรีย่อยขวา (ในแบบ recursive) สิ่งที่น่าสนใจในอัลกอริทึมนี้คือ นอกจากความง่ายของมันแล้ว มันยังมี running time เป็น $O(N)$ เนื่องจากมันใช้เวลาคงที่ในการทำงานกับโนดทุกโนดในทรี มีการเข้าถึงโนดแต่ละโนดเพียงครั้งเดียวและเป็นเพียงการทดสอบค่า null เท่านั้น

ในบางกรณีเราอาจจะจำเป็นต้องทำการประมวลผลตัวทรีย่อยทั้งสองด้านของโนดก่อนจะทำการประมวลผลตัวโนดนั้น ๆ เอง เช่นการคำนวณค่าความสูง (height) ของโนดใด ๆ เราจะต้องรู้ค่าความสูงของทรีย่อยทั้งสองด้านของโนดนั้น ๆ เสียก่อน ฟังก์ชันในรูปที่ 4.57 เป็นฟังก์ชันเพื่อการคำนวณดังที่กล่าวนี้ ฟังก์ชันประกาศให้ค่าความสูงของ leaf ของทรีมีค่าเป็นศูนย์ การท่องไปในทรีด้วยวิธีที่กล่าวนี้เรียกว่า postorder traversal และมี running time ของอัลกอริทึม คือ $O(N)$, เนื่องจากมีการทำงานที่ใช้เวลาคงที่สำหรับแต่ละโนด

public void printTree( )
 {
     if ( isEmpty( ) )
        System.out.println( "Empty tree" );
     else
         printTree( root );
  }
 private void printTree( BinaryNode t )
  {
     if ( t != null )
     {
         printTree( t.left );
         System.out.println( t.element );
         printTree( t.right );
      }
  }

รูปที่ 4.56 Routine เพื่อพิมพ์ค่าใน binary search tree เรียงตามลำดับค่า

      /** Compute height of a subtree 
      * t = the node that roots the tree */
        private int height( BinaryNode t )
        {
			if ( t == null)
				return –1;
			else
            	return 1 + max(height( t.left ), height( t.right ) );
        } 

รูปที่ 4.57 ฟังก์ชันเพื่อคำนวณค่าความสูง (height) ของทรีโดยการใช้ postorder traversal

การท่องไปในทรีแบบที่สามที่ใช้กันมากอีกแบบ คือการท่องไปในทรีที่เรียกว่า preorder traversal โดยวิธีนี้จะมีการประมวลผลโนดนั้น ๆ ก่อนการประมวลผลโนดลูกของมัน เช่นถ้าต้องการแสดงโนดและค่าความลึก (depth) ของมัน

การทำงานของอัลกอริทึมทั้งหมดที่กล่าวนี้มีสิ่งที่เหมือนกันอย่างหนึ่งคือจะจัดการกับกรณีที่ null ก่อนการทำงานอื่น ๆ ฟังก์ชันที่เขียนจะกำหนดให้ส่งผ่านพารามิเตอร์เป็น reference ที่อ้างถึงรากของทรีย่อยที่จะได้รับการประมวณผลเท่านั้น การท่องไปในทรีแบบที่สี่ซึ่งจะไม่ค่อยพบเห็นบ่อยนัก คือการท่องไปในทรีแบบ level-order traversal วิธีการท่องไปแบบนี้จะทำการประมวลโนดที่อยู่ในระดับความลึก d ก่อนให้ครบทุกโนดแล้วจึงจะไปประมวลผลโนดที่อยู่ในระดับความลึก d + 1 วิธีการท่องไปในทรีแบบ Level-order traversal แตกต่างจากการท่องไปแบบอื่น ๆ คือ มันไม่ได้เป็นแบบ recursive แต่จะต้องใช้โครงสร้าง queue ช่วย