精华内容
下载资源
问答
  • 以二叉链表作存储结构,设计求二叉树高度的算法
  • 一棵二叉树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));
    }
    
    
    展开全文
  • #include #include #define DATATYPE char #define NULL '\0' typedef struct node { DATATYPE data; struct node *lchild,*rchild; }BTLINK;... printf("\n 二叉树高度是%d",treeh); return 0; }
    #include <stdio.h>
    #include <stdlib.h>
    #define DATATYPE char
    #define NULL '\0'
    
    typedef struct node
    {
    	DATATYPE data;
    	struct node *lchild,*rchild;
    }BTLINK;
    BTLINK *creat()
    {
    	BTLINK *q;
    	BTLINK *s[30];
    	int j,i;
    	char x;
    	printf("i,x=");
    	scanf("%d,%c",&i,&x);
    	while(i!=0&&x!='$')
    	{
    		q=(BTLINK *)malloc(sizeof(BTLINK));
    		q->data=x;
    		q->rchild=NULL;
    		q->lchild=NULL;
    		s[i]=q;
    		if(i!=1)
    		{
    			j=i/2;
    			if(i%2==0)
    				s[j]->lchild=q;
    			else
    				s[j]->rchild=q;
    				
    		}
    		printf("i,x=");
    		scanf("%d,%c",&i,&x);
    		return s[1];  
    	}
    }
    
    int depthtree(BTLINK *bt)
    {
    	int dep,depl,depr;
    	if(bt=NULL)
    		dep=0;
    	else
    	{
    		depl=depthtree(bt->lchild);
    		depr=depthtree(bt->rchild);
    		if(depl>depr)
    			dep=depl+1;
    		else
    			dep=depr+1;
    	}
    	return dep;
    }
    
    int main(int argc, char *argv[]) 
    {
    	BTLINK *bt;
    	int treeh;
    	bt=creat();
    	treeh=depthtree(bt);
    	printf("\n 二叉树高度是%d",treeh);
    	return 0;
    }
    
    
    
    
    
    
    
    
    
    展开全文
  • 所以,递归,也是一种 典型的 用空间换时间 的算法。   5.如果root是空就返回0,如果非空就遍历子树。取最高子树,然后加1就得到了整棵树的高度。就这样递归下去的 6. 左子树的高度height(llink)...
    int GetHeight(AVLTree A)
    {
        int MaxH, HR, HL;
        if(A) {
            HL = GetHeight(A->Left);
            HR = GetHeight(A->Right);
            MaxH = (HL>HR)?HL:HR;
            return MaxH+1;
        }
        return 0;
    }

    1.递归函数关注以下几个因素
    ·退出条件
    ·参数有哪些
    ·返回值是什么
    ·局部变量有哪些
    ·全局变量有哪些
    ·何时输出
    ·会不会导致堆栈溢出

    2.

     

    3.理解递归的时候不能一直往深处考虑,那样不适合人类的思维,只需要思考最后该退出时要返回什么,一般的情况下该返回什么,写代码时明确了这两个即可

    4.

    int Hight(Node* root)
        {
            if ( !root )
                return 0;
            else
                return max(Hight(root->left_child),Hight (root->right_child)) + 1
        }

    !root , 也就是指针为空的时候返回 0;
    就是说,遇到空节点,返回 0 ;

    下一行: return max()+ 1 ;
    这个是关键点,返回每一个子节点的高度,
    括号内,是调用自身这个函数(返回节点树高度)

    整个函数的思想可以看做是分治:即把大问题分解成小问题,对于整体函数,不需要知道每一步的执行过程,只需要知道上一步的结果就可以。

    每个函数调用自身,判断出是否需要继续调用函数,还是直接返回最根部的值 0 。如果调用函数,即需要获取调用函数的返回值即可。

    如果想理解这个函数,提供一个逆向的思维方式,从叶子结点开始思考,也就是  !root 那一行,返回了 0 ,调用他的函数 作对比,取最高值(深度最深值),依次递增到根节点或所输最外层节点,最终返回最大深度。

    实现性原理:
    每次递归调用一次函数时,计算机都会新开辟出一段函数空间、存储空间,为当前新调用的函数提供存在的空间。  以这个函数的运行为例,系统最终会开辟一个类似树形连接的区域,然后再依次确定每个函数的返回值(从叶子结点开始)。

    所以,递归,也是一种 典型的 用空间换时间 的算法。

     

    5.如果root是空就返回0,如果非空就遍历子树。取最高子树,然后加1就得到了整棵树的高度。就这样递归下去的

    6.

    
    左子树的高度height(llink) 
    右子树的高度height(rlink) 
    这两个高度当然要取更大的数 对吧 
    加上自己的节点 1: 
          本次递归的p------> O(p) 
                          /  \ 
                         /    \ 
    height(llink)------>左子树  右子树 <----------height(rlink) 
    总的高度 为 1 + max(height(llink),height(rlink)); 
    

    7.

    
    public int height(BinaryTreeNode p) {  //p是一个二叉树根节点的引用
        if(p == null){
           System.out.println("高度为0")
           return 0;
         }else{
           return 1 + max(height(llink),height(rlink));  //这个LLINK 和RLINK分别是p的两个指针,指向左子树和右子树
         }
    }

    你可以这样理解:
    首先你就当height可以求出某个节点的高度
    从根节点开始,怎么表示这棵树的高度?根节点一层,左右子树,谁层数多,当然加上谁的啦
    所以 return 1 + max(height(llink),height(rlink));
    然后对llink或者rlink都是同样的理解
    最后什么时候返回?当然是节点为空的时候啦,因为一个叶子节点已经是最后一层,它的左右节点
    都是空的。

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

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

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

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

    展开全文
  • Question:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度。 Analysis: 1.用层次遍历来获得二叉树的高度; 2.对二叉树进行层次遍历,需要借助队列; 3.每次遍历到该层最右边结点时,level...
  • 算法:求二叉树的高度

    千次阅读 2018-12-20 20:30:23
    问题引入(树之高度) 输入描述 对于一个二叉树,输入第一行表示节点个数n(1 ≤ n ≤ 1000,节点编号为0到n-1)组成,下面是n-1行,每行有两个整数,第...使用递归法的高度 int getdeep_1(treeType...
  • 受后续遍历二叉树思想启发,想到可以利用后续遍历方法来求二叉树的深度,在每一次输出地方替换成算栈S大小,遍历结束后最大栈S长度即是栈深度。 算法的执行步骤如下: (1)当
  • 经典算法学习——求二叉树的高度

    万次阅读 2016-10-02 21:10:39
    二叉树是一种递归定义数据结构,我们对它做几乎所有操作都是递归的高度也是如此。分别左右子树的高度,然后取较长子树作为高度。代码上传至 https://github.com/chenyufeng1991/BinaryTreeHeight...
  •  假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 算法思想  采用层次遍历的算法,设置变量level来记录当前结点所在的层数,设置变量last指向当前层的最右边的结点,每次层级遍历出队时与...
  • 求二叉树的高度

    千次阅读 2017-07-26 19:43:26
    算法三:采用递归算法求二叉树的高度。 //法1:后序遍历,结点最大栈长即为树的高度 //法2:层次遍历,层次即为高度 //法3:递归算法求树高#include<iostream> #include<stack> #include
  • //使用非递归算法实现求二叉树的高度 //我们可以采用层序遍历方式(使用顺序存储结构),设置一个last指针指向每层最后一个节点指针,当出队时比较出队指针和last指针,若相同那么level+1 int Hight(BiTree T){ ...
  • 求二叉树宽度递归算法

    千次阅读 多人点赞 2019-07-05 08:07:06
    开辟一个数组count[二叉树高度],遍历每一个节点,然后根据当前节点所在层次i,则执行count[i]++; 最后遍历完出最大count即为二叉树宽度,代码很简单如下 int count[100]; int MAX=-1; void FindWidth(BitNode T...
  • // 求二叉树的高度函数 nullptr为0 然后累加 +1 return left-right // 结论都还是递归 当前状态 多加了一个递归求高度 双重递归 class Solution { public: //求二叉树的高度 int height(TreeNode * root) { if...
  • 设置变量记录队列长度与新入队元素数量,当队列长度与新入队元素数量相等时,表明队列中上一层节点已经全部出队,此时队列中节点全部为同一层节点。 int findTreeHight(BiTree T){ Queue que; //创建队列 ...
  • 6-8 求二叉树高度 (20分) 本题要求给定二叉树高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ...
  • 非递归求二叉树高度

    2021-03-26 10:28:15
    题目:假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度 分析: 若要采用非递归方式来求得二叉树的高度,我们采用层次遍历是最合适,因为这一层一层不就很好数吗哈哈。具体实现: 这里...
  • 6-8求二叉树高度 (递归与非递归) 本题要求给定二叉树高度。 函数接口定义: int GetHeight( BinTree BT ); 其中BinTree结构定义如下: typedef struct TNode *Position; typedef Position BinTree; struct ...
  • 根据给定二叉树,求二叉树的高度;求给定结点所有祖先。 要求:(1)根据性质5 建立二叉树二叉链表; (2)遍历算法必须采用非递归算法
  • 思路:用到非递归思想,毫无疑问就是使用 树层次遍历方法来做 采用层次遍历算法,设置变量level记录当前节点所在存数。设置变量level指向当前节点...level就是二叉树高度 int BTdepth(Bitree T) {  if(!T)
  • 6-8 求二叉树高度(20 分)本题要求给定二叉树高度。函数接口定义:int GetHeight( BinTree BT ); 其中BinTree结构定义如下:typedef struct TNode *Position; typedef Position BinTree; struct TNode{ Element...
  • 6.8 二叉树高度 int GetHeight(BinTree BT) { if (BT == NULL) return 0; int leftH = GetHeight(BT->Left); int rightH = GetHeight(BT->Right); if (leftH > rightH) r...
  • int Height(BTNode *T)//求二叉树高度 {  int L,R;  if(NULL == T)  return 0;  else  {  L=Height(T->lchild);  R=Height(T->rchild);  return L>R ? L+1 :R+1;  
  • 算法思想: 采用层次遍历的算法思想,设置变量level 来记录当前结点所在的层数,设置last指向当前层数的最右结点,每次层次遍历出队时与last指针比较,相等则层数加一,并让last指向下一层的最右结点。 每处理到这一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 408
精华内容 163
关键字:

求二叉树高度的算法