精华内容
下载资源
问答
  • 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;
    }
    
    
    展开全文
  • 二叉树的结构: 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;
    }

     

    展开全文
  • 主要介绍了C++基于递归和非递归算法求二叉树镜像的方法,针对二叉树遍历结合实例形式分析了递归与非递归算法的实现与使用技巧,需要的朋友可以参考下
  • 5·假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 LeetCode104. 二叉树的最大深度 思路:层次遍历,看一共有多少层 int maxDepth(TreeNode* root) { int d = 0; if(root){ queue<...

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

    LeetCode104. 二叉树的最大深度

    思路:层次遍历,看一共有多少层

    int maxDepth(TreeNode* root) {
            int d = 0;
            if(root){
                queue<TreeNode *> q;
                q.push(root);
                while(!q.empty()){
                    d++;
                    int n = q.size();
                    while(n--){
                        TreeNode *p = q.front();
                        q.pop();
                        if(p->left){
                            q.push(p->left);
                        }
                        if(p->right){
                            q.push(p->right);
                        }
                    }
                }
            }
            return d;
        }

     

    展开全文
  • //使用非递归算法实现求二叉树高度 //我们可以采用层序遍历的方式(使用顺序存储结构),设置一个last指针指向每层的最后一个节点指针,当出队时比较出队指针和last指针,若相同那么level+1 int Hight(BiTree T){ ...

    非递归(借助层序遍历队列)

    //使用非递归算法实现求二叉树的高度
    //我们可以采用层序遍历的方式(使用顺序存储结构),设置一个last指针指向每层的最后一个节点指针,当出队时比较出队指针和last指针,若相同那么level+1
    int Hight(BiTree T){
    	BiTree p = T;
    	BiTree Queue[MAXSIZE];
    	int front = -1, rear = -1;
    	int level = 0, last = 0;
    	Queue[++rear] = p//根节点入队
    	while(front<rear){
    		Queue[++front] = p;//出队
    		if(p->left!=NULL){
    			Queue[++rear] = p->left;
    		}
    		if(p->right!=NULL){
    			Queue[++rear] = p->right;
    		}
    		if(front==last){
    			level++;
    			last = rear;
    		}
    	}
    	return level;
    }

    递归实现

    //递归实现,根据树的高度等于max(h左,h右)+1
    int Hight2(BiTree T){
    	int h1 = 0, h2 = 0;
    	BiTree p = T;
    	if(p == NULL){
    		return 0;
    	}
    	else{
    		h1 = Hight2(p->left);
    		h2 = Hight2(p->right);
    		return (h1>h2?h1:h2)+1;
    	}
    }

     

    展开全文
  • 递归算法求二叉树的深度

    千次阅读 2018-11-29 22:19:55
    原理: 1.采用层次遍历的方法, 2.设置变量level记录当前...并让last指向下一层最右结点,至少遍历完成.level的值即为二叉树高度 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef 1000...
  • 假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求二叉树 bt 中所有叶子结点值之和 //假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求 //二叉树 bt 中所有叶子...
  • 递归算法计算二叉树中叶子节点的数目
  • 思路:用到非递归的思想,毫无疑问就是使用 树的层次遍历方法来做 采用层次遍历算法,设置变量level记录当前的节点所在存数。设置变量level指向当前节点...level就是二叉树高度 int BTdepth(Bitree T) {  if(!T)
  • 假设二叉树采用二叉链存储结构存放,结点值为 int 类型,设计一个递归算法求二叉树 bt 中所有结点值大于等于 k 的结点个数 #include "Btree.cpp" #include <bits/stdc++.h> int Nodenum(BTNode *bt,int k...
  • 递归求二叉树高度

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

    千次阅读 2018-09-22 12:34:55
    1.方法思路:用深搜和后序遍历结合,遍历所有节点,记录最大高度。时间为O(n),空间为O(max)。(自创) 代码如下(未测试): 1 2 3 4 5 6 7 8 9 10 11 12 ...
  • 有测试结果 (一) 从键盘输入二叉树的扩展先序遍历序列,建立二叉树的二叉链表存储结构; (二) 分别用递归和非递归算法实现二叉树的三种遍历;
  • PAGE 13 . 范文. 数据结构与算法实验报告三 二叉树的操作与应用 实验目的 熟悉...分别用递归和非递归算法实现二叉树的三种遍历 模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,
  • int height(BitNode *t){ if(t==null) return 0; else return 1+Max{height(t->lchild),height(t->rchild)}; } ...非递归先序遍历二叉树...非递归后序遍历二叉树...
  • 递归算法复制二叉树

    千次阅读 多人点赞 2019-04-16 20:58:27
    以想到关于二叉树算法问题,我觉得我们就应该去思考用递归的思想去试一下。所以经过思考终于写出了最简洁的代码。 二叉树的数据类型 typedef struct CSNode { char data; struct CSNode *LeftTree; ...
  • #数据结构 二叉树递归算法返回二叉树高度
  • 求二叉树高度递归算法中递归过程理解

    千次阅读 多人点赞 2019-07-04 12:08:16
    首先你就当height可以出某个节点的高度 从根节点开始,怎么表示这棵树的高度?根节点一层,左右子树,谁层数多,当然加上谁的啦 所以 return 1 + max(height(llink),height(rlink)); 然后对llink或者rlink...
  • 解题思路就是遇见空节点返回0,其余的时候返回左右子树中高度的最大值,将这个最大值+1就是该树的高度递归求解就可得出结果。 代码如下: public int TreeHigh...//若二叉树高度不为空,出左右子树的高度 .
  • 最简单的递归算法实现二叉树的遍历! //二叉树的先序遍历算法 void preorder(Btnode *p) { if(p!=null) { visit(p); preorder(p-&gt;lchild); preorder(p-&gt;rchild); } } //二叉树的中序遍历 ...
  • /************************ ...date:2017.12.24 非递归算法实现二叉树前、中、后序遍历 ************************/ #include<iostream> using namespace std; #define maxsize 100 typedef...
  • 使用递归算法求树的高度与最长路径(laihaitao
  • 用模板类 构造二叉树,并进行中序非递归遍历。
  • 二叉树的存储结构有顺序存储和链式存储两种存储方式,这里我们采用使用频率较高的链式存储方式(二叉链表)来存储二叉树. 下面给出二叉树结点的定义. struct BiTreeNode//二叉树结点定义 { BiTreeNode* LChild;//...
  • 计一个递归算法释放二叉树bt中的所有结点 对应的递归模型如下: f(BT)=不做任何事情 当BT=NULL时 f(BT)=f(BT->lchild); f(BT)=f(BT->rchild) 其他情况 #include <iostream> using namespace std; ...
  • 编写递归算法,将二叉树中所有节点的左右子树相互交换。 Status swap(BiTree T) { if(T){ BiTree tmp=T->lchild; T->lchild=T->rchild; T->rchild=tmp; if(T->lchild){ swap(...
  • 设计一个递归算法二叉树BT复制产生另一棵二叉树BT1(假设二叉树采用二叉链存储结构) 源代码如下: #include <iostream> using namespace std; //二叉树的结构 typedef struct BTNode { char data; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,081
精华内容 40,832
关键字:

递归算法求二叉树高度