c – 计算树的高度

发布时间：2020-12-16 10:54:23 所属栏目：百科来源：网络整理

导读：我正在尝试计算一棵树的高度.我对下面的代码不感兴趣. #includeiostream.hstruct 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) {

我正在尝试计算一棵树的高度.我对下面的代码不感兴趣.

#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);*/

}

它给了我正确的结果.
但是在some posts(谷歌搜索页面)建议做一个后序遍历并使用这个高度方法来计算高度.任何具体原因？

解决方法

但是,不是后期遍历正是你在做什么？假设left和right都是非null,则首先执行高度(左),然后是高度(右),然后在当前节点中进行一些处理.根据我的说法,这是后序遍历.

但我会这样写：

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

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

编辑：根据您如何定义树高,基本情况(对于空树)应为0或-1.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!