質問

うことにより計算の高さがありません。私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);*/

}

ちょっとcorretます。ですが 一部の投稿(読ページ）することが示唆されたい、ポストオーダ探索、この高さが算出されます。特定の理由がありますか？

役に立ちましたか？

解決

しかし、あなたがやっている正確に何を後順トラバーサルではないでしょうか？左と仮定すると右の両方が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はずです。

。

他のヒント

ノードの少なくとも一つが唯一の子を有する場合、コードは、木に失敗します。

// 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);
//...
ツリーは最初の条件を満たしていないだろう、ルート上のメソッドを呼び出す二つのノード（ルート、左または右の子のいずれか）を持っている場合は、

は、（サブツリーの少なくとも一方が非空である）、それは再帰的に呼び出します。両方の子供たち。そのうちの一つがヌルですが、まだそれはNULLポインタデリファレンスifを実行することになります。

正解はハンスがここにhref="https://stackoverflow.com/questions/2279147/calculate-height-of-a-tree/2279179#2279179">

あなたが外部コードがNULLポインタを渡さないことを保証することはできませんので、（この方法は、あなたのコードのように公開されている）すべてのエントリポイントを制御しない場合、最初のケースは安全です。第二の溶液（基準に署名を変更すること、及びそれtreeクラスのメンバメソッドする）すべてのエントリポイントを制御することができる場合クリーナ（またはしない）可能性があります。

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

定義から wikipedia.

予約(縦):

  1. 訪問タイムをお過ごし下さい。
  2. ト左のサブツリー.
  3. トラバース右側のサブツリー.

Inorder(対称):

  1. ト左のサブツリー.
  2. 訪問タイムをお過ごし下さい。
  3. トラバース右側のサブツリー.

Postorder:

  1. ト左のサブツリー.
  2. トラバース右側のサブツリー.
  3. 訪問タイムをお過ごし下さい。

"訪問"の定義と計算ノードの高さ".る場合はゼロの両方の左右がnullの場合は1+合わせの高さい。

に実装では、フォーカストラバーサル順序は関係ありませんではないでしょうか同じ。だんだものである、ということなくリンクソースに記載postorderができます。

ここで答えです。

int Help :: heightTree (node *nodeptr)
{
    if (!nodeptr)
        return 0;
    else
    {
        return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right));
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top