因为树是递归定义的,所以用递归算法很方便。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
using namespace std;
struct Node {
char data;
Node *lchild;
Node *rchild;
};
void High(Node *T, int &h)
{
if (T == NULL)
h = 0;
else {
int left_h;
High(T->lchild, left_h);
int right_h;
High(T->rchild, right_h);
h = 1 + max(left_h, right_h);
}
}
Node *CreateBiTree(Node *&T) { // 算法6.4
// 按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,
// 构造二叉链表表示的二叉树T。
char ch;
cin >> ch;
if (ch == '#')
T = NULL;
else {
if (!(T = (Node *)malloc(sizeof(Node))))
return 0;
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return T;
} // CreateBiTree
void Free(Node *&T)
{
if (T == NULL)
return;
Free(T->lchild);
// T->lchild = NULL;
Free(T->rchild);
// T->rchild = NULL;
free(T);
T = NULL;
}
int main(int argc, char **argv)
{
freopen("cin.txt", "r", stdin);
Node *T = NULL;
CreateBiTree(T);
int height;
High(T, height);
cout << height << endl;
Free(T);
return 0;
}
/* cin.txt:
A
B
C
#
#
D
E
#
G
#
#
F
#
#
#
*/
构造的树:
输出为5。
分享到:
相关推荐
以二叉链表作存储结构,设计求二叉树高度的算法。
求二叉树的高度。。。。。。。。。。。。。。。。。。。。。。。。。。。
数据结构中求二叉树的高度和宽度C++代码,比较适合初学者
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
二叉树的创建遍历以及求二叉树的高度程序源码 先序创建 前序遍历 树的层次
二叉树 最优二叉树 树 算法实现 源码 高度 结点 叶子 ...求二叉树高度算法的递归模型 求二叉树结点个数算法的递归模型 求二叉树叶子结点个数算法的递归模型 以括号表示法输出二叉树运算算法 以凹入法输出二叉树运算算法
根据给定的二叉树,求二叉树的高度;求给定结点的所有祖先。 要求:(1)根据性质5 建立二叉树的二叉链表; (2)遍历算法必须采用非递归算法。
实现了二叉树的基本操作(先序遍历、中序遍历、后续遍历,求二叉树高度、结点数、度为1的结点数和叶子结点数)。
2.掌握二叉树的先序、中序、后序遍历算法,将遍历方法熟练应用到建立二叉链表、统计叶子节点,统计节点个数,求二叉树高度和输出节点信息的算法中。 【实验类型】 验证型实验 【实验原理】 二叉树是n(n≥0)...
java二叉树实现 (简单实现,入门用) /**创建二叉树*/ ... /**求二叉树高度*/ public int treeDepth(BinaryTree tree); /**输出树(括号表示法)*/ public void disPlayTree(BinaryTree tree);
2) 实现二叉树的建立(利用扩展先序序列建立二叉链表存储的二叉树)、二叉树的遍历、统计二叉树结点数、求二叉树高度、打印二叉树等操作。 3) 编写一个测试主函数,建立如下二叉树,并测试所设计的算法。 (3)含...
cout* 8--求二叉树高度(深度) *"; cout* 9--求结点层次 *"; cout* 10-- 判定空树 *"; cout* 11--求双亲结点 *"; cout* 12--求孩子结点 *"; cout* 13--求兄弟结点 *"; cout* 14--查找结点 *"; cout* 15--求...
二叉链表的基本操作 (1)先序建立二叉树 (2)求二叉树的叶子节点的个数 (3)求二叉树的高度
求二叉树高度的函数BTNodedepth( ) 求二叉树中所有结点的函数Nodes( ) 求二叉树中所有叶子结点的函数 Leafnodes( ) 输出所创建的二叉树函数DispBTNode( ) 将二叉树左右孩子交换的函数Revolute
使用递归的算法求树的高度与最长路径(laihaitao
本资源是针对大学数据结构实验课而编写的,也是个人上机所交的校正版, 采用递归实现求二叉树的叶子数和结点数 简单 易懂,适合初学者。
实验五 求二叉树叶子,高度及哈夫曼树
java语言实现的二叉树的各种操作(包括递归与非递归遍历二叉树,求二叉树的高度,节点总数,叶子节点等)
(1)二叉树的建立 (2)求出二叉树的高度 (3)求出二叉树结点个数 (4)先序遍历递归实现 (5)先序遍历非递归实现 (6)求出二叉树叶子结点个数