4

木の高さを計算しようとしています。私は以下に書かれたコードを使いこなしています。

#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ページ）では、ポストオーダートラバーサルを実行し、この高さメソッドを使用して高さを計算することが提案されました。特定の理由はありますか？

4

5 に答える 5

16

しかし、注文後のトラバーサルは正確にあなたがしていることではありませんか？左と右の両方がnull以外であると仮定すると、最初に、、height(left)次にheight(right)、を実行し、次に現在のノードでいくつかの処理を実行します。私によると、それは注文後のトラバーサルです。

しかし、私はそれを次のように書きます：

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

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

編集：ツリーの高さを定義する方法に応じて、基本ケース（空のツリーの場合）は0または-1にする必要があります。

于 2010-02-17T08:19:35.060 に答える
4

少なくとも1つのノードに子が1つしかないツリーでは、コードは失敗します。

// 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);
//...

ツリーに2つのノード（ルートと左または右の子のいずれか）がある場合、ルートでメソッドを呼び出すと、最初の条件が満たされず（サブツリーの少なくとも1つが空ではない）、両方の子で再帰的に呼び出されます。それらの1つはnullですが、それでもnullポインターを逆参照してを実行しifます。

正しい解決策は、ハンスがここに投稿したものです。いずれにせよ、メソッドの不変条件を選択する必要があります。引数がnullの場合の呼び出しを許可し、それを適切に処理するか、引数をnull以外にして、nullポインターを使用してメソッドを呼び出さないようにする必要があります。 。

最初のケースは、すべてのエントリポイントを制御しない場合（メソッドはコードのようにパブリックです）、外部コードがnullポインタを渡さないことを保証できないため安全です。2番目の解決策（署名を参照に変更し、それをtreeクラスのメンバーメソッドにする）は、すべてのエントリポイントを制御できる場合、よりクリーンになる（またはそうでない）可能性があります。

于 2010-02-17T08:40:34.210 に答える
2

木の高さは、トラバーサルによって変化しません。それは一定のままです。これは、トラバーサルに応じて変化するノードのシーケンスです。

于 2010-02-17T08:17:30.940 に答える
2

ウィキペディアからの定義。

事前注文（深さ優先）：

  1. ルートにアクセスします。
  2. 左側のサブツリーをトラバースします。
  3. 右側のサブツリーをトラバースします。

順序なし（対称）：

  1. 左側のサブツリーをトラバースします。
  2. ルートにアクセスします。
  3. 右側のサブツリーをトラバースします。

ポストオーダー：

  1. 左側のサブツリーをトラバースします。
  2. 右側のサブツリーをトラバースします。
  3. ルートにアクセスします。

定義の「訪問」は「ノードの高さを計算する」ことを意味します。あなたの場合、どちらがゼロ（左と右の両方がヌル）であるか、1+子供の身長の合計です。

実装では、トラバーサルの順序は重要ではなく、同じ結果が得られます。カントは、ポストオーダーが優先することを示すソースへのリンクなしで、それ以上のことを本当に教えてくれます。

于 2010-02-17T08:27:14.840 に答える
0

ここに答えがあります： 

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}
于 2015-02-18T20:02:08.293 に答える