求解二叉树所有节点的深度

如何求解一个二叉树所有节点的深度？

常见的算法是采用递归求解二叉树的最大深度，算法如下：

int maxDepth(node *p)   
{  
    if (!p) 
        return 0;  
    int lh = maxDepth(p->left);  
    int rh = maxDepth(p->right);  
    return lh > rh ? lh + 1 : rh + 1;  
}

但是要求解所有节点的深度值呢？上面的算法就不再适用了。我们可以这样思考，采用递归遍历所有节点的时候， 递归函数的调用层数其实就是该节点的深度。

算法如下：

void print_depth(node *p)
{
    static int depth=0;
    depth++;
    if(!p){
        goto out;
    }else{
        printf("node %c: %dn",p->data,depth);
        print_depth(p->left);
        print_depth(p->right);
    }
out:
    depth--;
}

每当进入递归函数一次，depth就增加1，每退出函数一次，depth就减少1。由于递归函数中depth需要动态维护，因此这里使用了static关键字。如有不清楚static关键字的同鞋可以参考我之前的博文。
两种算法的不同之处在于，后者使用了一个变量记录递归函数的调用层数。如果层数越高，节点深度越深。因此后者可以将所有节点的深度值求出。进而有利于求解最大深度、指定深度节点路径等问题。因此我觉得相比单纯求解最大深度算法，后者的用途更多。

如计算下面的二叉树的所有节点深度：

完整程序：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
    char data;
    struct node *left;
    struct node *right;
    struct node *parent;
}node;

void create(node **p,node *parent)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='?')
        *p=NULL;
    else{
        *p=(node *)malloc(sizeof(node));
        if(!(*p)){
            perror("malloc error!n");
            exit(-1);
        }
        (*p)->data=ch;
        (*p)->parent=parent;
        create(&(*p)->left,*p);
        create(&(*p)->right,*p);
    }
}

void print_depth(node *p)
{
    static int depth=0;
    depth++;
    if(!p){
        goto out;
    }else{
        printf("node %c: %dn",p->data,depth);
        print_depth(p->left);
        print_depth(p->right);
    }
out:
    depth--;
}

int main(void)
{
    node *root,*p;
    /*
     *这里2.txt是先序建树的数据：abc??de?g??f???。？表示节点为空。
     * 二叉树建好后如上图所示。
     */
    freopen("2.txt","r",stdin);
    create(&root,NULL);
    print_depth(root);
    return 0;
}

输出为：

最后

以上就是大气猎豹为你收集整理的求解二叉树所有节点的深度的全部内容，希望文章能够帮你解决求解二叉树所有节点的深度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。