อธิบาย:
ความลึกของต้นไม้ไบนารี: เส้นทางไปยังต้นไม้จะเกิดขึ้นจากโหนดรูทไปยังโหนด (รวมถึงโหนดรูตและใบ) ที่ผ่านโหนดใบไม้ในทางกลับกัน ความยาวของเส้นทางที่ยาวที่สุดคือความลึกของต้นไม้
ความกว้างของต้นไม้ไบนารี: แต่ละชั้นของต้นไม้ไบนารีมีจำนวนโหนดจำนวนหนึ่ง จำนวนโหนดในชั้นที่มีจำนวนโหนดมากที่สุดเรียกว่าความกว้างของต้นไม้ไบนารี
แนวคิด: การใช้งานซ้ำ
1. แต่ละโหนดถือได้ว่าเป็นโหนดรูท
2. ความลึกของโหนดรูท (โหนดใด ๆ ) เท่ากับความลึกของทรีทรีซ้ายหรือขวาสูงสุด +1
3. เริ่มต้นข้ามจากโหนดรูท หากคุณข้ามไปยังโหนดใบไม้ความลึกคือ 0
// ความลึกของทรีไบนารีสาธารณะความลึกคงที่ int (รูทโหนด) {ถ้า (root == null) {return 0; } int dl = ความลึก (root.leftchild); int dr = ความลึก (root.rightchild); ส่งคืน dl> dr? DL+1: DR+1; -2. ความกว้างของต้นไม้ไบนารี
แนวคิด: เพิ่มตัวนับระหว่างการสำรวจลำดับเลเยอร์เพื่อบันทึกจำนวนโหนดในแต่ละเลเยอร์
1. เมื่อแต่ละเลเยอร์อยู่นอกคิวจำนวนโหนดในเลเยอร์ถัดไปคือขนาด () ของคิว
2. ในตอนท้ายของแต่ละเลเยอร์ผ่านการสำรวจเปรียบเทียบความกว้างสูงสุดกับจำนวนปัจจุบันของโหนดและบันทึกค่าสูงสุด
ความกว้าง int คงที่สาธารณะ (รูทโหนด) {ถ้า (root == null) return 0; queue <node> q = new linkedList <Node> (); q.add (root); int width = 1; // ความกว้างสูงสุด int len = 1; // จำนวนปัจจุบันของโหนด q.poll (); ถ้า (node.leftchild! = null) {q.add (node.leftchild);} ถ้า (node.rightchild! = null) {q.add (node.rightchild);}} len = q.size () ความกว้าง: q.size ();} ส่งคืนความกว้าง;}สรุป
ข้างต้นเป็นเรื่องเกี่ยวกับคำอธิบายภาษา Java ของความลึกและความกว้างของต้นไม้ไบนารี ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!