⼆叉树-递归计算⼆叉树的⾼度（C语⾔）
1.规定：只有⼀个根节点的⼆叉树⾼为1。
2.完整代码如下：
/* 递归函数 - 计算⼆叉树⾼度(只有⼀个根节点的⼆叉树⾼为1) */
#include <iostream>递归函数c语言规则
#include <malloc.h>
using namespace std;
//⼆叉树节点定义
typedef int ElementType;
typedef struct bitnode
{
ElementType data;                  //数据域
struct bitnode *left, *right;      //指针域
} bitnode, *bitree;                    //bitnode为结构体，bitree为指向结构体bitnode的指针
//先序创建⼀棵⼆叉树
bitree CreateTree()
{
bitree T;
ElementType item;
cin >> item;
if( item == 0 )                  //0为空树标记
{
T = NULL;                    //T为空树
}
else
{
T = (bitree)malloc(sizeof(bitnode));
T->data = item;
T->left = CreateTree();              //递归创建左⼦树
T->right = CreateTree();            //递归创建右⼦树
}
return T;                              //返回根节点
}
/
/先序周游⼀棵树
void PerOrder(bitree T)
{
if( T )                      //T != NULL
{
cout << T->data << " ";            //先访问根节点
PerOrder(T->left);                  //再访问其左⼦树
PerOrder(T->right);                //最后访问其右⼦树
}
}
//释放树的空间
bitree FreeTree(bitree T)
{
if( T )
{
FreeTree(T->left);                  //递归释放其左⼦树
FreeTree(T->right);                //递归释放其右⼦树
free(T);                            //释放掉根节点
T = NULL;                          //释放掉指向根节点的指针，避免野指针
}
return T;
}
/
/计算⼀棵树的⾼度
int TreeHeight(bitree T)
{
if( T == NULL )          //空树，返回0
return 0;
if( T->left == NULL && T->right == NULL )          //树根返回1
return 1;
return max(TreeHeight(T->left), TreeHeight(T->right)) + 1; //树的⾼度 = MAX(左⼦树的⾼度，右⼦树的⾼度) + 1; }
//main()函数中为测试代码，读者可⾃⾏设计
int main()
{
bitree root;
int height = 0;
cout << "先序创建⼀棵⼆叉树，⼀次性输⼊⼀组数据(以空格隔开):";
root = CreateTree();
cout << "先序周游:";
PerOrder(root);
cout << endl;
height = TreeHeight(root);
cout << "树的⾼度为:" << height << endl;
root = FreeTree(root);
if(root == NULL)
cout << "释放成功" << endl;
return 0;
}
3.运⾏结果：
4.要点：上述输⼊的数据所代表的的树形图为：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。