精华内容
下载资源
问答
  • 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语言求二叉树高度

    展开全文
  • 输入H:计算二叉树高度; 输入L:计算二叉树的叶子个数; 输入N:计算二叉树节点总个数; 输入1:先序遍历二叉树; 输入2:中序遍历二叉树; 输入3:后续遍历二叉树; 输入F:查找值=x的节点的个数; 输入P:以缩...
  • C语言 二叉树详解

    千次阅读 2020-02-07 00:53:19
    1.二叉树概念及结构 概念: 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 特点: 1.二叉树是一种非线性的数据结构,每棵子树的根结点有且只有一...

    1.二叉树概念及结构

    概念:
    一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
    特点:
    1.二叉树是一种非线性的数据结构,每棵子树的根结点有且只有一个前驱节点(父亲节点)
    2. 每个结点最多有两棵子树,即二叉树不存在度(度:一个节点含有的子树的个数称为该节点的度)大于2的结点。
    3. 二叉树的子树有左右之分,其子树的次序不能颠倒。
    4. 二叉树的这种结构是递归定义的。

    //左右孩子的二叉树链式结构定义
    //用链表来表示一棵二叉树,即用链来指示元素的逻辑关系,通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该点左孩子和右孩子所在的链结点的存储地址 。
    typedef int BTDataType;
    typedef struct BinaryTreeNode
    {
        BTDataType _data;   //数据域
      	struct BinaryTreeNode* left;//左孩子指针
    	struct BinaryTreeNode* right;//右孩子指针
    }BTNode;
    

    一般二叉树有这五种出现形式:
    (1)空树 (2) 单个节点 (3)只有一个左子树(4)只有一个右子树(5)左右子树都有

    在这里插入图片描述

    2.二叉树种类:

    (a)满二叉树:一个二叉树,如果每一个层的结点数都达到最大值(每个节点都有左右子节点),则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。一般用数组存储。
    (b)完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度(层数)为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。一般用数组存储。
    c)非完全(一般)二叉树:一个二叉树,不满足满二叉树和完全二叉树的条件的就是非完全二叉树,一般用二叉链存储。

    在这里插入图片描述

    3.二叉树的存储结构

    二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
    (1)顺序存储结构的适用情况:
    顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆又是一种特殊的二叉树结构,涉及很多,将会在后面专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
    在这里插入图片描述
    (2) 链式存储结构情况:
    二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该点左孩子和右孩子所在的链结点的存储地址 。
    在这里插入图片描述

    4.二叉树的性质

    1. 若规定根节点的层数为0,则一棵非空二叉树的第i层上最多有2^i 个结点.

    2. 若规定只有根节点的二叉树的深度为0,则深度为h的二叉树的最大结点数是2^(h+1) - 1.

    3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1

    4. 具有n个结点的完全二叉树的深度h=Log2(n+1). (Log2(n+1)是log以2为底,n+1为对数)

    5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

      若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
      若2i+1<n,左孩子序号:2i+1,2i+1>=n则无左孩子
      若2i+2<n,右孩子序号:2i+2,2i+2>=n则无右孩子
      此性质可适用于之后对这种完全二叉树的实现与理解

    5.二叉树的遍历

    二叉树的遍历是指按一定规律对二叉树中的每个节点进行访问且仅访问一次。其中的访问操作可指计算二叉树中节点的数据信息,打印该节点的信息,也包括对节点进行任何其他操作。
    遍历操作就是将二叉树中的节点按一定规律线性化的操作,目的在于将非线性结构变成线性化的访问序列。二叉树的遍历就是二叉树的最基本运算。
    三种遍历方法的递归定义:
    1.先序遍历操作过程:
    若二叉树为空,则为空操作,否则依次执行如下三个操作:
    (1)访问根节点;
    (2)按先序遍历左子树;
    (3)按先序遍历右子树;
    2.中序遍历操作过程:
    若二叉树为空,则为空操作,否则依次执行如下三个操作:
    (1按中序遍历左子树;
    (2)访问根节点
    (3)按中序遍历右子树;
    3.后序遍历操作过程:
    若二叉树为空,则为空操作,否则依次执行如下三个操作:
    (1)按后序遍历左子树;
    (2)按后序遍历右子树;
    (3)访问根节点;
    注意:先序,中序,后序遍历都是递归定义的,即在其子树上也按上述规则进行遍历操作

    二叉树遍历的算法应用:
    1.下面是三种遍历的打印结点信息操作

    void preorder(BTnode* root)//先序遍历打印
    {
    
    	if (root == NULL)
    		return;
    	printf("%c ", root->val);
    	preorder(root->left);
    	preorder(root->right);
    }
    void inorder(BTnode* root)//中序遍历
    {
    	if (root == NULL)
    		return;
    	inorder(root->left);
    	printf("%c ", root->val);
    	inorder(root->right);
    }
    void postorder(BTnode* root)//后序遍历
    {
    	if (root == NULL)
    		return;
    	postorder(root->left);
    	postorder(root->right);
    	printf("%c ", root->val);
    }
    
    

    2.输出二叉树的叶子节点
    满足叶子节点的条条件是:没有左右子树的节点。

    void preorder(BTnode* root)//使用先序遍历打印叶子节点
    {
    
    	if (root == NULL)
    		return;
    	if(root->left==NULL && root->right==NULLprintf("%c",root->val);//输出叶子节点
    	preorder(root->left);//遍历左子树
    	preorder(root->right);
    }
    

    3.统计叶子节点个数
    第一种方法:判断是否为叶子节点,计数器操作即可

    int  postorder(BTnode* root)//使用后序遍历找叶子节点
    {
    
    	if (root == NULL)
    		retusrn;
    	postorder(root->left);//遍历左子树
    	postorder(root->right);
    	if(root->left==NULL && root->right==NULL)
    		count++;//统计叶子节点个数count++
    	return count;
    }
    

    第二种方法:分治算法,若是空树,返回0;若只有一个节点,返回1;否则为左右子树的叶子节点之和。

    int postorder(BTnode* root)//使用后序遍历找叶子节点
    {
    	int count=0;
    	if (root == NULL)
    		count =0;
    	else if(root->left==NULL && root->right==NULL)
    		count=1;
    	else //叶子数为左右两个子树的叶子数之和
    		count=postorder(root->left)+postorder(root->right);
    	return count;
    }
    

    4.求二叉树的高度
    二叉树的高度为二叉树中节点层次的最大值,也可以视为其左右子树的高度的最大值加一。

    int postdepth(BTnode* root)
    {
    	int lh,rh,max;
    	if(root==NULL)//空树,返回 0
    	{
    		return 0;
    	} 
    	lh=postdepth(root->left);//求左子树深度
    	rh=postdepth(root->right);//求右子树深度
    	max=lh>rh? lh:rh;//求两者最大者
    	return max+1}
    

    6.二叉树链式结构的及常用功能的实现

    #include "binarytree.h"
    #include "Queue.h"
    
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    //算法思想:采用类似先序遍历的递归算法,从数组首位开始读入,如果是‘#’,则为空,否则,申请一个新节点存入当前根节点的数据,在分别用当前根节点的左子树和右子树进行递归调用,创建左右子树
    BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
    {
    	if (a[*pi] == '#' || *pi>=n)//代码健壮性
    	{
    		return NULL;
    	}
    	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    	root->_data = a[*pi];
    	(*pi)++;
    	root->_left = BinaryTreeCreate(a, n, pi);
    	(*pi)++;
    	root->_right= BinaryTreeCreate(a, n, pi);
    
    	return root;
    }
    
    // 二叉树销毁
    void BinaryTreeDestory(BTNode** root)
    {
    	if (*root == NULL)
    		return NULL;
    	BinaryTreeDestory((*root)->_left);
    	BinaryTreeDestory((*root)->_right);
    	free(*root);
    	*root = NULL;//释放的指针置空
    }
    
    
    // 二叉树节点个数
    int BinaryTreeSize(BTNode* root)
    {   //分治算法,为空直接返回0,只有一个根节点返回一,有左右子树了递归下去
    	/*if (root == NULL)
    		return 0;
    	else if (root->_left == NULL && root->_right == NULL)
    		return 1;
    	else
    	{
    		return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
    	}*/
    
    	//计数算法,使用先序遍历,根节点不为空了就加一
    	static count=0;
    	if (root == NULL)
    		return 0;
    	else
    	{
    		count++;
    		BinaryTreeSize(root->_left);
    		BinaryTreeSize(root->_right);
    	}
    	return count;
    }
    
    // 二叉树叶子节点个数
    int BinaryTreeLeafSize(BTNode* root)//利用二叉树遍历判断每个节点
    {
    	static count = 0;
    	if (root == NULL)
    		return 0;
    	else
    	{
    		if (root->_left == NULL && root->_right==NULL)
    			count++;
    		BinaryTreeLeafSize(root->_left);
    		BinaryTreeLeafSize(root->_right);
    	}
    	return count;
    }
    
    //二叉树深度
    //左右子树中深度较高者 再加上根节点一层
    int BinaryTreeHighlength(BTNode* root)
    {
    	if (root == NULL)
    		return 0;
    	int lefthigh = BinaryTreeHighlength(root->_left);
    	int righthigh = BinaryTreeHighlength(root->_right);
    	return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;
    }
    // 二叉树第k层节点个数
    
    //递归方式步骤:
    //给定根节点root:
    //如果root为空,或者层数k <= 0,则为空树或者不合要求,则返回0;
    //如果root不为空,且此时层数 k== 1,则此时root为第K层节点之一,则返回1;
    //如果root不为空,且此时层数 k > 1,则此时需要求root左子树(k - 1 )层节点数和root右子树(k - 1)层节点数
    int BinaryTreeLevelKSize(BTNode* root, int k)
    {
    	if (root == NULL||k<=0)
    		return 0;
    	if (root != NULL && k == 1)
    		return 1;
    	return BinaryTreeLevelKSize(root->_left, k - 1) +
    		BinaryTreeLevelKSize(root->_right, k - 1);
    }
    
    // 二叉树查找值为x的节点
    BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    {
    	BTNode* ret = NULL;
    	if (root == NULL)
    		ret=NULL;
    	else
    	{
    		if (root->_data == x)//先判断根
    		{
    			ret = root;
    		}
    		else
    		{
    			if (ret == NULL)//根不是,先看左子树
    				ret=BinaryTreeFind(root->_left, x);
    			if (ret == NULL)//左子树也不是,再看右子树
    				ret=BinaryTreeFind(root->_right, x);
    		}
    
    	}
    	return ret;
    }
    
    // 二叉树前序遍历
    void BinaryTreePrevOrder(BTNode* root)//根 左子树 右子树
    {
    	if (root)
    	{
    		printf("%c ", root->_data);
    		BinaryTreePrevOrder(root->_left);
    		BinaryTreePrevOrder(root->_right);
    	}
    }
    
    // 二叉树中序遍历
    void BinaryTreeInOrder(BTNode* root)//左子树 根 右子树
    {
    	if (root)
    	{
    		BinaryTreeInOrder(root->_left);
    		printf("%c ", root->_data);
    		BinaryTreeInOrder(root->_right);
    	}
    }
    
    // 二叉树后序遍历
    void BinaryTreePostOrder(BTNode* root)//左子树 右子树 根
    {
    	if (root)
    	{
    		BinaryTreePostOrder(root->_left);
    		BinaryTreePostOrder(root->_right);
    		printf("%c ", root->_data);
    	}
    
    }
    
    // 层序遍历
    //利用队列,先进先出,根节点入队列
    void BinaryTreeLevelOrder(BTNode* root)
    {
    	if (root)
    	{
    		Queue qu;
    		QueueInit(&qu); //初始化队列
    		QueuePush(&qu, root);  //根节点先入队列
    		BTNode* tmp=(BTNode*)malloc(sizeof(BTNode));
    		while (!QueueEmpty(&qu)) //队列不为空时
    		{
    			tmp= QueueFront(&qu);
    			//printf("%c", tmp->_data);//打印队列头(先入队列的头节点)
    			putchar(tmp->_data);
    			if (tmp->_left)   //有左孩子节点就入队列
    				QueuePush(&qu, tmp->_left);
    			if (tmp->_right)   //有右孩子节点就入队列
    				QueuePush(&qu, tmp->_right);
    			QueuePop(&qu);//打印完就出队列了
    		}
    		QueueDestroy(&qu);
    	}
    	
    }
    //层序遍历数组实现过程
    //1、创建一个指针数组,保存二叉树结构体指针,
    //2、保存二叉树根节点,再申请变量 in、out ,控制数组,在遍历过程中,始终能找到节点和该节点的前一个节点,
    //3、循环以上过程。
    void BinaryTreeLevelOrder2(BTNode* root)
    {
    	BTNode* temp[100];//创建pTreeNode指针类型的指针数组
    	int in = 0;
    	int out = 0;
    	temp[in++] = root;  //先保存二叉树根节点 
    
    	while (in > out)//入的比出的多就意味着数组里还有没出的
    	{
    		if (temp[out])
    		{
    			printf("%c ", root->_data);
    			temp[in++] = temp[out]->_left;//根节点的左子树节点入栈
    			temp[in++] = temp[out]->_right;//根节点的右子树节点入栈
    		}
    		out++;//相当于用完后出栈
    	}
    }
    
    // 判断二叉树是否是完全二叉树
    int BinaryTreeComplete(BTNode* root)
    {
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu, root);
    	int flag = 0;
    	BTNode* tmp;
    	while (!QueueEmpty(&qu))
    	{
    		tmp= QueueFront(&qu);
    		if (tmp->_left && tmp->_right)
    		{
    			QueuePush(&qu, tmp->_left);
    			QueuePush(&qu, tmp->_right);
    		}
    		else if (!tmp->_left && tmp->_right)//有右孩子却没左孩子,不是完全二叉树,返回0;
    			return 0;
    		else if (!tmp->_right)//右孩子为空,不知道左孩子的情况
    		{
    			flag = 1;//标记右孩子为空
    			if (tmp->_left)//且有左孩子
    				QueuePush(&qu, tmp->_left);//这个左孩子先入栈,在判断其左右子树,只要有任一左右子树,必然不是完全二叉树,
    		}
    		if (flag == 1 && (tmp->_left || tmp->_right))//右孩子为空   (本来就缺孩子 你再生有孩子 那绝对不是完全二叉树了)取出的队列头节点不是叶子(有左孩子或者有右孩子)
    			return 0;
    		QueuePop(&qu);
    	}
    	QueueDestroy(&qu);
    	return 1;
    }
    
    展开全文
  • C语言二叉树的深度

    千次阅读 2018-11-09 22:30:50
    6-8 求二叉树高度 (20 point(s)) 本题要求给定二叉树的高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; ...

    6-8 求二叉树高度 (20 point(s))

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

    函数接口定义:

    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

     

    如果树为空,那么高度为0

    如果根节点没有左右孩子,那么树的高度为1

    否则,递归求左子数和右子数的高度,然后总高度等于1+max(depthR,depthL)

    #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;
    }
    /* 你的代码将被嵌在这里 */
    int GetHeight(BinTree BT)
    {
    	int depthL;              // 左子数深度
    	int depthR;              // 右子数深度
    	if (BT == NULL)
    		return 0;
    	if (BT->Left == NULL && BT->Right == NULL)
    		return 1;
    	depthL = GetHeight(BT->Left);
    	depthR = GetHeight(BT->Right);
    	if (depthL > depthR)
    		return 1 + depthL;
    	else
    		return 1 + depthR;
    
    }
    

     

     

     

     

     

     

     

     

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

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

    在这里插入图片描述

    #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
    
    展开全文
  • 二叉树递归特性可以计算二叉树高度:不多逼逼,code:#includeusing namespace std;typedef struct BinaryTreeNode{char data; //数据struct BinaryTreeNode *left; //左孩子struct BinaryTreeNode *right; //右...
  • 递归法求二叉树高度 递归法可以理解为一个子问题当一棵树只有左孩子和右孩子的时候我们只需要计算其左孩子的高度和其右孩子的高度并且求的他门两个之间的最大值并且+1即可 这个1就是根节点这样我们就得到了递归代码...
  • 但为了防范于未然,将来可能需要用到,因此我特地花了一些时间想要把那些软件工程师天天挂嘴边的二叉树啥的学习了一遍,并手写代码。写此篇博客,一是为了总结学习二叉树中获得的零散知识;二是希望把自己学习过程及...
  • 数据结构——计算节点个数、二叉树高度一、计算各种节点(1)计算总节点:(2)计算单分支节点:(3)计算双分支节点:二、计算二叉树高度代码实现: 一、计算各种节点 二叉树结构体如下: // 二叉树结构体 ...
  • 二叉树 - 递归计算二叉树高度C语言

    万次阅读 多人点赞 2018-04-03 21:54:31
    2.完整代码如下:/* 递归函数 - 计算二叉树高度(只有一个根节点的二叉树高为1) */ #include &lt;iostream&gt; #include &lt;malloc.h&gt; using namespace std; //二叉树节点定义 typedef int ...
  • 源代码 /************************** 计算二叉树高度,寻找最长路径 ***********************************/ #include typedef struct abc { struct abc *lchild,*rchild; int data; }Node; Node * init(); void scan...
  • C语言计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){...
  • 二叉树的后根遍历序列为dabec,中根遍历序列为debac,则先根遍历序列为( ) A.acbed B.becab C.deabc D.cedba3.含有n个结点的二叉树用二叉链表表示时,空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 12.有关树的叙述...
  • C语言计算二叉树的宽度的两种方式二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。采用递归方式下面是代码内容:int GetMaxWidth(BinaryTree pointer){int ...
  • C语言实现二叉树

    2018-10-17 22:03:36
    1. C语言实现二叉树中节点间最大距离 #include<stdio.h> typedef struct TreeNode { int data; struct TreeNode * lchild; struct TreeNode * rchild; }TreeNode; /* 我们可以将所有的结点的左右子树的...
  • 1、班级: 数学101软件 学号:5姓名: 田贵文实验组别: 实验日期: 报告日期: 成绩: 报告内容:(目的和要求、原理、步骤、数据、计算、小结等)实验名称:C语言编程二叉树一、实验目的及要求1.掌握二叉树的存储...

空空如也

空空如也

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

c语言二叉树高度计算

c语言 订阅