-
2020-07-26 17:19:26
思路:设置level变量记录层数,last变量记录该层最右结点,在层次遍历出队时,让队列的front指针与last对比,相等证明该层遍历完了,last=rear,同时level+1,直至遍历完成,即队列为空,此时level即为二叉树的高度。完整代码如下:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MaxSize 100 struct tree { int data; struct tree* left; struct tree* right; }; typedef struct queue{ struct tree* numQ[MaxSize]; int front; int rear; }Queue; Queue Q; void initilize() { //初始化队列 Q.front = -1; Q.rear = -1; } struct tree* creatTree (struct tree* root) { int value; scanf("%d", &value); if (value == -1) return NULL; root = (struct tree*)malloc(sizeof(struct tree)); root->data = value; printf("请输入%d的左子树:", root->data); root->left = creatTree(root->left); printf("请输入%d的右子树:", root->data); root->right = creatTree(root->right); return root; } int main() { printf("请输入头节点:"); struct tree* root = creatTree(root); initilize(); //初始化队列 int level = 0,last = 0; Q.numQ[++Q.rear]=root;//根节点入队 struct tree *p; while(Q.front<Q.rear){ p=Q.numQ[++Q.front];//出队 if(p->left) Q.numQ[++Q.rear]=p->left; if(p->right) Q.numQ[++Q.rear]=p->right; if(Q.front==last){//该层遍历完毕 level++;last = Q.rear;//层数+1 } } printf("该树的高度为%d\n",level); return 0; }
更多相关内容 -
层次遍历求二叉树的高度(非递归)
2018-08-05 15:43:34所谓层次遍历,是将二叉树中的元素从根节点按照节点层数一层层的输出。 代码如下: int GetDepth(bitreenode *root) { int depth=0; bitreenode *p=root; queue<bitreenode*> q; q.push(p); //...来自大佬群主的第二题
所谓层次遍历,是将二叉树中的元素从根节点按照节点层数一层层的输出。
代码如下:
int GetDepth(bitreenode *root) { int depth=0; bitreenode *p=root; queue<bitreenode*> q; q.push(p); //根指针入队 while(!q.empty()) { depth++; //高度加一 int width=q.size(); //获取当前层次宽度 for(int i=0;i<width;i++) { p=q.front(); //获取队顶元素 q.pop(); //弹出队顶元素 if(p->leftchild!=NULL) //左孩子入队 q.push(p->leftchild); if(p->rightchild!=NULL) //右孩子入队 q.push(p->rightchild); } } cout<<depth<<endl; }
-
二叉树的前中后遍历、层次遍历、树高,叶子节点、由两种遍历求树
2021-10-18 17:58:04又前序遍历和中序遍历求树 Java代码拿去即可运行 package leetcode; public class TreeNode { private Integer value; private TreeNode left; private TreeNode right; public TreeNode() { } public...二叉树的前序遍历
二叉树的中序遍历
二叉树的后序遍历
二叉树的前层次序遍历
求叶子节点
求树高
又前序遍历和中序遍历求树
Java代码拿去即可运行
package leetcode; public class TreeNode { private Integer value; private TreeNode left; private TreeNode right; public TreeNode() { } public TreeNode(Integer value) { this.value=value; } public TreeNode(Integer value, TreeNode left, TreeNode right) { this.value = value; this.left = left; this.right = right; } public Integer getValue() { return value; } public void setValue(Integer value) { this.value = value; } public TreeNode getLeft() { return left; } public void setLeft(TreeNode left) { this.left = left; } public TreeNode getRight() { return right; } public void setRight(TreeNode right) { this.right = right; } }
package tree; import leetcode.TreeNode; import java.util.Arrays; import java.util.LinkedList; import java.util.Objects; public class Test { public static void main(String[] args) { // TreeNode treeNode1 = new TreeNode(1); // TreeNode treeNode2 = new TreeNode(2); // TreeNode treeNode3 = new TreeNode(3); // TreeNode treeNode4 = new TreeNode(4); // TreeNode treeNode5 = new TreeNode(5); // treeNode2.setLeft(treeNode4); // treeNode2.setRight(treeNode5); // treeNode1.setLeft(treeNode2); // treeNode1.setRight(treeNode3); // System.out.println(getHeight(treeNode1)); int[] a={1,2,4,5,3}; int[] b={4,2,5,1,3}; TreeNode treeNode1=buildTree(a,b); LevelOrderTraversal(treeNode1); } /*************先序遍历****************/ static void PreOrderTraversal(TreeNode treeNode) { if (treeNode != null) { System.out.println(treeNode.getValue()); // 打印根 PreOrderTraversal(treeNode.getLeft()); // 进入左子树 PreOrderTraversal(treeNode.getRight()); // 进入右子树 } } /*************中序遍历****************/ static void midOrderTraversal(TreeNode treeNode) { if (treeNode != null) { midOrderTraversal(treeNode.getLeft()); // 进入左子树 System.out.println(treeNode.getValue()); // 打印根 midOrderTraversal(treeNode.getRight()); // 进入右子树 } } /*************后序遍历****************/ static void lastOrderTraversal(TreeNode treeNode) { if (treeNode != null) { lastOrderTraversal(treeNode.getLeft()); // 进入左子树 lastOrderTraversal(treeNode.getRight()); // 进入右子树 System.out.println(treeNode.getValue()); // 打印根 } } /**********层次遍历*************/ public static void LevelOrderTraversal(TreeNode treeNode) { LinkedList<TreeNode> q = new LinkedList<>(); // 创建队列 TreeNode node; if (Objects.isNull(treeNode)) return; q.push(treeNode); // treeNode 入队 while (!q.isEmpty()) { node = q.getFirst(); // 访问队首元素 q.pop(); // 出队 System.out.println(node.getValue().toString()); if (node.getLeft() != null) {// 如果存在左儿子结点 q.addLast(node.getLeft()); // 入队 } if (node.getRight() != null) { q.addLast(node.getRight()); } } } /***************输出叶子结点********************/ static void findLeaves(TreeNode treeNode) { if (treeNode != null) { if (Objects.isNull(treeNode.getLeft()) && Objects.isNull(treeNode.getRight())) { System.out.println(treeNode.getValue()); // 打印根 } findLeaves(treeNode.getLeft()); // 进入左子树 findLeaves(treeNode.getRight()); // 进入右子树 } } /********************树的高度*****************/ static int getHeight(TreeNode treeNode) { int hl, hr, maxh; if (treeNode != null) { hl = getHeight(treeNode.getLeft()); // 求左子树高度 hr = getHeight(treeNode.getRight()); // 求右子树高度 maxh = (hl > hr) ? hl : hr; return maxh + 1; // 当前结点高度为左右子树最大的高度+1 } else return 0; } /******************前序中序遍历序列构造二叉树**************************/ public static TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length==0)return null; TreeNode root = new TreeNode(preorder[0]); int num=0; for(int i =0; i<inorder.length; i++){ if(inorder[i]==root.getValue()){ num=i; break; } } int[] preLeft = Arrays.copyOfRange(preorder,1,num+1); int[] preRight = Arrays.copyOfRange(preorder,num+1,preorder.length); int[] inoLeft = Arrays.copyOfRange(inorder,0,num); int[] inoRight = Arrays.copyOfRange(inorder,num+1,inorder.length); root.setLeft(buildTree(preLeft,inoLeft)); root.setRight(buildTree(preRight,inoRight)); return root; } }
-
递归和非递归方法(层次遍历)计算二叉树高度
2021-08-12 17:52:02递归和非递归方法(层次遍历)计算二叉树高度 1.递归方式计算二叉树高度 int Btdepth(BiTree T){ if(!T) return 0; ldep=Btdepth(T->lchild); rdep=Btdepth(T->rchild); return ldep>rdep? ldep+1:rdep...递归和非递归方法(层次遍历)计算二叉树高度
1.递归方式计算二叉树高度
int Btdepth(BiTree T){ if(!T) return 0; ldep=Btdepth(T->lchild); rdep=Btdepth(T->rchild); return ldep>rdep? ldep+1:rdep+1; }
2.层次遍历方法计算二叉树高度:
算法思想:last指向每层最右结点,level为高度。从头节点开始,
边入队,然后再出队进行层次遍历,并将孩子结点入队,此时rear
指向下一层最右结点。而我们在出队遍历时,遍历完当前层front
指向的也是最右结点。所以在代码中,front==last作为判断遍历完
当前层的条件。rear指向的是下层的最右结点,故将last赋值为rear。int Btdepth(BiTree T){ if(!T) return 0; int last=0, level=0; int front=-1, rear=-1; BiTree Q[MaxSize];//设置队列Q,元素为二叉树的结点指针,且容量足够 Q[++rear]=T;//根节点入队 BiTree p; while(front<rear){//队不空则循环 p=Q[++front];//队列元素出队,即正在访问的结点 if(p->lchild) Q[++rear]=p->lchild;//左孩子入队 if(p->rchild) Q[++rear]=r->rchild;//有孩子入队 if(front==last){//处理该层的最右结点 level++;//层数加1 last=rear;//last指向下层 } } }
-
层序遍历求二叉树(链式存储结构)的高度
2019-10-09 16:59:25int Btdepth(Bitreee T){ if(!T) return 0; //如果是空树,则高度为1; int front =-1,rear=-1; //定义顺序队列,队列元素是二叉树结点指针,用于层序访问链式二叉树; BiTree Q[MaxSize]; ... -
【数据结构】 顺序、链式存储结构的森林递归遍历、层次遍历求高度
2020-05-23 12:26:40降维问题:顺序、链式存储结构的二叉树递归遍历、层次遍历求高度 全部源代码在最后 一、概要设计 测试数据:如图所示森林 森林采用兄弟孩子链表表示法。 森林的数据输入采取输入兄弟孩子链表表示法下的等价二叉树的... -
07.二叉树的遍历和求其高度
2022-01-05 13:17:29(一)二叉搜索树的遍历 二叉树如图 先序遍历 访问顺序: 根节点、前序遍历左子树,前序遍历右子树 7、4、2、1、3、5、9、8、11、10、12 递归遍历代码: public void preorderTraversal() { ... -
Python实现二叉树前序、中序、后序及层次遍历示例代码
2020-12-26 11:02:30前言 树是数据结构中非常重要的一种,主要的用途是用来... 队列实现层次遍历 # -*- coding=utf-8 -*- class Node(object): """节点类""" def __init__(self, element=-1, l_child=None, r_child=None): self.eleme -
求树的深度(层次遍历)
2016-10-25 21:51:56题目描述: 二叉树采用二叉链表存储,设计一个非递归算法求二叉树的高度。 核心代码: (全部代码请参照本博客判断完全二叉树) void Leveltravel(BiTree Bt) { if(Bt) { int max; Sq q;BiTree e; InitSq(q... -
利用层次遍历非递归求二叉树高度
2016-09-30 17:47:42利用层次遍历非递归求二叉树高度主要的思想是:一层一层地出队列 — 在我们每次访问完一层时,这时队列中存储的刚好是下一层的所有元素。所以在下一次循环开始时,首先记录该层的元素个数,一次性访问完这一层的所有... -
二叉树的各种操作 先序 中序 后续 层次 遍历 求树高度 节点深度 知先序中序求后续 二叉排序树
2012-09-04 14:17:23/*二叉树的各种操作复习*/ #include #define BACK_ODER -1 #define IN_ODER 0 ...#define LEVEL_ODER 2//层次化遍历 typedef struct _Node{ char data; struct _Node *lchild; struct _Node *rchild -
七十七、 二叉树的层次遍历和最大深度
2021-01-12 03:43:55「@Author:Runsen」在讲解二叉树的时候,提到二叉树的遍历除了前中后序遍历,还有层次遍历。前中后序这三种遍历方法以及可以通过递归的方式实现了,那么今天就来讲讲层次遍历吧!LeetCode 第 102题:二叉树的层次... -
二叉树的创建、先序、中序、后序遍历、层次遍历、树的高度、结点数、叶子结点数、左右结点交换
2020-05-17 20:51:22#二叉树的创建、先序、中序、后序遍历、层次遍历、树的高度、结点数、叶子结点数、左右结点交换 下面展示一些 内联代码片。 #include <stdio.h> #include <iostream> #include <malloc.h> #... -
树 前序,中序,后序,层次遍历,获取树的高度
2018-10-16 14:52:37本程序建树方法采用“先序遍历+空树用0表示” 结点和树的构建 class Node { public: char data; Node *left,*right; Node() { left=right=NULL; } }; class Tree { private: Node *Root; public: ... -
新手求助帖python二叉树遍历方法及其求二叉树高度
2020-12-09 10:26:59python二叉树遍历方法及其求二叉树高度 新人求助 先上代码 代码: class BinaryTreeNode(object): def __init__(self): self.data='#' self.leftchild=None self.rightchild=None class TreeState(object): def... -
计算二叉树的深度(高度):深度优先遍历(DFS递归)、广度优先遍历(BFS,层次遍历)
2020-11-30 15:14:59计算二叉树的深度(高度):深度优先遍历(DFS递归实现)、广度优先遍历(BFS,层次遍历) 先简要概述两种遍历的优缺点: 深度优先搜素算法:不全部保留结点,占用空间少;有回溯操作,运行速度慢。 广度优先搜索... -
【数据结构】-树-求二叉树的高度/深度(层次遍历方法与递归方法)
2020-06-17 16:34:54层次遍历算法: int Height_Tree(BiTree T) { BiTNode* Q[100];//用数组做队列 int front = -1;//当前访问的节点 int rear = -1;//下一层新加入的节点 int level = 0, last = 0;//当前层的最后一个节点 ... -
树的先序(后序)中序构建二叉树 和树遍历+求树的深度和高度
2021-11-22 20:47:412.先序中序后序递归遍历树: 3.树的层次遍历 4.判断树的高度和深度: 5.树的销毁 1.树的先序(后序)中序构建二叉树 树的先序遍历: 根 左 右 树的中序遍历: 左 根 右 树的后序遍历 左 右 根 我们明确... -
【练习】c++分别用层序遍历和递归求二叉树深度
2021-04-24 01:06:14递归求深度: struct node { int data; node* lchild;//指向左孩子的结点 node* rchild;//指向右孩子的结点 }; int depth(node* root) { int l, r; node* tem = new node; if (root == nullptr) return 0; ... -
树与树算法&&二叉树的层次遍历/广度遍历/深度遍历详解与代码实现
2020-10-29 19:53:41=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点: 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一... -
【数据结构】 实验报告10 顺序、链式存储结构的二叉树递归遍历、层次遍历求高度
2020-05-05 12:19:53两种及以上存储结构(建议 顺序存储结构和链式存储结构各一)、两种及以上方法(建议 递归遍历和层次遍历方法各一)。分析各代码性能。 抽象数据类型(二叉树)独立模块实现。 其它要求同作业-01要求。 二、实验环境... -
二叉树:先序遍历,中序遍历,后序遍历,层序/层次遍历
2022-05-12 17:29:09介绍了二叉树的递归遍历和非递归遍历,还有一些较为复杂的遍历(和代码) 中序遍历:(morris遍历)空间复杂度O(1),非递归,不用栈 先序遍历:空间复杂度O(1),非递归,不用栈 后序遍历:空间复杂度O(1),非递归,不用栈 -
python实现二叉树的创建、前序遍历、中序遍历以及层次遍历
2022-02-24 17:50:54二叉树是指度不超过2的树,可以由n个结点构成,如下图。 二叉树的创建 注意:输入的格式,如下图,D结点的孩子结点,空结点用#代替,直到最后一层就可以停止输入,以下面这棵树为例,则我们的输入为 ABCDE#F##G###... -
数据结构_求二叉树的高度以及层次遍历二叉树算法_C语言源代码
2014-07-20 12:41:17int 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; -
数据结构-二叉树的非层次遍历以及应用(输出叶子结点,求树的高度)
2021-03-26 19:01:58数据结构-二叉树的非层次遍历以及应用(输出叶子结点,求树的高度)树的定义以树节点的堆栈和队列的结构堆栈的操作前序,中序,和后序的非递归遍历使用堆栈可以对二叉树进行层次遍历输出树的叶子结点求树的高度前序... -
JAVA实现通过中序遍历和后序遍历序列建树,并求树的高度,用层次遍历做验证
2021-02-27 08:31:52作为例子的树长这样:package bstpractice;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class BstTest {public static void main(String args[]){//step1,先根据中序,后序... -
二叉树的中序序列和后序序列构造二叉树,实现查找,求高度,先序、中序、后序和层次遍历,用相关数据进行...
2022-05-16 22:09:34if t==None: return 0 #空树的高度为0 else: lh=self._Height1(t.lchild) #求左子树高度lchildh rh=self._Height1(t.rchild) #求右子树高度rchildh return max(lh,rh)+1 def PreOrder(bt): #先序遍历的递归算法 _... -
小白都能看懂的二叉树基本操作(三):层序遍历、求高度、求节点与叶子节点个数
2021-08-26 09:32:17今天继续填坑! 建树的代码可以参考之前文章: 建树操作 有一说一,二叉树这个坑是真的大,填...如上树,层序遍历结果应该为: a -> b -> g -> c -> d -> h -> e -> f 为了达到这个目... -
层次遍历递归和非递归方法
2019-10-26 21:53:00层次遍历递归和非递归方法 如何遍历一棵树 有两种通用的遍历树的策略: 深度优先搜索(DFS) 在这个策略中,我们采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支... -
python实现二叉树层次遍历(宽度优先遍历或叫广度优先遍历)
2018-09-04 15:47:581、何为层次遍历 说白了,就是一层一层、由上至下、由左至右的搜索遍历... 利用队列,依次将根,左子树,右子树存入队列,按照队列的先进先出规则来实现层次遍历。 3、编程实现 class Node(): # 节点类 ...