求二叉树的深度代码实现

绝地灬酷狼 2022-08-09 15:53 130阅读 0赞

用递归的方案实现：

/* 求二叉树的深度 */
    int getDepthBiTree(BITREENODE* T)
    {
        int lDepth = 0, rDepth = 0;
    
        if(T == NULL)
        {
            return 0;
        }
        else
        {
            lDepth = getDepthBiTree(T->lchild);
            rDepth = getDepthBiTree(T->rchild);
        }
    
        return lDepth > rDepth ? lDepth+1 : rDepth+1;
    }

完整的代码：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    using namespace std;
    
    /* 二叉树存储结构定义*/
    typedef char TypeData;
    typedef struct BiTreeNode
    {
        TypeData data;
        struct BiTreeNode *lchild, *rchild;
    }BITREENODE;
    
    
    BITREENODE* createBiTree();          /* 创建二叉树 */
    void preOrderBiTree(BITREENODE* T);  /* 前序遍历该二叉树 */
    
    
    /* 创建二叉树 */
    BITREENODE* createBiTree()
    {
        TypeData ch = 0;
        BITREENODE* pNewNode = NULL;
    
        cin >> ch;
    
        if(ch == '#')
        {
            pNewNode = NULL;
        }
        else
        {
            /* 给节点分配内存 */
            pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));
            pNewNode->data = ch;
    
            /* 递归构建左右子树 */
            pNewNode->lchild = createBiTree();
            pNewNode->rchild = createBiTree();
        }
    
        return pNewNode;
    }
    
    /* 前序遍历该二叉树 */
    void preOrderBiTree(BITREENODE* T)
    {
        if(T)
        {
           cout << T->data << " ";
           preOrderBiTree(T->lchild);
           preOrderBiTree(T->rchild);
        }
    }
    
    /* 求二叉树的深度 */
    int getDepthBiTree(BITREENODE* T)
    {
        int lDepth = 0, rDepth = 0;
    
        if(T == NULL)
        {
            return 0;
        }
        else
        {
            lDepth = getDepthBiTree(T->lchild);
            rDepth = getDepthBiTree(T->rchild);
        }
    
        return lDepth > rDepth ? lDepth+1 : rDepth+1;
    }
    
    int main(void)
    {
        BITREENODE* pRoot = NULL;
        int depth = 0;
    
        /* 创建二叉树 */
        pRoot = createBiTree();
    
        /* 前序遍历该二叉树,这时候还没有线索化二叉树，可以这样进行前序遍历 */
        preOrderBiTree(pRoot);
        cout << endl;
    
        /* 求二叉树的深度*/
        depth = getDepthBiTree(pRoot);
        cout << depth << endl;
    
    
        return 0;
    }