精华内容
下载资源
问答
  • 背景介绍:不要C语言很久了,现在单位有要求C,所以就只能从头开始...题目:如何测量一个树的高度 思路:利用相似三角形来处理,借助两个人(有明显的高度差)的高度做相似三角形的等比。 代码实现: #include

    背景介绍:不用C语言很久了,现在单位有要求C,所以就只能从头开始C语言了,买了本《C语言入门经典》,跟着书走,争取能把上面的每个程序都走一遍,有时候可能我写的代码和书上的不一样

    题目来源:C语言入门经典


    题目:如何测量一个树的高度



    思路:利用相似三角形来处理,借助两个人(有明显的高度差)的高度做相似三角形的等比。



    代码实现:

    #include <stdio.h>

    int main(void){

    float shorty=0.0F;
    float lofty=0.0F;
    float tree_height=0.0F;

    float shorty_to_lofty=0.0F;
    float lofty_to_tree=0.0F;

    printf("Please enter the height of the shortly(cm):");
    scanf("%f",&shorty);

    printf("\nPlease enter the height of the lofty(cm):");
    scanf("%f",&lofty);

    printf("\nPlease enter the distance between shorty and lofty(cm):");
    scanf("%f",&shorty_to_lofty);

    printf("\nPlease enter the distance between lofty and tree(cm):");
    scanf("%f",&lofty_to_tree);

    tree_height=shorty+(shorty_to_lofty+lofty_to_tree)*(lofty-shorty)/shorty_to_lofty;

    printf("\nThe tree height is %3.2f",tree_height);

    }

    展开全文
  • 设置level变量记录层数,last变量记录该层最右结点,在层次遍历出队时,让队列的front指针与last对比,相等证明该层遍历完了,last=rear,同时level+1,直至遍历完成,即队列为空,此时level即为二叉树的高度。...

        思路:设置level变量记录层数,last变量记录该层最右结点,在层次遍历出队时,让队列的front指针与last对比,相等证明该层遍历完了,last=rear,同时level+1,直至遍历完成,即队列为空,此时level即为二叉树的高度。完整代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MaxSize 100
    
    struct tree {
        int data;
        struct tree* left;
        struct tree* right;
    };
    
    typedef struct queue{
        struct tree* numQ[MaxSize];
        int front;
        int rear;
    }Queue;
    
    Queue Q;
    
    void initilize() { //初始化队列
        Q.front = -1;
        Q.rear = -1;
    }
    
    struct tree* creatTree (struct tree* root) {
        int value;
        scanf("%d", &value);
        if (value == -1)
            return NULL;
        root = (struct tree*)malloc(sizeof(struct tree));
        root->data = value;
        printf("请输入%d的左子树:", root->data);
        root->left = creatTree(root->left);
        printf("请输入%d的右子树:", root->data);
        root->right = creatTree(root->right);
        return root;
    }
    int main() {
        printf("请输入头节点:");
        struct tree* root = creatTree(root);
        initilize();  //初始化队列
        int level = 0,last = 0;
        Q.numQ[++Q.rear]=root;//根节点入队
        struct tree *p;
        while(Q.front<Q.rear){
               p=Q.numQ[++Q.front];//出队
               if(p->left)
                 Q.numQ[++Q.rear]=p->left;
               if(p->right)
                 Q.numQ[++Q.rear]=p->right;
               if(Q.front==last){//该层遍历完毕
                 level++;last = Q.rear;//层数+1
               }
        }
        printf("该树的高度为%d\n",level);
        return 0;
    }
    

     

    展开全文
  • 利用递归求下图的叶子结点数量以及树的深度 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> //二叉树结点 typedef struct BINARYNODE { char ch; struct BINARYNODE* ...

    利用递归求下图的叶子结点数量以及树的深度

    在这里插入图片描述

    #define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    
    
    //二叉树结点
    typedef struct BINARYNODE {
    	char ch;
    	struct BINARYNODE* lchild;
    	struct BINARYNODE* rchild;
    }BinaryNode;
    
    
    
    //递归求叶子数量
    void CalculateLeafNum(BinaryNode* root,int *LeafNum) {
    	if (root == NULL) {
    		return;
    	}
    	if (root->lchild == NULL && root->rchild == NULL) {
    		(*LeafNum)++;
    	}
    	//判断左子树
    	CalculateLeafNum(root->lchild,LeafNum);
    	//判断右子树
    	CalculateLeafNum(root->rchild,LeafNum);
    }
    
    
    //递归求树的高度
    int CalculateTreeDepth(BinaryNode* root) {
    	if (root == NULL) {
    		return 0;
    	}
    	//深度初始化为0
    	int depth = 0;
    	//分别求左右子树的深度
    	int LeftDepth = CalculateTreeDepth(root->lchild);
    	int RightDepth = CalculateTreeDepth(root->rchild);
    	//取二者中最大值,并加1(本层高度)
    	depth = LeftDepth > RightDepth ? LeftDepth + 1: RightDepth + 1;
    	return depth;
    }
    
    
    //创建二叉树
    void CreateBinaryTree() {
    	//创建结点
    	BinaryNode node1 = { 'A',NULL,NULL };
    	BinaryNode node2 = { 'B',NULL,NULL };
    	BinaryNode node3 = { 'C',NULL,NULL };
    	BinaryNode node4 = { 'D',NULL,NULL };
    	BinaryNode node5 = { 'E',NULL,NULL };
    	BinaryNode node6 = { 'F',NULL,NULL };
    	BinaryNode node7 = { 'G',NULL,NULL };
    	BinaryNode node8 = { 'H',NULL,NULL };
    	//建立结点关系
    	node1.lchild = &node2;
    	node1.rchild = &node6;
    	node2.rchild = &node3;
    	node3.lchild = &node4;
    	node3.rchild = &node5;
    	node6.rchild = &node7;
    	node7.lchild = &node8;
    	//叶子数目
    	int LeafNum = 0;
    	//调用函数求叶子结点数目
    	CalculateLeafNum(&node1,&LeafNum);
    	printf("LeafNum = %d\n", LeafNum);
    	//计算树的深度
    	int Depth = CalculateTreeDepth(&node1);
    	printf("TreeDepth = %d\n", Depth);
    }
    
    int main() {
    	CreateBinaryTree();
    	return 0;
    }
    

    运算结果

    LeafNum = 3
    TreeDepth = 4
    
    展开全文
  • 图因此可以成为,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样一个图,写出一个函数找到所有最小高度树并返回他们根节点。该图包含n个节点,标记为0到n-1。给定数字n和一个无向边edges...

    == 一、问题来源==

    对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。该图包含n个节点,标记为0到n-1。给定数字n和一个无向边edges列表(每一个边都是一对标签)你可以假设没有重复的边会出现在edges 中。由于所有的边都是无向边,[0,1] 和[1,0]是相同的,因此不会同时出现在edges 里。

    示例1:

    输入: n=4, edges =[[1, 0],[1, 2],[1, 3]]

    0

    |

    1

    / \

    2 3

    输出:【1】

    示例2:

    输入: n=6, edges = [[O, 3],[1, 3],[2, 3], [4,3],[5, 4]]

    0 1 2

    \ | /

    3

    |

    4

    |

    5

    输出: [3, 4]

    说明:
    根据[树的定义],树是一个无向图,其中任何两个顶点只通过一条路径连接。换句话说,一个任何没有简单环路的连通图都是一棵树。
    树的高度是指根节点和叶子节点之间最长向下路径.上边的数量。

    二、心路历程

    使用C语言来解决摘要中所述的在无向图中寻找最小高度树的问题,对于一个没有学过数据结构的小白来讲,为了弄明白解题的整个过程差点挠光了头发。起初在网络上寻找相关的解题方法,简单的一搜,哦豁,是一道经典的leedcode题目,可参考的博客多如牛毛。此时心里那是美滋滋的,又可以白嫖一下前辈们的智慧结晶啦。可是事情如果如此简单,就不会诞生今天这一篇分享啦。当我满怀期待的打开一篇篇博客的时候,看到C++/java实现,我那脆弱的小心脏就逐渐变得哇凉哇凉的。C++没学过啊,Java我也不会啊。那你还会啥?我就会个C,还是没啥编程经验的那种。这可咋办呀,看了他们的解题思路。嗯,无向图,广度优先搜索?拓扑结构?越看越懵,这时候心里慌的一批。既然看不懂,就不掩耳盗铃了。求人不如求己,自己先分析问题,恶补一下数据结构的知识,然后跟几位有经验的同事讨论了一下,整理出了自己的解题思路。

    三、解题思路

    建立无向图 -> 遍历无向图 -> 对称性 -> 依次去除叶节点

    无向图是由定点和边两部份组成。表示图的方法有很多种,经过对比,我选择了使用邻接矩阵来表示图。因为相比于链表更容易让人理解,且运用无向图在邻接矩阵中的对称特性,可以很直观的判定无向图中每一个顶点的度。

    邻接矩阵
    在这里插入图片描述
    如上图所示:图的邻接矩阵存储方式是用两个数组来表示图。一个意为数组存储图中的顶点信息,一个二维数组(称为邻接矩阵)存储图中边的信息。

    有了这个矩阵我们就可以直观的看出图中的信息:

    1、顶点之间有联系,将他们的所在边的度置为 1;

    2、某个顶点的度,其实就是这个定点v(i)在邻接矩阵中第i行的(或者第i列)的元素之和,例如v(1)的度就是1+0+1+0=2;

    3、顶点v(i)的所有邻接点就是矩阵中第i行arc(i)(j)为 1 的点;

    4、无向图中顶点指向是相互的,所以arc(i)(j)的值呈主对角线对称分布;

    每次遍历邻接矩阵,得出度为1的顶点,此顶点在树结构中一定是叶节点。根据无向图在邻接矩阵中的对称原理,将该点与临界点对应的连接边的度均置为0,即完成了剪树叶的操作。执行递归操作,直至剩余1~2个顶点,它们就是我们寻找的最小高度树的根节点。

    四、示例2测试

    在这里插入图片描述

    五、代码示例(完整)

    /*******************************************************************************
    * Filename:
    *	FMHT 
    *Description:
    *	Find the Minimum Height Tree
    *Author:
    	QH
    *Time:
    	2020.8.24 
    ********************************************************************************/
    
    #include <stdio.h>
    
    typedef int VertexType;
    typedef int EdgeType;
    #define MAXVEX 100
    #define ZERO 0
    
    
    typedef struct{
    	VertexType vexs[MAXVEX];
    	EdgeType arc[MAXVEX][MAXVEX];
    	int numVertexes, numEdges;
    } MGraph;
    
    void CreateMGraph(MGraph *G);
    void RemoveLeave(MGraph *G);
    
    int main(){
    	//Building undirected graph with adjacency matrix
    	MGraph G;
    	CreateMGraph(&G);
    	printf("Output the root node of the minimum height tree\n");
    	RemoveLeave(&G);
    	
    	return 0;
    }
    
    /*******************************************************************************
    *****************
    * FUNCTION
    *	CreateMGraph
    *DESCRIPTION
    *	Representstion of undirected graph by adjacency matrix.
    *PARAMETERS
    *	G		[MGraph *]		structure
    *RETURNS
    *	void
    *****************
    *******************************************************************************/
    
    void CreateMGraph(MGraph *G){
    	int i, j, k;
    	printf("Please enter the number of vertexes and edges:");
    	scanf("%d,%d", &G -> numVertexes, &G -> numEdges);
    	printf("Please enter vertex:\n");
    	for (i = 0; i < G -> numVertexes; i ++)
    		scanf("%d", &G -> vexs[i]);
    		
    	for (i = 0; i < G -> numVertexes; i ++)
    		for (j = 0; j < G -> numVertexes; j ++)
    			G -> arc[i][j] = ZERO;
    	for (k = 0; k < G -> numEdges; k ++){
    		printf("please enter (vi,vj):");
    		scanf("%d, %d", &i, &j);
    		G -> arc[i][j] = 1;
    		G -> arc[j][i] = G -> arc[i][j];
    	}
    	//Adjacency matrix of output undirected graph
    	printf("Adjacency matrix of output undirected graph:\n");
    	for (i = 0; i < G -> numVertexes; i ++){
    		for (j = 0; j < G -> numVertexes; j ++){
    				printf("%d\t", G -> arc[i][j]);
    			}
    		printf("\n");
    	}
    
    }
    
    /*******************************************************************************
    *****************
    * FUNCTION
    *	RemoveLeave
    *DESCRIPTION
    *	Use recursive loops to remove leaf nodes layer by layer.
    *PARAMETERS
    *	G		[MGraph *]		structure
    *RETURNS
    *	void
    *****************
    *******************************************************************************/
    
    void RemoveLeave(MGraph *G){
    	int i, j;	//for circulation
    	int sum;	//Sum of connected edges of each vertex
    	int n = 0;	//Number of remaining vertices
    	int m[G -> numVertexes];	//save 
    	//initialize m[]
    	for (i = 0; i < G -> numVertexes; i ++){
    		m[i] = ZERO;
    	}
    	//Determine whether the vertex is a leaf. yes set 1,not set 2	
    	for (i = 0; i < G -> numVertexes; i ++){
    		sum = 0;
    		for (j = 0; j < G -> numVertexes; j ++){
    				sum = sum + G -> arc[i][j];
    				if (sum > 1){
    					n = n + 1;
    					m[i] = 2;
    					break;
    				}
    				if (sum == 1){
    					m[i] = 1;	//leaf
    				}	
    			}
    	}
    	//remove leaf
    	for (i = 0; i < G -> numVertexes; i ++){
    		if (m[i] == 1){
    			for (j = 0; j < G -> numVertexes; j ++){
    				G -> arc[i][j] = 0;
    				G -> arc[j][i] = 0;
    			}
    		}
    		if (m[i] == 2){
    			if (n < 3){
    				//Output the root node of the minimum height tree 
    				printf("%d\t", G -> vexs[i]);
    			}
    		}		
    	}
    	//Recursion and termination condition judgment	
    	if (n < 3){
    			return ;
    		}
    	else{
    		RemoveLeave(G);
    	}
    }
    
    展开全文
  • 我自己编写的程序,又找不到错的地方,运行一下的时候就是只能输入n和h的值,然后程序就崩了,计算不出要计算的高度和节点的数目,错在哪里了啊。。。麻烦各位了,先谢过哈 #include <stdio.h> typedef...
  • Problem Description Long long ago, there was a gunner whose name is Jack. He likes to go hunting very much. One day he go to the grove. There are n birds and n trees. The i-th bird stands on the top ...
  • Problem Description An AVL tree is a kind of balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed....
  • #include "层次遍历Queue.h" #include "非递归算法堆栈.h" void Create(BinaryTree* bt) //构造一棵空二叉树 { bt->root = NULL; } BTNode* NewNode(ElemType x, BTNode* ln, BTNode* rn) //创造一个新...
  • AVL树的C语言实现

    2015-08-03 12:10:35
    AVL树是带有平衡条件的二叉查找树。之所以需要平衡是因为有的二叉查找树很糟糕,像这样 ...空树的高度定义为-1.因为添加了平衡条件,所以我们在编写AVL树的基本操作时需要加入是否平衡的判断,以及
  • 给定一个有序整数数组,元素各不相同且按升序排列,编写一个算法,创建一棵高度最小二叉搜索。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉...
  • 树的操作—c语言实现

    千次阅读 2018-01-17 19:48:49
    前言  本文包含二叉树、二叉查找树、Av树等的定义和相关操作,由于部分记录在印象笔记中,给出了文章链接。 一....  遍历树形目录,先序遍历和后序... AvTree是BST的一种,但是其每个节点的左子树和右子树的高度
  • C语言编写AVL

    2021-01-04 17:01:29
    高度为HAVL包含结点数量范围:1.5H - 2H-1 (low(H) = low(H-1) + low(H-2)+ 1 ≈ 1.5 类斐波那契数列) 综上:所以高和结点数量关系 h = logn 二、平衡调整策略 发生在回溯阶段,第一个失衡...
  • 艺术 高度基于自适应基数树的高压缩基数树() 特征 非常便携-干净的C89实施 设计为主索引数据结构-上面的论文描述了不完全拥有其键的二级索引 非递归更新算法
  • 前言 在进行学习的过程中查阅了很多资料,这些资料中...(2) 在用到节点时,调用函数计算树的高度。 相比于(1)的方法,(2)方法更加直观,容易理解。 AVL树的实现 树节点定义与获取 节点定义 typedef struct Node{
  • /*************************************************************************/ 构建AVL--高度平衡 通过旋转方法,构建AVL,InsertAVL()函数插入元素;当结点左边子树集高时调用LeftBalance()修复AVL
  • "树的高度为 %d\n" ,depth); } } return 0 ; } void CreateBiTree(BiTree **root) { char ch; scanf ( " %c" ,&ch); if (ch == '#' ) *root = NULL; else { *root = (BiTree*) malloc ( ...
  • AVL树C语言实现

    2021-03-17 19:41:05
    参考: https://www.cnblogs.com/skywang12345/p/3576969.html AVLTree.h #ifndef _AVL_TREE_H_ #define _AVL_TREE_H_ typedef int Type; struct AVLTreeNode { Type key; ...// 获取AVL树的高度
  • Tree min_avl_tree(const int height)...这个是答案中给的,感觉纯粹是根据AVL树的定义写出来的,理所当然地用到了递归.传递参数时传递了指向int类型的指针,这样就有了类似静态局部变量的效果.总而言之,这个代码我很喜欢.
  • AVL树的创建--C语言实现

    千次阅读 2018-03-08 11:52:04
    AVL树是一种自平衡(Self-balancing)二叉查找树(Binary Search Tree),要求任何一个节点的左子树和右子树的高度之差不能超过1。 AVL树的插入操作首先会按照普通二叉查找树的插入操作进行,不同的是在成功插入一个...
  • #include #include typedef struct node { int data;... printf("树的高度:%d\n\n\n",num); printf("输入头结点数据(输入0代表结束):"); p1=CreatTree(); TravelTree4(p1); return 0; }
  • 4.结点的层和树的高度:结点的层,从第一层开始,依次加1,就是层,高度就是有几层就是树的高度。 5.有序树和无序树:不考虑结点位置的前后关系的是无序树,反之,考虑结点位置前后关系的是有序树。 6.森林:由一个...
  • AVL树C语言代码

    2019-02-26 16:56:28
    AVL树(自平衡二叉查找树的诞生就是为了解决此类问题),和之前的BST树很类似,但是要添加上平衡因子,并在插入或删除某结点后进行平衡 #include&amp;lt;stdio.h&amp;gt; #include&amp;lt;stdlib.h&...
  • ***二叉搜索***结构,首先是一个二叉树,特点是小元素放在左边,大元素放在右边。代码如下 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; typedef struct node { struct node *left;...
  • 二叉搜索树是二叉树在查找中高度精炼的体现,也是AVL树实现的前提,大家紧扣二叉搜索树的定义进行题目解答,方才将知识有的放矢。

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 228
精华内容 91
关键字:

c语言树的高度

c语言 订阅