首页 > 代码库 > 求二叉树的深度代码实现

求二叉树的深度代码实现

2024-08-13 21:46:05   220人阅读

用递归的方案实现：

 1 /* 求二叉树的深度 */ 2 int getDepthBiTree(BITREENODE* T) 3 { 4     int lDepth = 0, rDepth = 0; 5  6     if(T == NULL) 7     { 8         return 0; 9     }10     else11     {12         lDepth = getDepthBiTree(T->lchild);13         rDepth = getDepthBiTree(T->rchild);14     }15 16     return lDepth > rDepth ? lDepth+1 : rDepth+1;17 }

完整代码

技术分享
 1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5  6 using namespace std; 7  8 /* 二叉树存储结构定义*/ 9 typedef char TypeData;10 typedef struct BiTreeNode11 {12     TypeData data;13     struct BiTreeNode *lchild, *rchild;14 }BITREENODE;15 16 17 BITREENODE* createBiTree();          /* 创建二叉树 */18 void preOrderBiTree(BITREENODE* T);  /* 前序遍历该二叉树 */19 20 21 /* 创建二叉树 */22 BITREENODE* createBiTree()23 {24     TypeData ch = 0;25     BITREENODE* pNewNode = NULL;26 27     cin >> ch;28 29     if(ch == ‘#‘)30     {31         pNewNode = NULL;32     }33     else34     {35         /* 给节点分配内存 */36         pNewNode = (BITREENODE*)malloc(sizeof(BITREENODE));37         pNewNode->data =http://www.mamicode.com/ ch;38 39         /* 递归构建左右子树 */40         pNewNode->lchild = createBiTree();41         pNewNode->rchild = createBiTree();42     }43 44     return pNewNode;45 }46 47 /* 前序遍历该二叉树 */48 void preOrderBiTree(BITREENODE* T)49 {50     if(T)51     {52        cout << T->data << " ";53        preOrderBiTree(T->lchild);54        preOrderBiTree(T->rchild);55     }56 }57 58 /* 求二叉树的深度 */59 int getDepthBiTree(BITREENODE* T)60 {61     int lDepth = 0, rDepth = 0;62 63     if(T == NULL)64     {65         return 0;66     }67     else68     {69         lDepth = getDepthBiTree(T->lchild);70         rDepth = getDepthBiTree(T->rchild);71     }72 73     return lDepth > rDepth ? lDepth+1 : rDepth+1;74 }75 76 int main(void)77 {78     BITREENODE* pRoot = NULL;79     int depth = 0;80 81     /* 创建二叉树 */82     pRoot = createBiTree();83 84     /* 前序遍历该二叉树,这时候还没有线索化二叉树，可以这样进行前序遍历 */85     preOrderBiTree(pRoot);86     cout << endl;87 88     /* 求二叉树的深度*/89     depth = getDepthBiTree(pRoot);90     cout << depth << endl;91 92 93     return 0;94 }
View Code

 

求二叉树的深度代码实现


联系
我们