精华内容
下载资源
问答
  • 二叉树深度计算

    万次阅读 多人点赞 2019-03-10 15:45:36
    今天面试,被问到了二叉树深度计算问题。 一听到这个问题,第一反应是大学被写烂了的基本数据结构问题。 然而我已经毕业3年,没写算法很久,手都生了。但是呢,不能说生了就只对面试官说思路吧,于是还是...

    今天面试,被问到了二叉树的深度计算问题。

    一听到这个问题,第一反应是大学被写烂了的基本数据结构问题。

    然而我已经毕业3年,没写算法很久,手都生了。但是呢,不能说生了就只对面试官说思路吧,于是还是不假思索的立马拿起笔,写了起来,毕竟这是一个基本的数据结构题目。

    首先立马写了一个二叉树结构。

    public class BinaryTree{
            BinaryTree lChild, rChild;
            int value;
        }

    一写出来,立马有了感觉。顺势写了计算方法

    public int computeTreeDepth(BinaryTree binaryTree){
            if(binaryTree.lChild == null && binaryTree.rChild == null){
                return 1;
            }
            int lDepth = computeTreeDepth(binaryTree.lChild);
            int rDepth = computeTreeDepth(binaryTree.rChild);
            return Math.max(lDepth, rDepth);
        }

    然后就给面试官看了。

    面试官问我有感觉哪里不对吗?哎,只怪我太久没写算法题了,连这个基本的深度计算,都出现简单失误。更可气的是在当时的紧张环境下,我竟然没有发现哪里问题。后来经过面试官提醒,也终于改了过来。

        public int computeTreeDepth(BinaryTree binaryTree){
            if(binaryTree == null){
                return 0;
            }
            if(binaryTree.lChild == null && binaryTree.rChild == null){
                return 1;
            }
            int lDepth = computeTreeDepth(binaryTree.lChild) + 1;
            int rDepth = computeTreeDepth(binaryTree.rChild) + 1;
            return Math.max(lDepth, rDepth);
        }

    此时我的心里一万个对自己无语,竟然在面试的时候出现这么大的失误(不过也只怪我平常自从毕业就很少去深入写算法题了,以后一定要注意)

    这个时候,面试官说这是递归实现,写一下非递归实现。

    当时心里无语的我顿时一塞,非递归实现,然后一想,也简单。然后就屁颠屁颠的开始写起来。写着写着我发现,情况似乎不是我想的这么简单。随着时间的深入,我的心里变得异常紧张,结果硬是在那几分钟没想出来。此刻真是深深的鄙视自己,无论是什么原因让我当时的大脑短路了,终究的结果是我没写出来非递归实现。之后面试官委婉的叫我下去在思考这个问题吧。

    总结一下:

    问题:自己当时太想着展现自己,导致自己的思路太过紧凑反而限制了我的思维,导致这个简单的问题也写出漏洞,甚至连非递归实现最后没编写出来。

    对自己的思考:

    1.作为程序猿,平常还是要多锻炼自己的算法编写习惯,多去思考。只有这样才可以在面试中对算法题有一个较好的把控。

    2.面试的时候心态要放平稳,不能心浮气躁,导致自己出现各种临时小问题。因为对方只会看结果。

    回来了,自己重新写了一遍二叉树的深度计算实现,果然很简单。记录一下吧,就当是自己前进的路上的一个绊脚石,也希望自己在每一次总结之后能进步自己。

    多思考,多学习,放平心态,去面对每一个新技术,新思维。

    下面贴代码

    二叉树深度计算的递归实现:

        public int computeTreeDepth(BinaryTree binaryTree){
            if(binaryTree == null){
                return 0;
            }
            return Math.max(computeTreeDepth(binaryTree.lChild), computeTreeDepth(binaryTree.rChild)) + 1;
        }

    二叉树深度计算的非递归实现:

    首先想到是直接遍历,如果是直接遍历那自然就有两种思路,广度优先和深度优先。

    先说广度优先,因为是遍历下一层意味着上一层都已遍历,先进先出,采用队列实现:

        public int computeTreeDepth(BinaryTree binaryTree){
            //实例化队列
            Queue<BinaryTree> mVisitList = new LinkedList<>();
            BinaryTree tmp;
            int depth = 0, lengthTmp;
            if(binaryTree == null){
                //根为空,直接返回0
                return 0;
            }
            //将根加入队列
            mVisitList.offer(binaryTree);
            while (!mVisitList.isEmpty()){
                //只要队列不为空,说明新的一层数据不为空,且已经加到队列,深度+1
                depth ++;
                //遍历该层到所有数据,将他们出队,并附带把所有下一层到数据都加进来(如果有的话)
                lengthTmp = mVisitList.size();
                while (lengthTmp -- > 0){
                    tmp = mVisitList.poll();
                    if(tmp.lChild != null){
                        mVisitList.offer(tmp.lChild);
                    }
                    if(tmp.rChild != null){
                        mVisitList.offer(tmp.rChild);
                    }
                }
            }
            return depth;
        }

    然后深度优先,因为是深度遍历那肯定是先进后出,采用栈实现,然后遍历思路是先遍历当前节点的左子树,没有左子树到情况在遍历右子树:

        public int computeTreeDepth(BinaryTree binaryTree){
            //实例化栈
            Stack<BinaryTree> mVisitList = new Stack<>();
            BinaryTree tmp = binaryTree;
            int depth = 0;//遍历过程中到最大深度
            while (tmp != null){
                if(tmp.lChild != null || tmp.rChild != null){
                    //如果有子树,将当前节点入栈,且更新最大深度
                    mVisitList.push(tmp);
                    depth = Math.max(depth, mVisitList.size());
                    //因为是左子树优先,所以深度遍历下一个子节点的时候,优先左子树
                    tmp = tmp.lChild != null ? tmp.lChild : tmp.rChild;
                    continue;
                }
                //当前节点没有子树,直接更新最大深度(访问到当前节点到深度是栈的深度+1)
                depth = Math.max(depth, mVisitList.size() + 1);
                //此时回溯去找右子树
                while (!mVisitList.isEmpty()){
                    if(mVisitList.peek().rChild != null && mVisitList.peek().rChild != tmp){
                        //如果栈顶节点的右子树不为空,且栈顶节点的右子树不等于正在访问的节点,访问右子树
                        tmp = mVisitList.peek().rChild;
                        break;
                    }
                    //说明当前栈顶节点的右子树为空,直接出栈,继续回溯
                    // 且要更新当前节点,用于记录当前正在回溯的节点,避免死循环回溯
                    tmp = mVisitList.pop();
                }
            }
            return depth;
        }

    好了,上面就是二叉树的实现,自己写了几个测试用例没出现问题。但是不能保证完全没问题,有问题的话或者可以优化的欢迎留言交流,一起学习进步。

    展开全文
  • 1、完全二叉树与满二叉树的区别: 满二叉树:深度为k且有2^k-1个结点的二叉树称为满二叉树。 完全二叉树:设二叉树的深度为h,除...计算完全二叉树深度公式-推导证明: 假设两种极端情况 <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
    


     

    展开全文
  • 试写一个判别给定二叉树是否为完全二叉树的程序。 (1) 此二叉树以二叉链表作存储结构;
  • 二叉树深度计算 1、一颗树只有一个节点,它的深度是1; 2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1; 3、二叉树的根节点只有右子树而没有左子树,那么可以判断...

    二叉树的深度计算
    1、一颗树只有一个节点,它的深度是1;

    2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1;

    3、二叉树的根节点只有右子树而没有左子树,那么可以判断,那么二叉树的深度应该是其右树的深度加1;

    4、二叉树的根节点既有右子树又有左子树,那么可以判断,那么二叉树的深度应该是其左右子树的深度较大值加1。

    int TreeDeep(struct node *T)
    {
        int deep=0;
        if(T)
        {
            int ld=TreeDeep(T->l);
            int rd=TreeDeep(T->r);
            deep=ld>=rd?ld+1:rd+1;
        }
        return deep;
    }
    

    在这里插入图片描述
    满二叉树与完全二叉树
    一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树 。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。

    展开全文
  • 二叉树深度计算也就是对二叉树层数这个递归函数的记录过程。 验证某一元素在二叉树中的存在性也就是对二叉树的一个遍历过程,如果存在相同元素,就将该树节点的地址赋给一个新的树节点。 本实验用到简单二叉树 #...

    二叉树深度计算也就是对二叉树层数这个递归函数的记录过程。

    验证某一元素在二叉树中的存在性也就是对二叉树的一个遍历过程,如果存在相同元素,就将该树节点的地址赋给一个新的树节点。

    本实验用到简单二叉树

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define TRUE 1
    #define ERROR 0
    #define FALSE 0
    #define LIST_INIT_SIZE 100 
    #define LISTINCREMENT 10 
    #define OVERFLOW 0 
    typedef int Status;
    typedef Status ElemType;
    typedef char * Tree;
    typedef struct	BitNode{
    	ElemType data;                     //每一个结点的数据域 
    	struct BitNode *lchild;            //每一个结点的左孩子指针域用于存放左孩子结点的地址 
    	struct BitNode *rlight;            //每一个结点的右孩子指针域用于存放右孩子结点的地址 
    }BitNode, *BitTree; 
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    Status CreateBiTree(BitTree &T);
    Status getDepth(BitTree T);
    void search(BitTree T,BitTree &F,char KEY);
    //本实验的目的是按先序遍历的方式创建一个二叉树,然后按照中序遍历的方式实现查找,输出。
    //生成二叉树的必须条件是通过递归函数对子树依次进行遍历生成,或者遍历输出。 
    int main(int argc, char *argv[]) {
    	BitTree T,F;
    	char KEY;
    	printf("请输入要查找验证的元素:");
    	scanf("%c",&KEY);
    	getchar();
    	printf("请输入创建的二叉树:");
    	printf("\n"); 
    	CreateBiTree(T); 
    	Status m;
    	m=getDepth(T);
    	printf("该二叉树的深度是:%d",m);
    	printf("\n");
    	
    	
    	
    	search(T,F,KEY);
    	if(F!=NULL){
    		printf("该二叉树中存在该元素;"); 
    	}else{
    		printf("该二叉树中不存在该元素;");
    	}
    	return 0;
    }
    
    Status CreateBiTree(BitTree &T){                         //创建一个长度为n的完全二叉树 ,这种创建方法时按照先序遍历的方式创建的,依据根左右的顺序逐层创建 
    	char a;
    	scanf("%c",&a);
    	if(a==' '){
    		T=NULL;
    	}else{
    	T=(BitNode *)malloc(sizeof(BitNode));              //申请一个结构体类型的结点空间 
    		if(T==NULL){
    			exit(OVERFLOW);
    		}else{
    			T->data=a;                  	     //给结点传入数据(设置结点的数据域) 
    			CreateBiTree(T->lchild);             //按照先序遍历的顺序准则,创建左孩子,并且如若根节点的左孩子不为空,继续遍历左孩子的左孩子,如若左孩子的左孩子为空,
    										       	//然后遍历左孩子的右孩子,依此遍历创建。 
    			CreateBiTree(T->rlight);            //右孩子同样,前提是左孩子为空才可以遍历右孩子。 
    		}	
    	}
    	return OK;
    }
    
    Status getDepth(BitTree T){                   //深度求法第一想法是在创建函数的时候直接在递归中用一个人变量存储嵌套的次数也就是二叉树的深度。 
    											  //但是有个问题就是如果不是标准的二叉树,在中间结点上有结点叶子,但是在起始结点没有叶子。 
    	ElemType m,n;
    	if(T==NULL){
        	return 0;                             //子树均为空则返回 0 
    	}else{
    		m=(getDepth(T->lchild));
    			
    		n=(getDepth(T->rlight));
    		
    		if(m>=n){                            //这里可以用三目运算符 
    			return m+1;
    		}else{
    			return n+1;
    		}	
    	}
    }
    //实现查找数据域值等于key的结点是否存在,若存在则p指向该key值的结点,否则p为空。
    //第一步需要将整个二叉树进行遍历。 
    //void search(BitTree T,BitTree &F,char KEY){                          //要改变的变量就定义为引用指针  
    //	if(T==NULL){
    //		exit(OVERFLOW);
    //	}else{
    //		if(T->data==KEY){
    //		F=T;
    //		}else{
    //		search(T->lchild,F,KEY);
    //		search(T->rlight,F,KEY);	
    //		}	
    //	}
    //} 
    
    
    void search(BitTree T,BitTree &F,char KEY){                          //要改变的变量就定义为引用指针  
    	if(T!=NULL){
    		if(T->data==KEY){
    		F=T;
    		}else{
    		search(T->lchild,F,KEY);
    		if(F==NULL)
    		search(T->rlight,F,KEY);	
    		}	
    	}
    } 
    

    运行结果:

    出现的问题:

    1,我不太清楚在输入一个字符后为什么不可以直接创建二叉树,显示是二叉树无法中止,然后在输入函数后加上getchar()函数即可实现二叉树的创建,这一块不太明白是何缘由,网上的解决方案不太认可(未解决)

    2,(代码中注释的那一段寻找函数) 在验证某一函数的存在性只能遍历左子树,一到遍历右子树就自动结束。

    展开全文
  • 如何计算完全二叉树深度

    万次阅读 2017-09-22 19:46:52
    如何计算完全二叉树深度一棵有12个节点的完全二叉树,其深度是()一棵有12个节点的完全二叉树,其深度是() 4 5 3 6 在此之前我想说一下三种二叉树 Full Binary Tree Perfect Binary Tree Complete Binary Tree ...
  • 完全二叉树深度

    千次阅读 2019-09-25 20:00:59
    在完全二叉树中,具有n个结点的完全二叉树深度为(log2n)+1,其中(log2n)+1是向下取整。 满二叉树的深度为k=log2(n+1) 证明: 假设两种极端情况 该树为满二叉树时,结点n1=2^k-1 此时k=log2(n1+1) 当该树为满...
  • 数据结构(九)满二叉树深度计算

    千次阅读 2015-10-12 22:01:57
    答案是: log2(n+1)+1,注意是分支结点是n个 假设树有K层,所有的分枝节点都在1-(k-1)层,每层都是满的,对有1-(k-1)层,有2^(k-1)-1=n 变形后得:k=log(n+1)+1。 所以答案应该选择B。原题链接: ...
  • 二叉树与完全二叉树计算节点数 这是一个刷题博客,记录leetcode上关于二叉树栏目的刷题题解。 二叉树的节点数(leetcode 222) 题目描述:完全二叉树的节点个数 算法分析与设计 思路 1 如果没有 “完全二叉树” ...
  • 【数据结构】计算二叉树深度完整C语言代码

    千次阅读 多人点赞 2020-07-30 19:56:36
    二叉树深度的计算<数据结构>二叉树的深度计算完整代码展示程序结果 二叉树的深度计算 我们先看一个深度为3的二叉树。想求得此二叉树深度,先计算左孩子深度,再计算右孩子深度,比较得出最大值,即二叉树深度...
  • 由于是完全二叉树,所以二叉树的层高h一定是最左边节点的深度。规定根节点在第0层。则第h层至少有1个节点,至多有2h{2}^{h}2h个节点。所以二叉树的节点总数最少为: 最多为: 把根节点编号为1,然后从左到右,从上...
  • // 二叉树可以分为普通二叉树,搜索二叉树(排序二叉树),平衡二叉树,完全二叉树,满二叉树 // 搜索二叉树满足所有左子树的值都不大于根节点,所有右子树的值都不小于根节点,并且左右子树也都是搜索二叉树 // 平衡...
  • 本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。希望各位读者能够关注专题,并给出相应意见,通过系列的学习做到心中有“树”。 二叉树...
  • 首先,完全二叉树的含义就是从左到右依次排满一行再排一行,各节点之间都是相邻的。 判断他是否是完全二叉树, 分情况判断: ① 一个节点有右子树,但是没有左子树那么他一定不是完全二叉树 ② 一个节点的...
  • 完全二叉树计算叶子结点数

    千次阅读 2015-04-19 13:17:00
    深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。 2.一条规则: 对任何一棵二叉树T,如果其终端结点数为,度为2的结点数为,则。 ...
  • = deapth(node.rnode) if m >= n { return m + 1 } else { return n + 1 } } } } 计算二叉树的节点个数,如果指针指向空,返回0,如果指向下一个节点,则返回左节点的个数和右节点的个数再加本身。...
  • 二叉树各种计算公式

    万次阅读 多人点赞 2018-07-01 14:29:19
    1. n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种2. n层二叉树的第n层最多为2^(n-1)个3. 二叉树节点计算公式 N = n0+n1+n2,度为0的叶子节点比度为2的... 具有n个节点的完全二叉树深度为log2(n) + 16. B-树,除...
  • // 计算二叉树深度 // 参数:二叉树根节点root // 返回:二叉树深度 { // 请在这里补充代码,完成本关任务 /********** Begin *********/ int m; int n; if(root==NULL) { return 0; } else { m=...
  • 计算完全二叉树的树高 思路: 要求在低于O(N)的时间复杂度内解决问题 由于任务是累加,每个递归中都是O(1),所以很自然地,树的节点统计必然也是至少和节点数量一样O(N) —— 至少要遍历一遍吧 但是完全二叉树,满...
  • 满二叉树 完全二叉树
  • 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。 ————来自维基...
  • 完全二叉树

    千次阅读 2019-11-21 15:02:26
    堆常用来实现优先队列。用数组保存数据,而不是链表。 在队列中,操作系统调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待...完全二叉树:若设二叉树的深度为h,除第 h 层外,其...
  • 二叉树深度

    千次阅读 2020-01-27 17:22:05
    二叉树深度计算 1、一颗树只有一个节点,它的深度是1; 2、二叉树的根节点只有左子树而没有右子树,那么可以判断,二叉树的深度应该是其左子树的深度加1; 3、二叉树的根节点只有右子树而没有左子树,那么可以判断...
  • “遍历”是二叉树各种操作的基础,假设访问结点的具体操作不仅仅局限于输出结点数据域的值,而是把“访问”延伸到对结点的判别、计数等其他操作,可以解决一些关于二叉树的其他实际问题。如果在遍历过程中生成结点,...

空空如也

空空如也

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

完全二叉树深度计算