شجرة مجردة نوع البيانات

Question

أنا أفعل وحدة تسمى هياكل البيانات والخوارزميات.لقد بدأت للتو و أستاذي فقط علمنا أساسيات ما جبري دلالات وما البديهيات.... الخحتى الآن, لقد تستخدم الأشجار في شكل مصفوفات.عدم استخدام التوقيع على أمر قبل شجرة مثل شجرة(القيمة, شجرة, شجرة) حيث القيمة هو قيمة في عقدة ترك العقدة هي أول شجرة الحق العقدة الثانية الشجرة.

أنا الآن تحديد شجرة بلدي إما شجرة(القيمة, شجرة, شجرة) أو النيل, أنا لا يمكن معرفة كيفية تحديد الجبر أدنودي(قيمة الشجرة).

فإنه يحصل فقط أكثر تعقيدا مع كل مستوى ، بالإضافة إلى أنني لا أستطيع التفكير في أي حال المسح الضوئي من خلال مستوى واحد مرة واحدة, كنت أحاول منذ ساعة من الآن.الجبر فقط الفروع إلى أكثر وأكثر إذا-السس ونحن نذهب إلى أسفل الشجرة.أفعل ذلك الحق ؟ هل لي نقطة في الاتجاه الصحيح ؟ أو الأشجار لا يمكن تنفيذ مثل شجرة(القيمة, شجرة, شجرة)?

انها جزء من البرنامج التعليمي(لا يستحق أي علامات في أسئلة إضافية), ولكن أنا لا أبحث عن لحظة الإجابة, أنا أحب هذا الموضوع و ترغب في معرفة المزيد.

تعديل 1:لقد تحققت من ويكيبيديا ، وأنا لا ترغب في استخدام الكتاب المدرسي على إجابة واضحة ، أنا فقط أبحث عن تلميح نحو الاتجاه الصحيح ، سواء توجهي هو صحيح أو إنه من المستحيل تماما أن تحدد شجرة مثل شجرة(القيمة, شجرة, شجرة).وأنا أعلم أنك يمكن أن تمثل شجرة ADT في شكل قائمة.ولكن أردت أن تعتقد حقا عن ذلك.نأمل أن يجعل الشعور.شكرا جزيلا يا رفاق!

تحرير 2:Uhmm, من الصعب شرح ذلك عبر الإنترنت.دعونا نقول أنا تحديد بنية بيانات جديدة تسمى "شجرة".لا يمكن تعريفه بأي طريقة تريد ، ويجب أن تتصرف مثل متوازنة شجرة ثنائية(على الرغم من قيم الآباء والأمهات والأطفال لا يهم) لذا تعرف على أنها شجرة :شجرة(القيمة, شجرة, شجرة) أو النيل هذا ليس كود البرمجة, انها فقط كيف يمكنني تحديد ذلك.الشجرة هي قيمة + 2 أشجار أخرى أو شجرة النيل.الآن أدنودي(قيمة الشجرة) يضيف عقدة إلى شجرة في حين لا يزال الحفاظ على هذا التوازن.هذا ليس كود البرمجة, انها مجرد جبري دلالات.أنا لا أعرف ما إذا كنت يمكن أن يفسر ذلك بشكل صحيح.لكن علي أن الحل الذي لا يمكن تحقيقه باستخدام قوائم الانتظار أو مداخن, ولكن هذا هو آخر ADT يجب أن تحدد ، وهي ليست صالحة.

تحرير 3:يبدو أنني قد تولى العديد من الأشياء التي جعلت المشكلة أكثر صعوبة مما هو عليه حقا كان من المفترض أن يكون.أولا وقبل كل شيء ، من القليل تفسير أعطى ، Gamecat الجواب كان مثاليا.ولكن أنا أتفق مع التعليقات, انها صحيحة تماما أن تشمل غيرها من ADTs.في الواقع ، عندما نبني أي شيء يستخدم الباحث ، باستخدام ADT لهذا الهيكل.اعتقد كل ADT أن تكون فريدة من نوعها.على أي حال, شكرا جزيلا يا شباب على إجاباتك!

Answer 1

إذا كنت ترغب في إضافة عقدة في شجرة ، يمكنك استخدام وظيفة العودية.

أفترض الشجرة هو أمر.لذلك يجب أن تحصل على شيء مثل هذا:

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

تأكد من تحديث الأشجار الفرعية إذا كان يتم تغييرها!

يمكنك تحويل هذا إلى عدم وظيفة متكررة من قبل:

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

إذا كانت الشجرة يجب أن تكون متوازنة.تحتاج إلى تخزين على توازن الوزن (التي يمكن أن تكون -1 ، 0 أو 1).إذا كنت بحاجة إلى إضافة عقدة على "الثقيلة" الموقع ، تحتاج إلى هذا التعديل.على سبيل المثال إذا كان الجانب الأيسر لديه عقدة واحدة أكثر من الجانب الأيمن و تحتاج إلى إضافة مزيد من عقدة إلى اليسار.كنت بحاجة للحصول على عقدة مع أعلى قيمة من اليسار الشجرة وتعزيز ذلك إلى أعلى الحالي.الأعلى السابق يضاف إلى الشجرة الصحيحة.تأكد للحفاظ على الأشجار الفرعية متوازنة جدا.

على سبيل المثال:إضافة العقد 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

هذا هو السؤال الصعب ، حيث انها غامضة جدا.أفترض أن لديك نص الكتاب أو شيئا مماثلة كجزء من المواد الدراسية.وحتى مع ذلك ، فإنه يشعر كما لو كان العديد من الأشياء التي كنت تواجه مشاكل مع شرحها من قبل الموارد الأساسية مثل ويكيبيديا على الأشجار الثنائية.

هذه الصفحة توضح كيفية القيام بمختلف شجرة traversals ، وكيف الأشجار يمكن أن تكون ممثلة.