精华内容
下载资源
问答
  • 假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 参数: 辅助队 q(存储节点);1对位标记参数L(用来记录当前一层队尾所在位置);指针P(用来指向出队元素);记录高度参数 dept(记录当前高度...

    题目:

    假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。

    参数:

    辅助队 q(存储节点);1对位标记参数L(用来记录当前一层队尾所在位置);指针P(用来指向出队元素);记录高度参数 dept(记录当前高度);

    步骤:

    1. 参数初始化 L=0,deot=0;
    2. 将结点放入队列q中,
    3. 判断当前结点是否有孩子结点,有则将孩子结点放入队列q中
    4. 判断L是否等于队头指针,若等于则dept+1
    5. 判断队头指针是否小于队尾指针,若小于则继续进行循环,若不小于则循环结束返回当前dept值;

    代码实现:

    #include <iostream>
    using namespace std;
    
    typedef struct TreeNode{
        char data;
        struct TreeNode *lchrld,*rchild;
        int tag;
    }TreeNode,*Tree;
    
    //构建树
    void creatTree(Tree &t){
        char ch;
        ch = getchar();
        if(ch=='#') t=NULL;
        else{
            t = (TreeNode *)malloc(sizeof(TreeNode));
            t->data = ch;
            t->tag=0;
            t->lchrld=NULL;
            t->rchild = NULL;
            creatTree(t->lchrld);
            creatTree(t->rchild);
        }
    
    }
    int dept(Tree t){
    
        if(!t) return 0;
        TreeNode *q[10];
        int f=-1,r=-1;
        int ans=0,L=0;
        TreeNode *p;
        q[++r] = t;
        while (f<r)
        {
            p=q[++f];
            if (p->lchrld) q[++r] = p->lchrld;
            if(p->rchild) q[++r] = p->rchild;
            if(L==f){
                ans++;
                L=r;
            }
            
        }
        return ans;
        
    }
    int main(){
        Tree t;
        creatTree(t);
        cout<<dept(t);
    
        return 0;
    }
    
    
    
    
    
    

    测试用例:输入样式 421##3##5##

    image.png

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

    思路:非递归则需要利用层序遍历思想,记录层数。每从队列中出满一队节点,则高度+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;
    }
    
    展开全文
  • Question:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 Analysis: 1.用层次遍历来获得二叉树高度; 2.对二叉树进行层次遍历,需要借助队列; 3.每次遍历到该层的最右边的结点时,level...

    Question:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度。

    Analysis:

    1.用层次遍历来获得二叉树的高度;
    2.对二叉树进行层次遍历,需要借助队列;
    3.每次遍历到该层的最右边的结点时,level+1;
    4.该算法的关键时,如何知道当前的结点是不是该层最后一个结点(last ==rear);

    Code:

    //二叉链表的结构
    typedef struct BiTNode{
        ElemType data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //层次遍历二叉树
    int GetBiTreeHeigth(BiTree T){
        if(T==NULL) retrun 0;  //空树,高度为0;
        
        InitQueue Q[MaxSize];  //初始化一个空队列;
        int front =-1,rear=-1;
        int last=0;
        int level =0;
        BiTree P;
        
        //EnQueue(Q,T);  //将当前结点入队;
        Q[++rear] = T;
        
        while(front <rear){
            P = Q[++front]; //出队,DeQueue(Q,Q.front);
            
            //访问当前结点visit(T);
            if(P->lchild){
                Q[++rear] = P->lchild; //EnQueue(Q,T->lchild);
            }
            if(P->rchild){
                Q[++rear] = P->rchild; //EnQueue(Q,T->rchild);
            }
            
            if(front==last){//当前层最后结点;
                level++;
                last=rear;
            }
        }
        
        return level;
    }
    
    
    展开全文
  •  假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 算法思想  采用层次遍历的算法,设置变量level来记录当前结点所在的层数,设置变量last指向当前层的最右边的结点,每次层级遍历出队时与...

    题目描述

     假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度。

    算法思想

     采用层次遍历的算法,设置变量level来记录当前结点所在的层数,设置变量last指向当前层的最右边的结点,每次层级遍历出队时与last指针比较,如果相等,则层数加1,并让last指向下一层的最右边的结点,直到遍历完成。那么最后的level的值即为二叉树的高度。


    实现代码

    实现代码:

     非递归算法:

    int Depth(BNode *root){
        int level = 0; //level为层数
        BNode *last = root;//last为下一层的最右结点
        if(root == NULL){ //树空,则高度为0
            return 0;
        }
        queue<BNode *> treenode; //申请一个队列
        treenode.push(root); //根结点入队
        while(!treenode.empty()){ //队不空时循环
            BNode *p = treenode.front(); //队首
            treenode.pop(); //根结点出队
            if(p->lchild != NULL){ //如果存在左子树,则左子树根结点入队
                treenode.push(p->lchild);
            }
            if(p->rchild != NULL){ //如果存在右子树,则右子树根结点入队
                treenode.push(p->rchild);
            }
            if(p == last){ //如果刚才出队的是该层最右结点
                level++; //层数加1
                last = treenode.back(); //last指向下层
            }
        }
        return level;
    }
    

     递归算法:

    int Depth2(BNode *root){
        if(root == NULL){ //空树,高度为0
            return 0;
        }
        int left = Depth2(root->lchild); //左子树高度
        int right = Depth2(root->rchild); //右子树高度
        return (left>right? left+1 : right+1); //树的高度为最大子树的高度加上根结点
    }
    

    完整代码及实例

    完整代码:

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct BNode{
        char data;
        struct BNode *lchild;
        struct BNode *rchild;
    }BNode;
    
    const int N = 100;
    char str[N]; //存储先序遍历序列
    int i; //标记处理到哪一个字符了
    BNode *BulidTree(){
        if(str[i] == '#'){
            i++; //处理下一个字符
            return NULL;
        }else{
            //新建一个结点
            BNode *p = (BNode *)malloc(sizeof(BNode));
            p->data = str[i];
            p->lchild = NULL;
            p->rchild = NULL;
            i++;
            p->lchild = BulidTree();
            p->rchild = BulidTree();
            return p;
        }
    }
    
    //非递归算法
    int Depth(BNode *root){
        int level = 0; //level为层数
        BNode *last = root;//last为下一层的最右结点
        if(root == NULL){ //树空,则高度为0
            return 0;
        }
        queue<BNode *> treenode; //申请一个队列
        treenode.push(root); //根结点入队
        while(!treenode.empty()){ //队不空时循环
            BNode *p = treenode.front(); //队首
            treenode.pop(); //根结点出队
            if(p->lchild != NULL){ //如果存在左子树,则左子树根结点入队
                treenode.push(p->lchild);
            }
            if(p->rchild != NULL){ //如果存在右子树,则右子树根结点入队
                treenode.push(p->rchild);
            }
            if(p == last){ //如果刚才出队的是该层最右结点
                level++; //层数加1
                last = treenode.back(); //last指向下层
            }
        }
        return level;
    }
    
    //递归算法
    // int Depth2(BNode *root){
    //     if(root == NULL){ //空树,高度为0
    //         return 0;
    //     }
    //     int left = Depth2(root->lchild); //左子树高度
    //     int right = Depth2(root->rchild); //右子树高度
    //     return (left>right? left+1 : right+1); //树的高度为最大子树的高度加上根结点
    // }
    
    int main(){
        scanf("%s",str);
        i = 0;
        BNode *root = BulidTree();
        int level = Depth(root);
        printf("%d\n",level);
        return 0;
    }
    

    运行结果:
    在这里插入图片描述

    实例中的二叉树为:
    在这里插入图片描述

    展开全文
  • 受后续遍历二叉树思想的启发,想到可以利用后续遍历的方法求二叉树的深度,在每一次输出的地方替换成算栈S的大小,遍历结束后最大的栈S长度即是栈的深度。 算法的执行步骤如下: (1)当
  • 二叉树的结构: typedef struct BTNode { ElemType data; struct BTNode *lchild, *rchild...这个递归算法求二叉树的深度其实和遍历二叉树的后序遍历算法差不多。 int BTNodeDepth(BTNode *b) { int lchildD...
  • 5·假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 LeetCode104. 二叉树的最大深度 思路:层次遍历,看一共有多少层 int maxDepth(TreeNode* root) { int d = 0; if(root){ queue<...
  • 算法思想: 采用层次遍历的算法思想,设置变量level 来记录当前结点所在的层数,设置last指向当前层数的最右结点,每次层次遍历出...非递归算法: int Btdepth(BiTree T) { if(!T){ return 0; //如果树为空则返回0 }
  • 算法思想: A:front=rear=0,last=1 A出队后[B(1),C(2)],front=1=last,level++,last更新为2 等front再次等于last的时候,第二层的结点就遍历完了,level再次++ void THeigh(TNode* p) { Queue Q; InitQueue(Q); ...
  • 算法思路也适用于 (1)每层的结点个数 (2)树的最大宽度 (3)节点位于某一层 int height(BiTree T){ if(T==null) return 0; int front=-1, rear=-1;//front 出队指针 rear 入队指针 int last = 0, level=0;/....
  • 非递归求二叉树高度

    2021-03-26 10:28:15
    题目:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度 分析: 若要采用非递归的方式来求得二叉树高度,我们采用层次遍历是最合适的,因为这一层一层的不就很好数吗哈哈。具体实现: 这里...
  • Hello I'm trying to write a non recursive method for getting the size of a node since recursion in Java is expensive. This would include the number of child nodes + 1 (itself). I've converted an C imp...
  • 非递归算法求二叉树的深度

    千次阅读 2018-11-29 22:19:55
    原理: 1.采用层次遍历的方法, 2.设置变量level记录当前...并让last指向下一层最右结点,至少遍历完成.level的值即为二叉树高度 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef 1000...
  • //使用非递归算法实现求二叉树高度 //我们可以采用层序遍历的方式(使用顺序存储结构),设置一个last指针指向每层的最后一个节点指针,当出队时比较出队指针和last指针,若相同那么level+1 int Hight(BiTree T){ ...
  • 二叉树的高是树比较重要的一个概念,指的是树中结点的最大层数本次算法通过非递归算法来求得树的高度,借用栈来实现树中结点的存储。 学英语真的很重要,所以文中的注释还有输出以后会尽量用英语写,文中出现的英语...
  • 利用层次遍历非递归求二叉树高度

    万次阅读 多人点赞 2016-09-30 17:47:42
    利用层次遍历非递归求二叉树高度主要的思想是:一层一层地出队列 — 在我们每次访问完一层时,这时队列中存储的刚好是下一层的所有元素。所以在下一次循环开始时,首先记录该层的元素个数,一次性访问完这一层的所有...
  • //任务:用非递归算法计算二叉树高度 //算法思想:使用层次遍历,利用队列指针,设置一个专门的指针last专门指向一层元素的最后一个元素 //将一层中最后一个元素之前的元素依次出队,并将每个元素的孩子结点入队,...
  • 笔记:非递归算法二叉树高度

    千次阅读 2018-09-22 12:34:55
    1.方法思路:用深搜和后序遍历结合,遍历所有节点,记录最大高度。时间为O(n),空间为O(max)。(自创) 代码如下(未测试): 1 2 3 4 5 6 7 8 9 10 11 12 ...
  • 思路:用到非递归的思想,毫无疑问就是使用 树的层次遍历方法来做 采用层次遍历算法,设置变量level记录当前的节点所在存数。设置变量level指向当前节点的最右边,每次遍历之后就和level进行比较,若二者相等,那么...
  • 递归计算二叉树高度Previously I wrote about an algorithm for finding out the height of a binary tree using iteration. Though that method gets the job done (in 7 steps no less), the same can be ...
  • 分别用递归和非递归先序后序中序创建二叉树、层序创建二叉树求二叉树高度、输出叶子节点 #include <stdio.h> #include <stdlib.h> #include<string.h> #define MAXSIZE 100 typedef struct ...
  • 递归与非递归求二叉树深度

    千次阅读 2016-08-26 11:47:43
    分别用递归与非递归算法求二叉树深度。 分析 方法一: 递归方法大家都很熟悉,如何用非递归求解呢? 我们知道二叉树有层序遍历,利用层序遍历的过程,记录当前层数,那么遍历结束后也就求得二叉树的层数...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,842
精华内容 6,336
关键字:

非递归算法求二叉树的高度