精华内容
下载资源
问答
  • 方法一:递归 因为递归是先遍历完每棵子树再输出,所以只需要比较哪棵子树最深并返回该子树的高度并加上根结点(1)即为该二叉树高度。 代码:

    方法一:递归
    因为递归是先遍历完每棵子树再输出,所以只需要比较哪棵子树最深并返回该子树的高度并加上根结点(1)即为该二叉树的高度。

    代码:
    在这里插入图片描述

    方法二:层次遍历
    因为层次遍历是将每一层元素都输出后才遍历下一层,所以我们可以在遍历完每一层的最后一个结点后高度加一。
    如何判断是否为当前层的最后一个结点呢?可以用queue.size()来判断,当size(当前层元素个数),当size=0时即遍历完该层元素。
    代码:
    在这里插入图片描述

    展开全文
  • 二叉树高度计算算法思悟

    千次阅读 2018-04-09 00:15:55
    二叉树高度计算算法思悟 总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种; github系列源码 递归算法实现 递归算法依旧格式优美、逻辑清晰、实现简单,便于...

    二叉树高度计算算法思悟

    总体来说,现在掌握的二叉树高度计算算法共有递归算法、基于后序遍历的算法、基于层次遍历的算法三种;
    github系列源码

    1. 递归算法实现

      递归算法依旧格式优美、逻辑清晰、实现简单,便于理解,但是递归算法伴随着额外的系统开销,而这些额外的开销是可以避免的,既然有更好的实现,就不应安于现状~

      public int getHeight(){
          int height;
          int leftHeight=0;
          int rightHeight=0;
          if(leftTree!=null){
              leftHeight=leftTree.getHeight();//得到左子树高度
          }
          if(rightTree!=null){
              rightHeight=rightTree.getHeight();//得到右子树高度
          }
          height=(leftHeight>rightHeight?leftHeight:rightHeight)+1;//返回高度
          return height;
      }
    2. 基于后序遍历思想的实现

      从递归算法的实现来看,是不是很像二叉树后序遍历的实现代码:首先计算左子树高度(相当于后序遍历中首先访问左子树)然后计算右子树高度(然后访问右子树),最后返回树高(然后访问根结点);

      既然我们已经实现非递归的后序遍历算法,那么我们就可以照猫画虎啦~

      但是还有两点需要说明:

      第一:在计算过程中,我们通过栈的最大深度来反映从树的高度(为什么呢?),因为栈中保留着根结点到叶子结点(准确的说,是到所有结点的路径,自然也包括我们想要的叶子结点)的路径~而最长的路径自然反映树的高度~;

      第二:通过模拟中序遍历或者先序遍历可以达成目标吗?我觉得不可以~因为先序遍历时,访问某棵右子树时,其父节点已经弹出栈了,那么路径就不完整了,而中序遍历也是因为同样的原因,唯有后序遍历方可~(其实从递归算法的实现也可以理解,先序和中序遍历根本不像嘛);

      public int getHeight(){
          //通过后序遍历的思路计算树高
          int height=0;
          int currentHeight;
          //我们需要一个栈
          MyLinkedDeque<BinaryTreeNode<T>> stack=new MyLinkedDeque<>();
          BinaryTreeNode<T> currentNode=this,visited=null;//后序遍历所需要的辅助变量
          while(currentNode!=null||!stack.isEmpty()){
              while(currentNode!=null){
                  stack.addFirst(currentNode);
                  currentNode=currentNode.leftTree;
              }//常规操作,一直入栈,直到遇见null
              if(!stack.isEmpty()){
                  currentNode=stack.peekFirst();//注意,这里只是peek~
                  if(currentNode.rightTree!=null&&currentNode.rightTree!=visited){
                      currentNode=currentNode.rightTree;//进入右子树
                  }else {//访问
                      currentHeight=stack.size();//得到栈的深度(大小)
                      height=(height>currentHeight?height:currentHeight);//更新树的高度
                      stack.pollFirst();//功成身退;
                      visited=currentNode;
                      currentNode=null;//常规操作
                  }
              }
          }
          return height;//返回高度
      }
    3. 基于层次遍历思想的实现

      基于层次遍历,或者说树的宽度优先遍历思想设计的计算方法其核心为:每往下遍历一层,树的高度增加1;当遍历结束,自然可以得到树的高度;

      那么问题来了,怎样得到一棵树中某一层的结点?怎样判断遍历结束?怎样判断一个结点属于A层而不是A+1层?

      在方法2中,我们用的额外数据结构为栈,而这里,我们用到的是队列;所以我们访问一个结点时,就把它的子结点入队列,当访问完该结点以及该结点的兄弟结点时(也就是访问完一层结点),队列里自然保留了下一层要访问的结点;我们需要两个整型变量来帮助我们实现结点所属层次的判断:变量A用来记录正在访问的这一层还有多少结点尚未访问;变量B用来记录下一层结点的数目;一层访问完后,将变量B赋值给变量A即可;

      public int getHeight(){
          int height=0;
          int currentLevelNum=1;
          int nextLevelNum=0;
          MyLinkedDeque<BinaryTreeNode<T>> queue=new MyLinkedDeque<>();
          BinaryTreeNode<T> currentTree;
          queue.addLast(this);
          while(!queue.isEmpty()){
              while(currentLevelNum>0){
                  currentTree=queue.pollFirst();
                  if(currentTree.rightTree!=null){
                      queue.addLast(currentTree.rightTree);
                      nextLevelNum++;
                  }
                  if(currentTree.leftTree!=null){
                      queue.addLast(currentTree.leftTree);
                      nextLevelNum++;
                  }
                  currentLevelNum--;
              }//遍历完一层结点
              height++;
              currentLevelNum=nextLevelNum;
              nextLevelNum=0;//重置变量
          }
          return height;
      }
    展开全文
  • #数据结构 二叉树递归算法返回二叉树高度

    #数据结构 二叉树递归算法返回二叉树高度
    在这里插入图片描述

    展开全文
  • 求一棵二叉树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));
    }
    
    
    展开全文
  • 以二叉链表作存储结构,设计求二叉树高度算法
  • 2.非递归算法求解二叉树高度 3.递归算法求解二叉树高度 4.二叉树各个值不同,先序和中序遍历序列分别存于数组A[1..n],B[1....n]中, 算法建立该二叉树链表 5.二叉树用二叉链表形式存储,写一个判定二叉树是否是...
  • (4)求二叉树高度 。 (5)求二叉树的叶子个数。 (6)对于树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。 (8)借助队列实现二叉树的层次遍历。 (9)在主函数中设计一个简单的菜单,...
  • 二叉树的基本算法及遍历(递归)创建二叉树(前序遍历)A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))递归销毁二叉树查找值为x的结点(前序遍历)求某一结点的左右孩子求二叉树高度以括号表示法输出二叉树(前序遍历)...
  • 二叉树基本算法

    2011-10-31 20:08:05
    包括: 1、按层次序列建立二叉树 2、按先根序列建立二叉树 3、按先序和中序序列建立二叉树 ...13、求二叉树高度 14、按值查找节点并输出其孩子 15、交换二叉树的左右子树 16、二叉树的删除(递归实现) 0、退出系统
  • 编写创建二叉树算法

    千次阅读 2016-02-02 18:40:41
    ④、编写求二叉树高度算法; ⑤、编写输出二叉树的算法; ⑥、编写先序遍历递归算法; ⑦、编写主函数。 代码如下: #include #include #include #include #define MaxSize 50 //①: void CreateBTNode...
  • 二叉树基本算法锦集——带你定义一棵二叉树并完成先序中序后序的递归实现和非递归实现,计算高度和结点个数、深度,进行key的查找,插入左右子树等等……
  • 二叉树 最优二叉树 树 算法实现 源码 高度 结点 叶子 ...求二叉树高度算法的递归模型 求二叉树结点个数算法的递归模型 求二叉树叶子结点个数算法的递归模型 以括号表示法输出二叉树运算算法 以凹入法输出二叉树运算算法
  • 二叉树遍历算法

    2019-12-09 15:05:06
    试题描述:“遍历算法应用”的算法在计算机上调通(加上主函数) 程序的初始二叉树: #include <bits/stdc++.h> using namespace std; int count=0; typedef struct node *Tree; struct node { int element;...
  • 二叉树递归算法

    千次阅读 2018-05-04 17:18:04
    //二叉树,先序创建二叉树,然后使用递归完成各种操作 //对于遍历,传递的是每个根节点对应的左右子树根节点地址, //使用取地址符&amp;获取根节点地址之后进行操作,但又不希望修改 //此子树,所以使用const //...
  • 求解二叉树高度的递归算法

    千次阅读 2014-02-27 15:08:43
    二叉树高度就是1+max{height(root->light),height(root->right)},从而有了递归算法的求解思路。 int height(Betree *p) { if(p==NULL) hi=0;  else { if(p->lchild==NULL) lh=0; else lh=height(p->lchild);/...
  • 前言 本篇博文主要想要阐述清楚的是:平衡二叉树在插入和删除结点的过程中...任意一个结点左右子树的高度差绝对值不超过1,我们把左子树和右子树的高度差称为平衡因子,所以平衡因子的取值范围为 -1,0, 1. 平衡...
  • 二叉树基本概念
  • 二叉树-你必须要懂!(二叉树相关算法实现-iOS) ...这几天详细了解了下二叉树的相关算法,原因是看了唐boy的一篇博客(你会翻转二叉树吗?),还有一篇关于百度的校园招聘面试经历,深刻体会到二叉树
  • 出口③:递归完左右子树以后,得到左右子树的平衡因子,判断平衡因子是否都为1(即都平衡,都平衡则以当前节点为根的树都平衡),把当前树的高度保存在h变量中,结束这一层的递归算法。 入口①:递归左子树 入口②:
  • 所以,递归,也是一种 典型的 用空间换时间 的算法。   5.如果root是空就返回0,如果非空就遍历子树。取最高子树,然后加1就得到了整棵树的高度。就这样递归下去的 6. 左子树的高度height(llink)...
  • 主要介绍二叉树相关的代码实现,二叉树遍历算法的具体应用 先序遍历建立二叉链表 void CreateBitree(BiTNode *&T) { char ch; scanf (“%c”, &ch); if (ch==‘#’) T=NULL; else { T=(BiTree)malloc...
  • int height(BitNode *t){ if(t==null) return 0; else return 1+Max{height(t->lchild),height(t->rchild)}; } ...非递归先序遍历二叉树...非递归后序遍历二叉树...
  • 算法思路也适用于 (1)每层的结点个数 (2)树的最大宽度 (3)节点位于某一层 int height(BiTree T){ if(T==null) return 0; int front=-1, rear=-1;//front 出队指针 rear 入队指针 int last = 0, level=0;/....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 36,634
精华内容 14,653
关键字:

二叉树高度算法