精华内容
下载资源
问答
  • 1、完全二叉树与满二叉树的区别: ...在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 计算完全二叉树深度公式-推导证明: 假设两种极端情况 <1>该树为满二叉树时...

    1、完全二叉树与满二叉树的区别:

    满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树。 
    完全二叉树:设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。

    2、计算二叉树的深度 : 

    满二叉树的深度为k=log2(n+1)
    在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 

    计算完全二叉树深度公式-推导证明:
    假设两种极端情况
    <1>该树为满二叉树时,结点n1=2^k-1
    此时k=log2(n1+1)
    
    <2>当该树为满二叉树附加一个结点时,n2=2^(k-1),此时k=log2n2 +1,
    并且log2(n1+1)=log2n2 +1
    对任意结点n的完全二叉树,n2<=n<=n1
    2^(k-1)<=n<=2^k -1
    log2(n+1)<=k<=log2n +1
    则k向下取整log2n +1
    


     

    展开全文
  • python求二叉树深度 1.代码实现 class BinaryTreeNode(object): # 创建二叉树结点的函数 def __init__(self): self.data = '#' self.LChild = None self.RChild = None class BinaryTree(object): # 创建...
  • 二叉树深度的算法二叉树深度方法一:深度优先的遍历方式方法二:广度优先的遍历方式总结 二叉树深度 注:本文中二叉树通过二叉链表构建。 节点类型定义如下: struct node{ char data; node *lchild; node *...

    求二叉树深度

    注:本文中二叉树通过二叉链表构建。
    节点类型定义如下:

    struct node{
    	char data;
    	node *lchild;
    	node *rchild;
    };
    

    方法一:深度优先的遍历方式

    思路一(自上向下):每下一层,就和当前暂存的最大的深度作比较并取最大值

    对二叉树做遍历操作,最简单可以用递归的方式实现。
    这就需要我们对递归进行下一层的时候,需要记录下一层的深度等于当前深度+1。

    通过递归实现后的代码如下:

    int maxDeep = 0; //暂存的最大深度
    void MaxDeep(node* root, int nowDeep){
    	if (root == NULL){//递归结束条件,说明这一层已经不是二叉树的节点,也就不需要使nowDeep和maxDeep进行比较
    		return;
    	}
    	
    	maxDeep = max(maxDeep, nowDeep);//取较大值
    	MaxDeep(root->lchild, nowDeep+1);//递归处理左子树
    	MaxDeep(root->rchild, nowDeep+1);//递归处理右子树
    }
    

    需要注意的是,调用时,根节点的深度为一,即nowDeep传1。

    思路二(自下向上):当前树的最大深度等于其子树的最大深度+1
    在第一种思路中,我们需要借助一个额外的变量maxDeep去记录当前处理过的最大深度,这是一个外部变量,当然可以放到形参里面,但是一个对递归没有什么作用的数作为一个形参出现就会显得有些奇怪,用起来也不方便。

    为了方便使用,我们可以换一种思路:
    既然自上向下的路走不通,可以反过来走。

    对于一棵二叉树,可以根据有无父节点分为“根节点”和“非根节点”,对于每个“非根节点”又可以作为一棵新的树的根节点。那么这种思路反过来,就有了:
    当前树的最大深度等于其子树的最大深度+1。这里的“1”是根节点自己还有一层深度需要加上。

    以这种思路实现的代码:

    int maxDeep(node* root){
    	if(root == NULL){//递归到叶子节点的“子树”,不存在,其深度为0,递归结束。
    		return 0;
    	}
    	return max(maxDeep(root->lchild),maxDeep(root->rchild))+1;//如果有子树,其深度为左右子树的最大值+1。
    }
    

    这个代码还可以简写成:

    int maxDeep(node* root){
    	return root == NULL ? 0 : max(maxDeep(root->lchild),maxDeep(root->rchild))+1;
    }
    

    方法二:广度优先的遍历方式

    深度优先的方式是一路走到黑,记录路径长度。
    那么广度优先的方式就是真真正正的计算层次来得到二叉树的深度了。

    这里用到了二叉树的层次遍历的思路
    实现代码:

    struct que{//只是封装了队列节点类型,并没有自己封装队列,可以使用STL的queue进行操作
    	node* root;
    	int index;
    }; 
    
    int maxDeep(node* root){
    	que q[505];
    	for (int i = 0;i < 505; i++){//初始化
    		q[i].root = NULL;
    		q[i].index = 0;
    	}
    	//层次遍历
    	int head = 0;
    	int tail = 1;
    	q[tail].root = root;//根节点入队
    	q[tail].index = 1;
    	while (head != tail){
    		head++;//当然也可以写成环形队列的方式
    		if (q[head].root->lchild != NULL){//其左子树不为空
    			tail++;
    			q[tail].root = q[head].root->lchild;//左子树入队
    			q[tail].index = q[head].index+1;//记录其左子树的根节点所在层数为该节点层数+1
    		}
    		if (q[head].root->rchild != NULL){//其右子树不为空
    			tail++;
    			q[tail].root = q[head].root->rchild;//右子树入队
    			q[tail].index = q[head].index+1;//记录其右子树的根节点所在层数为该节点层数+1
    		}
    	}
    	return q[tail].index;//做到最后就是最深的一层,即为二叉树的深度
    }
    

    总结

    • 两种方法各有优劣,深度优先的方法使用了递归的方式进行实现,对时间和空间的消耗都是较大的,但编码复杂度极低;广度优先的方法则相反,对时间空间的消耗较小,但编码复杂度较高。
    • 深度优先的方式可以不适用递归的方式进行,需要手动用栈进行模拟递归,对系统时间和空间的消耗有所改善,但编码复杂度将会提高,需要自行进行取舍。
    • 在广度优先的方式实现时没有对队列进行封装,同时可以使用C++ STL的queue进行实现。
    展开全文
  • 二叉树深度

    千次阅读 2014-07-13 13:56:06
    1.二叉树深度:树中结点的最大层次称为树的深度或高度。 2.二叉树层次:从根开始定义起,根为第一层,根的孩子为第二层,以此类推。 要点: 1.递归。 2.二叉树深度为左右子树深度较大值+1。 代码: ...
    概念:
    1.二叉树深度:树中结点的最大层次称为树的深度或高度。
    2.二叉树层次:从根开始定义起,根为第一层,根的孩子为第二层,以此类推。
    要点:
    1.递归。
    2.二叉树深度为左右子树深度较大值+1。

    代码:

    /*
    求二叉树深度
    by Rowandjj
    2014/7/13
    -------------------------------
    题目描述:
    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
    输入:
    第一行输入有n,n表示结点数,结点号从1到n。根结点为1。 n <= 10。
    接下来有n行,每行有两个个整型a和b,表示第i个节点的左孩子右孩子。a为左孩子,b为右孩子。当a为-1时,没有左孩子。当b为-1时,没有右孩子。
    输出:
    输出一个整型,表示树的深度。
    样例输入:
    3
    2 3
    -1 -1
    -1 -1
    样例输出:
    2
    */
    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    typedef struct _NODE_//采用数组存储
    {
    	int l;//存储左孩子的序号
    	int r;//存储右孩子的序号
    }TreeNode,*pTree;
    int GetDepth(pTree T,int index)
    {
    	if(!T)
    	{
    		return 0;
    	}
    	if(index == -1)
    	{
    		return 0;
    	}
    	int nl = GetDepth(T,T[index].l);
    	int rl = GetDepth(T,T[index].r);
    	return (nl > rl) ? nl+1: rl+1;
    }
    int main()
    {
    	int n;
    	int l,r;//左右孩子的序号
    	while(cin >> n)
    	{
    		pTree pT = (TreeNode*)malloc(n * sizeof(TreeNode));
    		if(!pT)
    		{
    			exit(-1);
    		}
    		for(int i = 0; i < n; i++)
    		{
    			cin>>l>>r;
    			pT[i].l = (l == -1) ? -1 : l-1;
    			pT[i].r = (r == -1) ? -1 : r-1;
    		}
    		cout<<GetDepth(pT,0);
    	}
    	
    	return 0;
    }


    展开全文
  • 【数据结构】计算二叉树深度完整C语言代码

    千次阅读 多人点赞 2020-07-30 19:56:36
    二叉树深度的计算<数据结构>二叉树的深度计算完整代码展示程序结果 二叉树的深度计算 我们先看一个深度为3的二叉树。想求得此二叉树深度,先计算左孩子深度,再计算右孩子深度,比较得出最大值,即二叉树深度...

    【数据结构】二叉树深度的计算

    二叉树的深度计算

    我们先看一个深度为3的二叉树。想求得此二叉树深度,先计算左孩子深度,再计算右孩子深度,比较得出最大值,即二叉树深度。
    通过先序序列键盘输入一个二叉树 ABD##E##CF###。

    在这里插入图片描述
    注:
    二叉树的输入方式:先左后右,深度遍历,没子树的结点为#。
    在这里插入图片描述

    设计算法则先遍历二叉树的左子树的深度,然后再遍历二叉树右子树的深度。最后判断左子树和右子树的深度,如果左子树比右子树深则返回左子树深度+1,否则返回右子树深度+1。

    完整代码展示

    #include <stdio.h>
    #include <malloc.h>
    typedef struct BiTNode
    {
    	char data;  /*结点的数据域*/
    	struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
    } BiTNode , *BiTree;
    
    /*创建一棵二叉树*/
    void CreatBiTree(BiTree *T)
    {
    
    	char c;
    	scanf("%c",&c);
    	if(c == '#') 
    		*T = NULL;
    	else
    	{
    		*T = (BiTNode * )malloc(sizeof(BiTNode)); /*创建根结点*/
    		(*T)->data = c; /*向根结点中输入数据*/
    		CreatBiTree(&((*T)->lchild)); /*递归地创建左子树*/
    		CreatBiTree(&((*T)->rchild)); /*递归地创建右子树*/
    	}
    }
    
    //计算二叉树的深度
    int getBitreeDepth(BiTree T)
    {
    	int leftHeight, rightHeight, maxHeight;//左子树,右子树,最大深度
    	if (T != NULL) //如果为空树
    	{
    		leftHeight = getBitreeDepth(T->lchild);//左子树深度
    		rightHeight = getBitreeDepth(T->rchild);//右子树深度
    		maxHeight = leftHeight>rightHeight?leftHeight:rightHeight;//最大深度
    		return maxHeight+1;//二叉树深度=最大深度+1
    	}
    	else
    	{
    		return 0;
    	}
    }
    
    void main()
    {
    	BiTree T = NULL; /*最开始T指向空*/
    		printf("请您输入一个二叉树(以#为空子树):\n");
    	CreatBiTree(&T); /*创建二叉树*/
    		printf("\n二叉树的深度为%d\n",getBitreeDepth(T));
    	getchar() ;
    	getchar() ;
    }
    
    
    

    程序结果

    在这里插入图片描述

    展开全文
  • 二叉树深度递归怎么去想问题? 求二叉树的深度为什么可以用递归呢?这是因为我们这样思考问题:求一个二叉树的深度,我们即求根结点所在二叉树的深度,即求左右子树的最大深度,对于每个结点都是求左右子树的最大...
  • 二叉树的深度,平衡二叉树深度

    千次阅读 2016-07-11 19:26:20
    题目描述输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。算法: 1、如果树为空,则深度为0 2、如果树不是空,那么深度是左子树的...
  • 二叉树深度计算

    万次阅读 多人点赞 2019-03-10 15:45:36
    今天面试,被问到了二叉树深度计算问题。 一听到这个问题,第一反应是大学被写烂了的基本数据结构问题。 然而我已经毕业3年,没写算法很久,手都生了。但是呢,不能说生了就只对面试官说思路吧,于是还是...
  • 二叉树深度优先遍历、广度优先遍历{非递归}
  • 二叉树深度的递归算法 intdepth(BTreeroot)...{ intldepth,rdepth; if(!root) return0; else...{ ldepth=depth(root->lchild); rdepth=depth(root->rchild); if(ldepth>=rdepth)//取左右子树深度的...
  • 主要介绍了PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次),结合实例形式详细分析了php针对二叉树的深度优先遍历与广度优先遍历相关操作技巧与注意事项,需要的朋友可以参考下
  • 要求二叉树的深度,方法是先求出左子树的深度,再求出右子树的深度,二叉树的深度就是左子树的深度和右子树的深度中的最大值加1.... //求二叉树深度的算法 public int getDepth(BiTreeNode T) { if...
  • 二叉树深度:递归的方法:从根节点按照先序顺序遍历二叉树,返回左子树和右子树中较大的深度,再加上1就是根节点的深度。C++代码实现:typedef struct TreeNode{ int data; struct TreeNode* leftchild; struct...
  • C数据结构,能够进行二叉树深度广度查询。数据结构基础作业
  • java 实现二叉树深度优先遍历的 前、中、后序遍历(递归).pdf
  • 【算法题】递归求二叉树深度

    千次阅读 2019-06-01 09:25:01
    这两道题,如果你知道二叉树深度算法的递归过程,就很容易做出来。 关于二叉树的相关知识,可以看我的这篇文章:数据结构】树的简单分析总结(附js实现) 题目描述 给定一个二叉树,找出其最大深度。 二叉树的深度为...
  • 计算二叉树深度 统计二叉树的结点个数   建立二叉链表 在先序遍历的递归算法中,将输出语句改为输入语句即可。(可回顾“递归算法”) 需要注意的是,递归算法会遍历满二叉树中的每一个结点,所以我们必须对空...
  • 数据结构之二叉树深度的求解

    千次阅读 2016-11-10 14:18:22
    题目:二叉树用二叉链表表示,编写求二叉树深度的算法。 答案是: int height(Bitree T) {  if (T==NULL) return 0;  u=height(T->lchild);  v=height(T->rchild);  if (u>n) return
  • 二叉树深度优先遍历和广度优先遍历
  • 二叉树深度(递归方式)int FindTreeDeep(BinTree BT){ int deep=0; if(BT!=null){ int left=FindTreeDeep(BT.left); int right=FindTreeDeep(BT.right); deep=left>right?left+1:right+1; }
  • 数据结构实验之二叉树的建立与遍历 Time Limit: 1000MS Memory limit...请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。 输入  输入一个长度小于50个字符的字符串。 输出 输出共有
  • 二叉树深度遍历的几种写法

    千次阅读 2016-04-20 15:57:42
    二叉树深度遍历的几种写法 二叉树的结构:struct treeNode{ int val; treeNode* left; treeNode* right; treeNode(int x):val(x),left(NULL),right(NULL){} };最简单的是递归方式写出,这种效率比较差,但是...
  • 二叉树深度和高度 In this tutorial, we will learn how to find height and depth of binary tree with program implementation in C++. It is one of the most commonly used non-linear data structures. We will...
  • 二叉树深度的算法

    万次阅读 2012-02-15 11:35:57
    题目:二叉树用二叉链表表示,编写求二叉树深度的算法。 答案是: int height(Bitree T) {  if (T==NULL) return 0;  u=height(T->lchild);  v=height(T->rchild);  if (u>n) return (u

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 98,152
精华内容 39,260
关键字:

二叉树深度