حساب ارتفاع شجرة

Question

أحاول حساب ارتفاع الشجرة. أنا doint مع الكود المكتوب أدناه.

#include<iostream.h>

struct tree
{
    int data;
    struct tree * left;
    struct tree * right;
};

typedef struct tree tree;

class Tree
{
private:
    int n;
    int data;
    int l,r;
public:
    tree * Root;
    Tree(int x)
    {
        n=x;
        l=0;
        r=0;
        Root=NULL;
    }
    void create();
    int height(tree * Height);

};

void Tree::create()
{
    //Creting the tree structure
} 

int Tree::height(tree * Height)
{
    if(Height->left==NULL && Height->right==NULL)
    {return 0;
    }
    else
    {
        l=height(Height->left);
        r=height(Height->right);

        if (l>r)
        {l=l+1;
        return l;
        }
        else
        {
            r=r+1;
            return r;
        }
    }
}

int main()
{
    Tree A(10);//Initializing 10 node Tree object
    A.create();//Creating a 10 node tree

    cout<<"The height of tree"<<A.height(A.Root);*/

}

يعطيني نتيجة كوريت. ولكن في بعض الوظائف(googled page) اقترح القيام بعبارة ما بعد الحدود واستخدام طريقة الارتفاع هذه لحساب الارتفاع. أي سبب محدد؟

Answer 1

لكن أليس عبور ما بعد الحدود ما تفعله على وجه التحديد؟ على افتراض أن اليسار واليمين غير خريفين ، فأنت تفعل أولاً height(left), ، من ثم height(right), ، ثم بعض المعالجة في العقدة الحالية. هذا اجتياز ما بعد الحدود حسب لي.

لكني سأكتبها مثل هذا:

int Tree::height(tree *node) {
    if (!node) return -1;

    return 1 + max(height(node->left), height(node->right));
}

تحرير: اعتمادًا على كيفية تحديد ارتفاع الشجرة ، يجب أن تكون العلبة الأساسية (لشجرة فارغة) 0 أو -1.

Answer 2

سوف يفشل الرمز في الأشجار حيث يوجد واحد على الأقل من العقد طفل واحد فقط:

// code snippet (space condensed for brevity)
int Tree::height(tree * Height) {
    if(Height->left==NULL && Height->right==NULL) { return 0; }
    else {
        l=height(Height->left);
        r=height(Height->right);
//...

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

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

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

Answer 3

ارتفاع الشجرة لا يتغير مع اجتياز. لا يزال ثابتا. إنه تسلسل العقد الذي يتغير اعتمادًا على التجوّل.

Answer 4

تعريفات من ويكيبيديا.

preorder (العمق الأول):

1. قم بزيارة الجذر.
2. اجتياز الشجرة الفرعية اليسرى.
3. اجتياز الشجرة الفرعية اليمنى.

inorder (متماثل):

1. اجتياز الشجرة الفرعية اليسرى.
2. قم بزيارة الجذر.
3. اجتياز الشجرة الفرعية اليمنى.

Postorder:

1. اجتياز الشجرة الفرعية اليسرى.
2. اجتياز الشجرة الفرعية اليمنى.
3. قم بزيارة الجذر.

"زيارة" في التعريفات تعني "حساب ارتفاع العقدة". والتي في حالتك إما صفر (كل من اليسار واليمين فريدة) أو 1 + الارتفاع المشترك للأطفال.

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

Answer 5

هنا الجواب:

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}