精华内容
下载资源
问答
  •  假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树高度。 算法思想  采用层次遍历的算法,设置变量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;
    }
    

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

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

    展开全文
  • 思路:非递归则需要利用层序遍历思想,记录层数。每从队列中出满一队节点,则高度+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;
    }
    
    展开全文
  • 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;
        }

     

    展开全文
  • #includestruct node{char info;struct node *llink, *rlink;};typedef struct node NODE;NODE *create(){ //构造二叉树char x;NODE *p;scanf("%c", &x);printf("%c", x); //打印出已输入的二叉树if...

    #includestruct node{

    char info;

    struct node *llink, *rlink;

    };

    typedef struct node NODE;

    NODE *create(){ //构造二叉树

    char x;

    NODE *p;

    scanf("%c", &x);

    printf("%c", x); //打印出已输入的二叉树

    if(x!='.'){

    p=(NODE *)malloc(sizeof(NODE));

    p->info=x;

    p->llink=create();

    p->rlink=create();

    }

    else p=NULL;

    return p;

    }

    int run(NODE *t){

    static int count=0;

    if(t){

    run(t->llink); //递归遍历左子树,直到叶子处

    run(t->rlink); //递归遍历右子树,直到叶子处

    if(t->llink ==NULL && t->rlink == NULL) {

    count++;

    }

    }

    return count;

    }

    main()

    { NODE *T;

    int left_number;

    printf("请输入一棵树:\n" );

    T=create();

    printf("\n");

    if(!T) printf("This is a empty binary tree.");

    else{

    left_number=run(T);

    printf("\n这棵树共有 %d 个子叶. \n", left_number);

    }

    printf("\n");}

    四、实验结果与分析

    (2)习题1:注意叶子结点是指该结点既没有左孩子又没有右孩子,采用递归算法就很容易计算出其数目。

    实验结果如图:

    五、实验心得及体会

    本次实验加深了我对树的各种遍历方法。尤其是先序遍历。在建立树的过程中更是采取了递归的方法。有的算法用递归表示要比用循环表示简洁精练[如二叉树的遍历],代码更简洁清晰,可读性更好有的算法递归能实现循环不一定能实现,递归的内部实现要消耗额外的空间和时间。所以说循环的效率更高。

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

    千次阅读 2018-11-29 22:19:55
    原理: 1.采用层次遍历的方法, 2.设置变量level记录当前...并让last指向下一层最右结点,至少遍历完成.level的值即为二叉树高度 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef 1000...
  • 题目:编写递归算法求二叉树中元素值为x的结点的深度 题目:编写递归算法求二叉树中以元素值为x的结点为根的子树的深度 //题目:编写递归算法求二叉树中元素值为x的结点的深度 //对应代码的GetDepth_OneValue...
  • #include   struct BiTree{    char data;    struct BiTree *lchild;    struct BiTree *rchild;   };   struct BiTree* CreatBiTree(){    char x;    struct BiTree* p;
  • 编写递归算法,计算二叉树中叶子结点的数目。熟悉树的各种表示方法和各种遍历方式,掌握有关算法的实现,了解树在计算机科学及其它工程技术中的应用学院名称 学生姓名 课程名称 数据结构专业班级 学号 实验题目 2 树...
  • 编写递归算法,计算二叉树中叶子结点的数目
  • 递归算法计算二叉树中叶子节点的数目
  • 编写递归算法,在二叉树位于先序序列中第k个位置的结点的值 //题目:编写递归算法,在二叉树位于先序序列中第k个位置的结点的值 //解决方法:递归函数的参数使用引用参数 #include<iostream> using ...
  • #include <stdio.h>#include <malloc.h> typedef struct BTNode { int data; struct BTNode *left, *right;...BTNode *creat_bt(){ //按前序建二叉树; BTNode *t;int x; printf("请输入...
  • #include <stdio.h> #include <malloc.h> typedef struct BTNode { int data; struct BTNode *left, *right;...BTNode *creat_bt(){ //按扩展前序建二叉树; BTNode *t;int x; scanf("%d...
  • 编写递归算法二叉树中先序序列中第k个位置的节点 #include&lt;stdio.h&gt;//freopen()的头文件 #include&lt;malloc.h&gt; #include&lt;iostream&gt; using namespace std; const ...
  • //编写递归算法求二叉树中叶子结点的个数 #include<stdio.h> #include<stdlib.h> #define MaxSize 1000 typedef struct BiTNode { char data; struct BiTNode* lchild; struct BiTNode* rchild...
  • 递归求二叉树高度 #include "BST.h" int max (int a ,int b) { if(a&gt;=b) return a; else return b; } int hight( BSTNode&lt;int,int *&gt; *root ) { if( root == NULL ) ...
  • 编写递归算法,计算二叉树中叶子结点的数目 //算法思想:后序遍历 先左右子树的叶子结点,再加上根结点的情况 #include<iostream> #include<stack> using namespace std; #define TElemType double ...
  • 编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的...
  • 求二叉树高度递归算法中递归过程理解

    千次阅读 多人点赞 2019-07-04 12:08:16
    首先你就当height可以出某个节点的高度 从根节点开始,怎么表示这棵树的高度?根节点一层,左右子树,谁层数多,当然加上谁的啦 所以 return 1 + max(height(llink),height(rlink)); 然后对llink或者rlink...
  • 编写递归算法,将二叉树的所有节点的左、右子树相互交换 //题目:利用递归交换二叉树每个结点的左右子树 //总结:使用先序递归/后序递归,不能使用中序递归 #include<iostream> #include<stack> using ...
  • 解题思路就是遇见空节点返回0,其余的时候返回左右子树中高度的最大值,将这个最大值+1就是该树的高度递归求解就可得出结果。 代码如下: public int TreeHigh...//若二叉树高度不为空,出左右子树的高度 .
  • 编写递归算法,将二叉树中所有节点的左右子树相互交换。 Status swap(BiTree T) { if(T){ BiTree tmp=T->lchild; T->lchild=T->rchild; T->rchild=tmp; if(T->lchild){ swap(...
  • 最简单的递归算法实现二叉树的遍历! //二叉树的先序遍历算法 void preorder(Btnode *p) { if(p!=null) { visit(p); preorder(p-&gt;lchild); preorder(p-&gt;rchild); } } //二叉树的中序遍历 ...
  • 题目:编写递归算法,在二叉树位于先序序列中第k个位置的结点的值。 描述:核心代码为Fink_K()函数块内容。 关键:Fink_K()函数的形参需要设置一个int型指针。 #include <stdio.h> #include <stdlib.h&...
  • 在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。递归算法的特点递归过程一般通过函数或子过程来实现。递归算法:在函数或子过程的内部,直接或者间接地调用自己的...
  • 计一个递归算法释放二叉树bt中的所有结点 对应的递归模型如下: f(BT)=不做任何事情 当BT=NULL时 f(BT)=f(BT->lchild); f(BT)=f(BT->rchild) 其他情况 #include <iostream> using namespace std; ...
  • 在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。递归算法的特点递归过程一般通过函数或子过程来实现。递归算法:在函数或子过程的内部,直接或者间接地调用自己的...

空空如也

空空如也

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

编写递归算法求二叉树的高度