ในบทความก่อนหน้านี้ฉันได้กล่าวว่าอัลกอริทึมปฏิทินการสำรวจซ้ำแบบเรียกซ้ำ (Binary Tree First Root (ลำดับแรก) Traversal)
สรุปอัลกอริทึมที่ไม่ซ้ำซ้อนของการเดินทางครั้งแรก
1) ป้อนสแต็กส่วนใหญ่เพื่อเข้าสู่สแต็กโหนดแรกจากนั้นไปที่โหนดนี้
2) ในขณะที่
3) ลูกที่ถูกต้องของโหนด IF เป็นจริงโอนไปยัง 1) ดำเนินการต่อไปเพื่อสำรวจต่อไปมิฉะนั้นโหนดปัจจุบันจะออกและถ่ายโอนไปยังโหนดพาเรนต์ที่ผ่านการสำรวจ 1))
ก่อนอื่นให้ดูอัลกอริทึมที่สอดคล้องกับแนวคิดนี้:
คัดลอกรหัสรหัสดังนี้:
int preordertraversenonrcursiveEx (const bitree & t, int (*visitnode) (ข้อมูล telemtype)))
-
ถ้า (t == null)
-
กลับ -1;
-
bitNode *pbinode = t;
Sqstack S;
initstack (& s);
push (& s, (selectype) t);
ในขณะที่ (! isstackedy (s))
-
ในขณะที่ (pbinode)
-
VisitNode (pbinode-> data);
ถ้า (pbinode! = t)
-
push (& s, (selectype) pbinode);
-
pbinode = pbinode-> lchild;
-
ถ้า (pbinode == null)
-
ป๊อป (& s, (selemtype*) & pbinode);
-
if (pbinode-> rchild == null)
-
ป๊อป (& s, (selemtype*) & pbinode);
-
pbinode = pbinode-> rchild;
-
กลับ 0;
-
หมายเหตุ: 1) มีการใช้โครงสร้างสแต็กที่นี่และคุณสามารถเห็นสแต็กที่เก็บไว้ในลำดับของโครงสร้างด้านบน
2) เมื่อบันทึกโหนดที่นี่สิ่งที่ฉันบันทึกคือที่อยู่ของตัวชี้นั่นคือที่อยู่ของโหนดเปลี่ยนเป็นที่เก็บข้อมูล int . ทำไมคุณถึงคิดเกี่ยวกับการใช้พอยน์เตอร์ด้วยตัวเอง?
อัลกอริทึมข้างต้นนั้นผิดจริง! ทำไม ที่นี่ฉันตรวจสอบเป็นเวลานาน เพราะถ้าสแต็กว่างเปล่าหลังจากป๊อป แต่ยังมีต้นไม้ที่ถูกต้องมันจะไม่ดำเนินการต่อไป เมื่อต้นไม้เด็กซ้ายว่างเปล่าดังนี้: ดังนี้:
คัดลอกรหัสรหัสดังนี้:
int preordertraversenonrcursive (const bitree & t, int (*visitnode) (ข้อมูล telemtype)))
-
ถ้า (t == null)
-
กลับ -1;
-
bitNode *pbinode = t;
Sqstack S;
initstack (& s);
push (& s, (selectype) t);
ในขณะที่ (! isstackedy (s))
-
getTop (s, (selectype*) & pbinode);
ในขณะที่ (pbinode)
-
VisitNode (pbinode-> data);
pbinode = pbinode-> lchild;
push (& s, (selectype) pbinode);
-
ถ้า (pbinode == null)
-
ป๊อป (& s, (selemtype*) & pbinode);
-
if (! isstackedy (s))
-
ป๊อป (& s, (selemtype*) & pbinode);
pbinode = pbinode-> rchild;
push (& s, (selectype) pbinode);
-
-
กลับ 0;
-
นี่เป็นกรณีแรก กดลงในโหนดเด็กที่ถูกต้องแล้วตรวจสอบว่าลูกซ้ายของต้นไม้ขวาว่างเปล่าและดำเนินการต่อรอบหรือไม่
มีของเสียสองอันที่นี่: หนึ่งคือการผลักเข้าไปในโหนดของเด็กว่าง
กลับมาที่นี่เพื่อดูอัลกอริทึมที่ออกแบบมาก่อนซึ่งโหนด NULL ไม่ได้ถูกกดลงในตัวชี้ว่างหรือเด็กที่ว่างเปล่า แต่มันไม่สามารถส่งออกได้อย่างสมบูรณ์ null เป็นโมฆะนั่นคือเพื่อว่าจะไม่มีความอับอายที่จะไม่แสดงโหนดของทรีย่อย -ทรีที่ถูกต้องดังนี้: ดังต่อไปนี้:
คัดลอกรหัสรหัสดังนี้:
// ไม่ผ่านต้นไม้ไบนารี
int preordertraversenonrcursiveex (Const Bitree & T,
int (*VisitNode) (ข้อมูล telemtype)))
-
ถ้า (t == null)
-
กลับ -1;
-
bitNode *pbinode = t;
Sqstack S;
initstack (& s);
push (& s, (selectype) t);
ในขณะที่ (! isstackedy (s) || pbinode) // การดัดแปลงหลักคือประโยคนี้
-
ในขณะที่ (pbinode)
-
VisitNode (pbinode-> data);
ถ้า (pbinode! = t)
-
push (& s, (selectype) pbinode);
-
pbinode = pbinode-> lchild;
-
ถ้า (pbinode == null)
-
ป๊อป (& s, (selemtype*) & pbinode);
-
if (pbinode-> rchild == null)
-
ป๊อป (& s, (selemtype*) & pbinode);
-
pbinode = pbinode-> rchild;
-
กลับ 0;
-
หลังจากนั้นมีการเพิ่มลูปมันก็เพียงพอแล้ว ดังนี้ทดสอบต้นไม้ไบนารีในส่วนก่อนหน้า:
ในเวลานี้ข้อมูลอินพุตยังคงอยู่ที่ 12 34 0 0 78 0 0. ผลการทดสอบมีดังนี้:
--- bitree ---
โปรดป้อนข้อมูลโหนด Bitree:
12
โปรดป้อนข้อมูลโหนด Bitree:
34
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
78
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
12 34 78
นี่ไม่เพียงพอที่จะทดสอบดูต้นไม้ไบนารีต่อไปนี้
ในเวลานี้ข้อมูลอินพุตควรเป็น: 12 34 24 0 0 0 0 0 0 78 37 0 0 0 0. ผลการทดสอบมีดังนี้:
--- bitree ---
โปรดป้อนข้อมูลโหนด Bitree:
12
โปรดป้อนข้อมูลโหนด Bitree:
34
โปรดป้อนข้อมูลโหนด Bitree:
ยี่สิบสี่
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
50
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
78
โปรดป้อนข้อมูลโหนด Bitree:
37
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
โปรดป้อนข้อมูลโหนด Bitree:
0
12 34 24 50 78 37
มันสามารถเห็นได้จากการสำรวจเบื้องต้นว่ามันถูกต้อง แล้วเพิ่มเข้าร่วม