ตัวอย่างการโพสต์แบบไม่ซ้ำซ้อนตัวอย่างปฏิทินตัวอย่าง

ในการเดินทางข้ามที่ไม่ซ้ำซ้อนของการเดินสาย Prelude, Medium และ Post -order, โพสต์ -ลำดับเป็นปัญหามากที่สุด ถูกเก็บไว้ในสแต็ก

มีวิธีการมากมาย

คัดลอกรหัสรหัสดังนี้:

typedef struct {node * p;

LastOrderTraverse (bitree bt) {

// ก่อนอื่นเริ่มจากโหนดรูทไปที่ด้านล่างซ้ายไปที่หัวและป้อนแต่ละโหนดบนเส้นทางเข้าสู่สแต็ก

p = bt;

ในขณะที่ (bt)

push (bt, 0);

bt = bt.lchild;

-

// จากนั้นเข้าสู่วงจรร่างกาย

ในขณะที่ (! stack.empty ()) {// ตราบเท่าที่สแต็กไม่ว่างเปล่า

sn = stack.gettop ();

// หมายเหตุโหนดใด ๆ n ตราบใดที่เขามีลูกซ้ายหลังจาก n ป้อนสแต็กลูกซ้ายของ n ต้องติดตามสแต็ก (สิ่งนี้สะท้อนในช่วงครึ่งหลังของอัลกอริทึม) ดังนั้นเมื่อเราได้รับ สแต็คเมื่อองค์ประกอบด้านบนคุณสามารถมั่นใจได้ว่าองค์ประกอบนี้ไม่มีลูกซ้ายหรือลูกซ้ายของเขาได้รับการเข้าถึงดังนั้นในเวลานี้เราไม่สนใจลูกซ้ายของเราเราสนใจเฉพาะเด็กที่ถูกต้อง

// หากมีการเข้าถึงเด็กที่เหมาะสมหรือองค์ประกอบไม่มีลูกที่ถูกต้องคำจำกัดความของโพสต์ -การเดินทางต่อไปสามารถเดินทางได้ในเวลานี้

if (! sn.p.rchild || sn.rvisited) {{

p = pop ();

เยี่ยมชม (P);

-

อื่น // ถ้าเด็กที่ถูกต้องมีอยู่และ rvisited คือ 0 นั่นหมายความว่าเด็กที่เหมาะสมที่ไม่ได้ย้ายไม่ได้ถูกย้ายมาก่อนดังนั้นเขาจะจัดการกับลูกที่เหมาะสมของเขา

-

// ในเวลานี้เราต้องไปที่ด้านล่างซ้ายจากโหนดของเด็กที่ถูกต้องจนจบและวางโหนดทั้งหมดบนเส้นทางนี้ลงในสแต็ก

// แน่นอนตั้งค่า rvisited ของโหนดเป็น 1 ก่อนที่จะเข้าสแต็กเพราะสแต็คของเด็กที่เหมาะสมหมายความว่าเด็กที่เหมาะสมจะได้รับการเข้าถึงก่อนที่มันจะเป็นที่เข้าใจกันดีเพราะเรามักจะติดตามจากการสังเกต องค์ประกอบของสแต็กสำหรับการเยี่ยมชม) จะเห็นได้ว่าเมื่อองค์ประกอบอยู่ด้านบนของสแต็กเด็กที่เหมาะสมจะต้องผ่านการเยี่ยมชมดังนั้นผู้ที่ได้รับการตั้งค่าไว้ที่ 1 ที่นี่

sn.rvisited = 1;

// ไปที่จุดสิ้นสุดไปด้านล่างซ้ายและวางองค์ประกอบทั้งหมดบนเส้นทางเข้าไปในสแต็ก

p = sn.p.rchild;

ในขณะที่ (p! = 0) {

กด (p, 0);

p = p.lchild;

-

} // รอบนี้สิ้นสุดลง

-

-