精华内容
下载资源
问答
  • 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;
    }
    
    
    展开全文
  • 一棵二叉树T的高度 int bt_Height(BiTNode *T) { if(T==NULL) return 0; else if(T->lchild==NULL&&t->rchild==NULL) return 1; else retrun 1+max(bt_Height(T->lchild),bt-Height(T-&...

    C语言数据结构二叉树

    求一棵二叉树T的高度

    int bt_Height(BiTNode *T)
    {
       if(T==NULL)
          return 0;
       else
          if(T->lchild==NULL&&t->rchild==NULL)
             return 1;
          else
              retrun 1+max(bt_Height(T->lchild),bt-Height(T->rchild));
    }
    
    
    展开全文
  •  假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度算法思想  采用层次遍历的算法,设置变量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;
    }
    

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

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

    展开全文
  • 思路:用到非递归的思想,毫无疑问就是使用 树的层次遍历方法来做 采用层次遍历算法,设置变量level记录当前的节点所在存数。设置变量level指向当前节点...level就是二叉树高度 int BTdepth(Bitree T) {  if(!T)

    思路:用到非递归的思想,毫无疑问就是使用 树的层次遍历方法来做

    采用层次遍历算法,设置变量level记录当前的节点所在存数。设置变量level指向当前节点的最右边,每次遍历之后就和level进行比较,若二者相等,那么层数加1,并让level指向下一层的最右边节点,至少遍历完成。level就是二叉树高度

    int  BTdepth(Bitree T)

    {

       if(!T)          //树空,高度是0

    {

      return 0;}

    int front=-1, rear=-1;

    int last=0, level=0;  //last指向下一层的第一个节点位置

    Bitree  Q[maxsize];

    Q[++rear]=T;  //将根入队列

    Bitree p;

    while(front<rear)//队列不为空,则循环

    {

         p=Q[++front];//队列元素出队列。

    if(p->lchild)  Q[++rear]=p->lchild;//左孩子入队

    if(p->rchild)  Q[++rear]=p->rchild;//右孩子入队

    if(front==level)//处理该层的最右边节点

    {

        level++;//层数加1

    last=rear;//last指向下一层

    }

    }

    return level;

    }


    展开全文
  • 以二叉链表作存储结构,设计求二叉树高度算法
  • //使用非递归算法实现求二叉树高度 //我们可以采用层序遍历的方式(使用顺序存储结构),设置一个last指针指向每层的最后一个节点指针,当出队时比较出队指针和last指针,若相同那么level+1 int Hight(BiTree T){ ...
  • 5·假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 LeetCode104. 二叉树的最大深度 思路:层次遍历,看一共有多少层 int maxDepth(TreeNode* root) { int d = 0; if(root){ queue<...
  • 非递归求二叉树高度

    2021-03-26 10:28:15
    题目:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度 分析: 若要采用非递归的方式来求得二叉树高度,我们采用层次遍历是最合适的,因为这一层一层的不就很好数吗哈哈。具体实现: 这里...
  • 算法:求二叉树高度

    千次阅读 2018-12-20 20:30:23
    问题引入(树之高度) 输入描述 对于一个二叉树,输入的第一行表示节点的个数n(1 ≤ n ≤ 1000,节点的编号为0到n-1)组成,下面是n-1行,每行有两个整数,第...使用递归法树的高度 int getdeep_1(treeType...
  • 6-8 求二叉树高度 (20分) 本题要求给定二叉树的高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ...
  • 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. ...
  • 方法一:递归 因为递归是先遍历完每棵子树再输出,所以只需要比较哪棵子树最深并返回该子树的高度并加上根结点(1)即为该二叉树高度。 代码:
  • 经典算法学习——求二叉树高度

    万次阅读 2016-10-02 21:10:39
    树的高度也是如此。分别左右子树的高度,然后取较长的子树作为高度。代码上传至 https://github.com/chenyufeng1991/BinaryTreeHeight 。核心代码如下:int BinaryTreeHeight(Node *node) { int treeHeight = ...
  • 用层次遍历算法求二叉树高度 关键: 1、last指针何时指向下一层 代码1: int getBiTreeDepth(BTNode *t){ //1.创建队列 2.初始化工作=>根节点入队 BTNode *que[MAXSIZE]; int front=-1,rear=-1;//front...
  • #include #include #define DATATYPE char #define NULL '\0' typedef struct node { DATATYPE data; struct node *lchild,*rchild; }BTLINK;... printf("\n 二叉树高度是%d",treeh); return 0; }
  • 假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求二叉树 bt 中所有叶子结点值之和 //假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求 //二叉树 bt 中所有叶子...
  • 6-8 求二叉树高度

    千次阅读 2018-05-13 23:15:45
    本题要求给定二叉树高度。函数接口定义:int GetHeight( BinTree BT ); 其中BinTree结构定义如下:typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; ...
  • 二叉树高度计算算法思悟

    千次阅读 2018-04-09 00:15:55
    二叉树高度计算算法思悟 总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种; github系列源码 递归算法实现 递归算法依旧格式优美、逻辑清晰、实现简单,便于...
  • 假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求二叉树 bt 中所有结点值大于等于 k 的结点个数 #include "Btree.cpp" #include <bits/stdc++.h> int Nodenum(BTNode *bt,int k...
  • 算法求二叉树深度

    2020-05-29 21:32:37
    输入一棵二叉树该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 分析 用递归即可,递归计算左子树深度left,递归计算右子树深度right,选择两者中较...
  • 二叉树的详细讲解请戳这:懵逼树上懵逼果:学习...前序遍历的顺序为根-左-右,具体算法为:把根节点push到栈中循环检测栈是否为空,若不空,则取出栈顶元素,保存其值看其右子节点是否存在,若存在则push到栈中看其...
  • 假设二叉树采用二叉链表存储结构,试设计一个算法 求二叉树高度并给出指定结点的所在的层数(高度) */ # include <iostream> # include <stdlib.h> # include <stdio.h> using namespace std; ...
  • 求二叉树高度

    2018-06-02 13:59:01
    假设二叉树 T 采用二叉链表存储结构,设计一个算法,计算该二叉树高度。 其中二叉树的二叉链表表示定义如下: typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;...
  • int height(BitNode *t){ if(t==null) return 0; else return 1+Max{height(t->lchild),height(t->rchild)}; } ...非递归先序遍历二叉树...非递归后序遍历二叉树...
  • (1)编写计算整个二叉树高度算法。(2)编写计算二叉树最宽的算法。二叉树的最大宽度是指二叉树左右层中结点个数的最大值。 这是西北大学考研试题。 二叉树的高度递归定义为: 当二叉树为空时,其深度为0。当...
  • 6-8 求二叉树高度(20 分)本题要求给定二叉树的高度。输出样例(对于图中给出的树):4#include &lt;stdio.h&gt; typedef struct BTiNode { char data; struct BTiNode *left,*right; }BTiNode,*BiTree...
  • 用递归来求二叉树高度、宽度

    千次阅读 2019-09-22 15:50:19
    二叉树高度height = Math.max(height[left],height[right])+1; 即左右子树高度的最大值加1,即为树的高度,以此不断递归,最后出树的高度。 其实也用到了DFS的思想 public static int TreeDepth(TreeNode root) { ...
  • 二叉树算法设计

    2019-11-03 12:44:10
    设计算法求二叉树的结点个数。 void Count(BiNode *root) { if (root) { Count(root->lchild); number+ +; //number为数据成员 Count(root->rchild); } } 左子树中节点的数目+右子树中节点的数目+1 ...

空空如也

空空如也

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

设计算法求二叉树高度