精华内容
下载资源
问答
  • 本题要求给定二叉树高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree ...

    本题要求给定二叉树的高度。

    函数接口定义:

    int GetHeight( BinTree BT );
    

    其中BinTree结构定义如下:

    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    

    要求函数返回给定二叉树BT的高度值。

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    int GetHeight( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("%d\n", GetHeight(BT));
        return 0;
    }
    /* 你的代码将被嵌在这里 */
    

    输出样例(对于图中给出的树):

    Alt

    4
    

    实例代码:

    int GetHeight( BinTree BT )
    {
    	int n;
    	if(BT == NULL){
    		return 0;
    	}
    	n = GetHeight(BT->Left) >  GetHeight(BT->Right) ? GetHeight(BT->Left)+1:GetHeight(BT->Right)+1;
    	return n;
    }
    
    展开全文
  • 本题要求给定二叉树高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree ...

    本题要求给定二叉树的高度。
    函数接口定义:

    int GetHeight( BinTree BT );

    其中BinTree结构定义如下:

    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };

    要求函数返回给定二叉树BT的高度值。
    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    int GetHeight( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("%d\n", GetHeight(BT));
        return 0;
    }
    /* 你的代码将被嵌在这里 */

    输出样例(对于图中给出的树):
    在这里插入图片描述

    4

    函数如下:

    int GetHeight(BinTree BT){
     int a,b;
     if(BT==NULL){
      return 0;
     }
     a=GetHeight(BT->Left)+1;
     b=GetHeight(BT->Right)+1;
     return a>b?a:b;//若a>b,返回a,否则返回b。
    }
    展开全文
  • 每从队列中出满一队节点,则高度+1。设置变量记录队列长度与新入队元素的数量,当队列长度与新入队元素数量相等时,表明队列中上一层节点已经全部出队,此时队列中的节点全部为同一层节点。 int findTreeHight...

    思路:非递归则需要利用层序遍历思想,记录层数。每从队列中出满一队节点,则高度+1。设置变量记录队列长度与新入队元素的数量,当队列长度与新入队元素数量相等时,表明队列中上一层节点已经全部出队,此时队列中的节点全部为同一层节点。

    int findTreeHight(BiTree T){
    	Queue que;	//创建队列 
    	que = InitQueue();
    	BiTree t;
    	t = T;
    	PushQueue(&que,t);
    	int h = 0;	//记录高度
    	int child = 0;
    	while(!IsEmptyQueue(que)){
    		if(t->LChild){
    			PushQueue(&que,t->LChild);
    			child++;
    		}
    		if(t->RChild){
    			PushQueue(&que,t->RChild);	//入队 
    			child++;
    		}		
    		PopQueue(&que,&t);	//对头出队 
    		if(child == que.len){	//len为队列中元素个数 
    			h++;
    			child = 0;
    		}
    	}
    	return h;
    }
    
    展开全文
  • c语言求二叉树高度The height of a Binary Tree is defined as the maximum depth of any leaf node from the root node. That is, it is the length of the longest path from the root node to any leaf node. ...

    c语言求二叉树高度

    The height of a Binary Tree is defined as the maximum depth of any leaf node from the root node. That is, it is the length of the longest path from the root node to any leaf node.

    二叉树的高度定义为任何叶节点距根节点的最大深度。 也就是说,它是从根节点到任何叶节点的最长路径的长度。

    Let us consider the below Binary Tree.

    让我们考虑下面的二叉树。

    Binary Tree Ht
    Binary Tree Ht
    二叉树Ht

    Since the leaf nodes corresponding to the maximum depth are 40 and 50, to find the height, we simply find the number of edges from the root node to either one of these two nodes, which is 3.

    由于对应于最大深度的叶节点是4050 ,为了找到高度,我们只需找到从根节点到这两个节点之一的边数,即3。

    Now that we know what the height of a Binary tree signifies, we shall now construct an algorithm to find the height of any Binary Tree.

    现在我们知道二叉树的高度表示什么,现在我们将构造一个算法来查找任何二叉树的高度。

    在C ++中查找二叉树的高度的逻辑 (Logic for finding the Height of Binary Tree in C++)

    Let us now decide the logic behind finding the height and write our pseudo code first.

    现在让我们决定寻找高度的背后逻辑,并首先编写伪代码。

    We shall use recursion on the tree, to find the height. (Refer to the Wikipedia article for the concepts)

    我们将在树上使用递归来找到高度。 (有关概念,请参阅Wikipedia文章

    Since the height of the tree is defined as the largest path from the root to a leaf, we can recursively compute the height of the left and right sub-trees.

    由于树的高度定义为从根到叶的最大路径,因此我们可以递归计算左和右子树的高度。

    We can apply the definition of the height on the sub-trees now.

    我们现在可以在子树上应用高度的定义。

    We observe that it is the maximum between the left and the right sub-trees and then add one.

    我们观察到它是左右子树之间的最大值,然后加一。

    Since the height of the tree is the maximum height of the sub-tree + 1, we keep doing this, until the sub-tree becomes NULL, and it’s height is 0.

    由于树的高度是子树的最大高度+ 1 ,因此我们一直这样做,直到子树变为NULL ,并且其高度为0。

    At this point, our function will finally terminate, and

    至此,我们的功能将最终终止,并且

    Let’s write the function tree_height() that computes the height.

    让我们写一个函数tree_height()来计算高度。

    
    // Find height of a tree, defined by the root node
    int tree_height(Node* root) {
        if (root == NULL) 
            return 0;
        else {
            // Find the height of left, right subtrees
            left_height = tree_height(root->left);
            right_height = tree_height(root->right);
             
            // Find max(subtree_height) + 1 to get the height of the tree
            return max(left_height, right_height) + 1;
    }
    

    Line #3 evaluates the terminating condition, when the sub-tree size is 0, or when the root node is NULL.

    第3行评估子树大小为0或根节点为NULL时的终止条件。

    Lines 7 and 8 recursively find the height of the left and right sub-trees.

    第7和8行递归地找到左和右子树的高度。

    And finally, Line 11 returns the maximum among the two, returning the height of the tree.

    最后,第11行返回两者中的最大值,并返回树的高度。

    用C / C ++实现 ( Implementation in C/C++)

    The below is a complete program showing how the Binary Tree is constructed, and then shows the logic for finding the height in tree_height().

    下面是一个完整的程序,显示了如何构造二叉树,然后显示了在tree_height()查找高度的逻辑。

    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Node Node;
    
    // Define the Tree Node here
    struct Node {
        int value;
        // Pointers to the left and right children
        Node* left, *right;
    };
    
    
    Node* init_tree(int data) {
        // Creates the tree and returns the
        // root node
        Node* root = (Node*) malloc (sizeof(Node));
        root->left = root->right = NULL;
        root->value = data;
        return root;
    }
    
    Node* create_node(int data) {
        // Creates a new node
        Node* node = (Node*) malloc (sizeof(Node));
        node->value = data;
        node->left = node->right = NULL;
        return node;
    }
    
    void free_tree(Node* root) {
        // Deallocates memory corresponding
        // to every node in the tree.
        Node* temp = root;
        if (!temp)
            return;
        free_tree(temp->left);
        free_tree(temp->right);
        if (!temp->left && !temp->right) {
            free(temp);
            return;
        }
    }
    
    int tree_height(Node* root) {
        // Get the height of the tree
        if (!root)
            return 0;
        else {
            // Find the height of both subtrees
            // and use the larger one
            int left_height = tree_height(root->left);
            int right_height = tree_height(root->right);
            if (left_height >= right_height)
                return left_height + 1;
            else
                return right_height + 1;
        }
    }
    
    int main() {
        // Program to demonstrate finding the height of a Binary Tree
    
        // Create the root node having a value of 10
        Node* root = init_tree(10);
        
        // Insert nodes onto the tree
        root->left = create_node(20);
        root->right = create_node(30);
        root->left->left = create_node(40);
        root->left->right = create_node(50);
    
        // Find the height of the tree
        int height = tree_height(root);
        printf("Height of the Binary Tree: %d\n", height);
    
        // Free the tree!
        free_tree(root);
        return 0;
    }
    


    翻译自: https://www.journaldev.com/34979/height-of-a-binary-tree-in-c-plus-plus

    c语言求二叉树高度

    展开全文
  • 二叉树递归特性可以计算出二叉树高度:不多逼逼,code:#includeusing namespace std;typedef struct BinaryTreeNode{char data; //数据struct BinaryTreeNode *left; //左孩子struct BinaryTreeNode *right; //右...
  • 求二叉树高度

    2017-12-14 14:53:26
    二叉树高度 二叉树高度 二叉树高度 二叉树高度 二叉树高度
  • 求二叉树高度 (20分) 1.非递归实现,利用层次遍历 int GetHeight( BinTree BT ){ int height=0,last=1; if(BT==NULL) return 0; BinTree queue[20]; int i=0; int front=0; queue[front]=BT; int rear=1; ...
  • 二叉树创建C语言实现

    2018-02-24 15:07:59
    通过链式存储结构实现二叉树的创建,包含如下操作: 1. 创建树; 2. 销毁树; 3. 清空树; 4. 插入结点; 5. 删除结点; 6. 获取结点; 7. 获取根结点;...9. 获取树的高度; 10. 获取树的度; 11. 显示二叉树
  • 二叉树C语言

    2019-08-29 19:20:18
    文章目录二叉树二叉树的定义二叉树的几个重要性质二叉树的抽象数据类型定义二叉树的存储结构二叉树的遍历遍历二叉树的应用 二叉树 二叉树的定义 二叉树TTT:一个有穷的结点的集合。 这个结合可以为空 如不为空,则...
  • 平衡二叉树(C语言简单实现) 本文参考自《大话数据结构》 平衡二叉树是一种二叉排序树,其中每一个结点的左子树和右子树的高度差至多等于1 。 将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF...
  • int Height(BTNode *T)//求二叉树高度 {  int L,R;  if(NULL == T)  return 0;  else  {  L=Height(T->lchild);  R=Height(T->rchild);  return L>R ? L+1 :R+1;  
  • 求二叉树高度,计数叶子节点数.计数度为1的节点数等基本操作. IDE:vs2013 具体实现代 ... C语言指针基本操作 C语言指针基本操作 指针 指针介绍 如果说C语言最有魅力的地方在哪,那么毋庸置疑,非指针莫属了. 众所周知,...
  • 平衡二叉树C语言) 数据结构-树:算法与数据结构参考 题目: 给定一个二叉树,判断它是否是高度平衡的二叉树1。例: 输入: [3,9,20,null,null,15,7] 输出:true 思路: 递归,分别判断左右子树是否为平衡二叉树 ...
  • 网上看了一些平衡二叉树的说明和实现,自己再实现一遍加深记忆 typedef struct TAG_AVL_T{ int data;... //二叉树高度 BT_NODE* left; //左 BT_NODE* right; }BT_NODE; #define LH ...
  • 二叉树C语言实现)

    2019-07-28 10:43:41
    以下为用C语言实现的二叉排序树,包含了树的创建,销毁,添加,删除,修改,前、中、后、层序遍历,深度,密度。 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define TYPE ...
  • 于是按查找最大值和最小值的方法计算二叉树的深度。结果发现这俩个根本不是一回事。即使你不断遍历左子树,找到了最小值,但是其最小值节点依然可能会有右子树,这样深度也就会不断增加。也就是说最大值对应的节点并...
  • 二叉树C语言实现

    2017-11-28 19:51:20
    //二叉树的二叉链表结点结构 typedef struct Node {  char data;  struct Node*LChild;  struct Node*RChild; }BiTNode,*BiTree; //扩展先序遍历序列创建二叉链表 void CreateBiTree(BiTree *
  • 二叉树基础 C语言一、基本概念二、树的表示1.表示方法的困难之处2. 改进的一种表示方式:child-sibling表示法三、二叉树基本理念1. 基本概念(1)与普通的度为2的树的区别:二叉树的左右分叉有区别(2) 特殊二叉树2...
  • 一些栈,队列和树的基本基本操作 BiTree.h #include<stdio.h> #include<...//平衡二叉树的平衡因子 struct BiNode *lchild,*rchild; } BiNode, *BiTree; typedef BiTree ElemType_Q; typedef .
  • C语言求二叉树高度

    千次阅读 2018-08-27 21:34:50
    利用后续遍历,递归实现 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree;... BinTree Le...
  • //设置队列Q,元素类型为二叉树结点指针 Q[++rear] = T; //根结点入队 BiTree p; while(front ){ //队不空则循环 p=Q[++front]; if(p->lchild){ Q[++rear] = p->lchild; } if(p->rchild){ Q[++rear] = p->rchild; }...
  • 还原二叉树C语言

    千次阅读 2018-11-16 17:38:54
    给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树高度。 输入描述 输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,350
精华内容 1,740
关键字:

求二叉树的高度c语言

c语言 订阅