精华内容
下载资源
问答
  • 二叉树深度递归怎么去想问题? 求二叉树的深度为什么可以用递归呢?这是因为我们这样思考问题:求一个二叉树的深度,我们即求根结点所在二叉树的深度,即求左右子树的最大深度,对于每个结点都是求左右子树的最大...

    思路

    二叉树深度递归怎么去想问题?

    求二叉树的深度为什么可以用递归呢?这是因为我们这样思考问题:求一个二叉树的深度,我们即求根结点所在二叉树的深度,即求左右子树的最大深度,对于每个结点都是求左右子树的最大深度,这样就是把一个大的问题切分成小的问题,然后最小的问题有一个出口,结点为空时深度为 0

    二叉树的深度如果不用递归该怎么办?

    最直接的想法,就是使用栈,递归本来就是一种栈的方式,这时我们又联想到了先序,中序,后续遍历时候也使用到了栈来遍历,那我们也适用先序遍历,来求栈的深度就行了吧?我们再仔细思考会发现,不论是先序还是中序,当左结点找不到时会切换到右结点,并且切换到右结点的时候,根结点会被释放,这样记录的深度就不是真实的深度,而是比真实深度要少,那我们用后序遍历呢?后序的话左结点找不到,找右结点,并且根不会出栈,右结点再按照后序来遍历,如果右边也没有,也就是左右结点都没有,根结点就会出来,这样可以保证真实深度。我们可以设置一个变量来记录栈中能达到的最大深度即为二叉树的深度

    Java 实现

    // 结点
    class Node {
        int data;
        Node left = null;
        Node right = null;
    }
    
    // 二叉树
    public class BinaryTree {
        // 根结点
        private Node root;
        // 输入的数组
        private int[] arr_in;
        // 输出的数组
        private int[] arr_out;
        // 记录数组下标
        private static int index;
        
        // 初始化
        public BinaryTree(int[] arr) {
            root = new Node();
            this.arr_in = arr;
            arr_out = new int[arr.length];
            index = 0;
        }
    
    	// 二叉树深度(递归)
        public int getDepthRecursion(Node r) {
            if (r != null) {
                int m = getDepthRecursion(r.left);
                int n = getDepthRecursion(r.right);
                return (m>=n)?(m+1):(n+1);
            }
            else
                return 0;
        }
        
        // 二叉树深度(非递归)
        public int getDepth(Node r) {
            Stack stack = new Stack();
            Node node = r;
            Node top;
            int depth = 0;
            int maxDepth = 0;
            while(node || !stack.empty()) {
                if (node != null) {
                    stack.push(node);
                    depth++;
                    if (depth > maxDepth)
                        maxDepth = depth;
                    node = node.left;
                }
                else {
                    if (stack.peek().right && stack.peek().right != top)
                        node = stack.peek().right();
                    else {
                        top = stack.pop();
                        depth--;
                        node = null;
                    }
                }
            }
            return maxDepth;
        }
    
    展开全文
  • 二叉树的结构: typedef struct BTNode { ElemType data; struct BTNode *lchild, *rchild...这个递归算法二叉树深度其实和遍历二叉树的后序遍历算法差不多。 int BTNodeDepth(BTNode *b) { int lchildD...

    二叉树的结构:

    typedef struct BTNode 
    {
        ElemType data;
        struct BTNode *lchild, *rchild;
    } BTNode;
    

    递归算法求二叉树的深度depth:

    这个递归算法求二叉树的深度其实和遍历二叉树的后序遍历算法差不多。

    int BTNodeDepth(BTNode *b)
    {
        int lchildDepth, rchildDepth;
        if (b == NULL) return 0;
        else {
            lchildDepth = BTNodeDepth(b->lchild);//求左子树的高度为lchildDepth
            rchildDepth = BTNodeDepth(b->rchild);//求右子树的高度为rchildDepth
            return (lchildDepht > rchildDepth) ? (lchildDepth + 1) : (rchildDepth + 1);//取大者
        }
    }

    非递归算法求二叉树的深度:

    其实非递归算法求二叉树的深度就是使用二叉树的层次遍历的算法。

    int BTNodeDepth(BTNode *b)
    {
        BTNode *p = NULL, queue[MaxSize];
        int front, rear;
        front = rear = -1;
        int level = 1;
        int last = front;
        while (front != rear) 
        {
            p = queue[++front];
            if (l->lchild)
                queue[rear++] = p->lchild;
            if (l->rchild)
                queue[rear++] = p->rchild;
            if (last == front) 
            {
                level++;
                last = rear;
            }
        }
        return level;
    }

     

    展开全文
  • // 返回最大深度递归算法 if(!bTree) return 0; return (search_btDepthRecursion(bTree->lchild)>search_btDepthRecursion(bTree->rchild)?search_btDepthRecursion(bTree->lchild):search_...
    //递归
    int search_btDepthRecursion(LINKBINTREE *bTree)
    {
    //	返回最大深度,递归算法 
    	if(!bTree)
    		return 0;
    	return (search_btDepthRecursion(bTree->lchild)>search_btDepthRecursion(bTree->rchild)?search_btDepthRecursion(bTree->lchild):search_btDepthRecursion(bTree->rchild))+1;
    }
    //非递归
    int search_btDepth(LINKBINTREE *bTree)
    {
    	if(bTree)
    	{
    		int front = 0,rear = 0,level,depth = 0;//利用队列容易实现
    		LINKBINTREE *p,*queue[MAXSIZE],*head = bTree;
    		rear = (rear+1)%MAXSIZE;
    		queue[rear] = bTree;//首节点先入队 
    		level = rear;
    		while(rear!=front)
    		{
    			front = (front+1)%MAXSIZE;
    			p = queue[front];//出队 
    			if(p->lchild){
    //				遍历左子树 
    				rear = (rear+1)%MAXSIZE;
    				queue[rear] = p->lchild;
    			} 
    			if(p->rchild){
    //				遍历右子树 
    				rear = (rear+1)%MAXSIZE;
    				queue[rear] = p->rchild;				
    			}
    			if(front==level)
    			{
    //				每遍历完一层就depth+1 
    				depth++;
    				level = rear;
    			}
    		}
    		return depth;
    	}else{
    		printf("bt empty!");
    		return;
    	}
    }
    
    展开全文
  • 二叉树深度递归

    2020-10-24 09:36:20
    二叉树深度递归算法源码 数据结构: typedef struct BINODE { TELEMETYPE data; struct BINODE *lchild,*rchild; }BiNode,*BiTtree; 递归函数 int GetTreeDeep(BiTtree T) //计算二叉树的深度 { if(T==NULL) ...

    二叉树求深度递归算法源码

    数据结构

    typedef struct BINODE

    {

       TELEMETYPE data;
    
       struct BINODE *lchild,*rchild;
    

    }BiNode,*BiTtree;

    递归函数

    int GetTreeDeep(BiTtree T) //计算二叉树的深度

    {

       if(T==NULL)
    
              return 0;
    
       else{
    
              int a = GetTreeDeep(T->lchild);
    
              int b = GetTreeDeep(T->rchild);
    
              return (a>b)?(a+1):(b+1);
    
       }
    

    }

    在这里插入图片描述

    如(a)图,假设给出创建了这个二叉树,使用如上给出的递归实现的经典算法,这个递归过程是怎样的呢?

    递归过程中GetTreeDeep这个函数被自身多次调用,让我们给它们标号:

    函数 返回值 做什么? 步骤

    GetTreeDeep ----》进入函数 ----》访问A 0

    int a = GetTreeDeep(T->lchild); 1 ----》访问B 1

    int a = GetTreeDeep(T->lchild); 0 ----》访问B的左空节点 2

    int b = GetTreeDeep(T->rchild); 0 ----》访问B的右空节点 3

    此时标号2,3函数完成,得到a=0,由步骤2,3得到步骤1函数的a值为1,再由步骤1得到步骤0对应的返回值为2,此时计算到树的高度为2,这只是根节点左部的子树高度,此时运行到刚开始进入函数内的第二个GetTreeDeep,所以接下来该访问右部子树:

    int b = GetTreeDeep(T->rchild); ------ 》访问C 4

    int a = GetTreeDeep(T->lchild); 2 ------》访问D 5

    int a = GetTreeDeep(T->lchild); 1 ------》访问F 6

    int a = GetTreeDeep(T->lchild); 0 ------》访问F的左空节点 7

    int b = GetTreeDeep(T->rchild); 0 ------》访问F的右空节点 8

    步骤7,8的返回值为0,由此得到步骤6的返回值为1,步骤4对应的返回值为2,接下来,运行到该访问C的右节点:

    int b = GetTreeDeep(T->rchild); ------》访问E 9

    int a = GetTreeDeep(T->lchild); 1 ------》访问G 10

    int a = GetTreeDeep(T->lchild); 0 ------》访问G的左空节点 11

    int b = GetTreeDeep(T->rchild); 0 ------》访问G的右空节点 12

    以此类推:可知步骤8的返回值为1,现在该访问E的右节点:

    int b = GetTreeDeep(T->rchild); 1 ------》访问H 13

    int a = GetTreeDeep(T->lchild); 0 ------》访问H的左空节点 14

    int b = GetTreeDeep(T->rchild); 0 ------》访问H的右空节点 15

    现在开始返回,比较各个节点的返回值孰大孰小

    1, 首先比较的是步骤13和步骤10的返回值,二者一样大,返回1+1,步骤9得返回值2

    2, 比较步骤9和5,二者同样为2,故步骤4的返回值为2+1,为3

    3, 比较步骤4和步骤1,前者为3,后者为1,取前者,所以最后返回3+1,得步骤0的返回值为4,,即为最终结果。

    展开全文
  • 二叉树深度递归算法 intdepth(BTreeroot)...{ intldepth,rdepth; if(!root) return0; else...{ ldepth=depth(root->lchild); rdepth=depth(root->rchild); if(ldepth>=rdepth)//取左右子树深度的...
  • 二叉树深度的递归和非递归算法

    千次阅读 2017-04-11 09:47:44
    递归算法public static<T> int heightOfBinaryTreeInRecursion(BinaryTreeNode<T> root){ // 求二叉树深度递归算法 int leftHeight,rightHeight; if(root == null) return 0; leftHeight = he
  • 二叉树的存储结构有顺序存储和链式存储两种存储方式,这里我们采用使用频率较高的链式存储方式(二叉链表)来存储二叉树. 下面给出二叉树结点的定义. struct BiTreeNode//二叉树结点定义 { BiTreeNode* LChild;//...
  • 1.求叶节点个数(包含于4.) 2.由已知中序、先序序列建树 3.求高度 4.求度为1/2/0的节点个数 5.交换二叉树左右孩子(镜面反射二叉树) 6.查找先序序列中第k个节点 7.根据先序、后序确定满二叉树 ...算法思想:
  • int TreeDepth(BiTree T) { int LDepth,RDepth; if(T == NULL) { return 0; } else { LDepth = TreeDepth(T->lchild); RDepth = TreeDepth(T->rchild); return (LDepth >...(LDepth + 1...
  • 有关二叉树递归算法

    千次阅读 2017-11-21 16:03:37
    二叉树可实现一下功能: 判断二叉树是否为完全二叉树 计算度为1的结点的个数 计算度为2的结点的个数 计算度为0(叶子结点)的结点的个数 统计二叉树的高度(默认根的高度为1) 统计二叉树的宽度 计算各结点中最大元素...
  • 例题:设二叉树的存储结构为二叉链表,编写有关二叉树递归算法 如有谬误或者不足还请批评指正! (1)统计二叉树中度为0、1、2的结点个数 int num_0 = 0, num_1 = 0, num_2 = 0; void CountNode(BiTree T) { if ...
  • 3、熟悉求二叉树深度递归算法的设计与实现。 实验内容 问题描述:已知二叉树t,分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度,并对二叉树分别进行中序遍历。 要求: 1、二叉树分别采用顺序或...
  • 如何通过递归求出一棵二叉树的最大深度,首先递归算法特别重要的一个部分就是结束条件,那么结束条件怎么定义呢?对于二叉树而言,递归就是不断递归二叉树的左右结点,那么结束条件自然就是当结点为null时 if (root ...
  • int depth_Non_recursive(bitree bt)//利用队列进行非递归算法 { queue<bitree> q; bitree p=bt; int level=0,len; if(!bt) return 0; q.push(p); while(!q.empty())//每次只有把在同一层的所有结点出队以后...
  • -二叉树深度与宽度的计算递归版本) #include<stdio.h> #include<stdlib.h> #include<math.h> #define MAXSIZE 10010 #define ElemType int typedef struct BTNode{ ElemType data; BTNode ...
  • 递归计算二叉树深度

    千次阅读 2018-07-23 21:20:56
    #include "stdio.h" #include "malloc.h" typedef struct BiTNode{  char data; /*结点的数据域*/  struct BiTNode *lchild , *rchild;.../*创建一棵二叉树*/ void CreatBiTree(BiTr...
  • int depth( const BiTree T ) {  if (NULL == T)  {  return 0;  }  int ldepth = depth(T.leftPtr);  int rdepth = depth(T.rightPtr);    return ((ldepth >rdepth)
  • 二叉树递归深度优先DFS算法

    千次阅读 2017-10-06 10:58:14
    二叉树可以递归遍历,实现简洁,易于理解。这里介绍二叉树的非递归的三种遍历,以下图二叉树为例讲解。 先前声明 #define ELEMENTTYPE char typedef struct node* pnode; typedef struct node* PBintree; ...
  • 给定一个二叉树,找出其最小深度(最小深度是从根节点到最近叶子节点的最短路径上的节点数量) 示例: 给定二叉树 [3,9,20,null,null,15,7], 7 / \ 9 6 / \ 15 8 它的最小深度为2. typedef struct TreeNode...
  • 算法题源力扣,如下: 给定一个二叉树,找出其最大深度二叉树深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7],...
  • /* 判断完全二叉树,依据定义:任何一个节点(除去叶子节点)有且仅有两个“孩子” */ #include #define MAX_TREE_DEGREE 10 typedef struct BTnode{//以二叉链表作为存储结构  char data;  struct BTnode* ...
  • 二叉树深度递归) 思想: 1.如果为空树,返回0; 2.如果不是空树 (1)递归计算左子树的深度,记为m (2)递归计算右子树的深度,记为n 若m>n, 返回m+1 否则返回n+1 int depth(BiTree T) { if(T == NULL) ...
  • //递归算法二叉树深度 int CaculateTreeDepth1(BinaryTreeNode<T>* treeNode) { if (treeNode == NULL){ return 0; } int depth = 0; int leftDepth = CaculateTreeDepth1(treeNode->...
  • 1.实验目的 熟练掌握二叉树的二叉链表存储结构的C语言实现。掌握二叉树的基本操作-前序、中序、后序遍历二叉树的三种方法。了解非递归遍历过程中“栈”的作用和状态,而且能...(4)编写求二叉树深度递归算法。 ...
  • 二叉树深度的非递归算法

    千次阅读 2012-11-26 11:57:22
    //统计单分支的深度 p = p->lchild; } else{ -- top; p = nodePointer[top]; p = p->rchild; if(p == NULL) { //单分支结束 if(depth > temp ) temp = depth; -- depth; } }//else }//while return ...
  • 编写递归算法计算二叉树中叶子结点的数目
  • 二叉树深度算法

    万次阅读 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
收藏数 37,519
精华内容 15,007
关键字:

计算二叉树深度的递归算法