精华内容
下载资源
问答
  • 二叉树的层次遍历
    千次阅读 多人点赞
    2020-08-27 01:23:39

    在二叉树中,我们常见的遍历方式 主要有四种。分别是:

    • 前序遍历(根节点->左节点->右节点)
    • 中序遍历(左节点->根节点->右节点)
    • 后序遍历(左节点->右节点->根节点)
    • 层次遍历

    其实记住以上的输出顺序还是非常简单的。首先要明白,左节点一定先比右节点输出
    那么就很好理解了,那么那些所谓的前序、中序、后序而言是针对根节点的相对位置命名的。
    例如前序遍历,则就是根节点是最前面输出的,所以我们不难得到,前序遍历的顺序为:根节点->左节点->右节点。其他同理。

    那么今天介绍下一种不同的方式—层次遍历。注意层次队列不能使用递归来完成,并且需要借助一个队列来帮我们完成整个过程的遍历!

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    #define  ElemType char
    #define maxSize 100
    typedef struct Tree{
    	ElemType data;
    	struct Tree * rchild;
    	struct Tree * lchild;
    }Tree,*Treep;
    
    /*
    	采用前序遍历的思想创建二叉树 
    */ 
    void createTree(Tree * &p){
    	char c;
    	scanf("%c",&c);
    	if(c == ' '){
    		return;
    	}
    	p = (Tree *)malloc(sizeof(Tree));
    	p->data = c;
    	p->lchild = NULL;
    	p->rchild = NULL;
    	createTree(p->lchild);
    	createTree(p->rchild);
    	
    }
    /*
    	该算法的主要思想是
    		1. 输出根节点的值
    		2. 把该节点的左孩子添加到队列
    		3. 把该节点的右孩子添加到队列
    		4. 从队列一一取出 重复上述步骤。
    		 
    		在遍历当前层次的时候,输出当前节点,并把下一层次
    		的节点按左右节点顺序存入队列。
    		队列的特点是:先进先出 那么这就很好的利用了队列的特点
    		达到了层次遍历的效果。 
    */ 
    void levelPrint(Tree * p){
    	//初始化一个非循环队列
    	Treep stack[maxSize];
    	int front,real;
    	front = real = 0;
    	Tree *curr ,*pre;
    	pre = p;
    	while(pre != NULL){
    		// 输出当前节点的值 
    		cout<<pre->data;
    		// 拿到当前节点的左孩子指针 
    		curr = pre->lchild;
    		//如果左孩子不为空 入队!
    		if(curr != NULL){
    			stack[real++] = curr;
    		}
    		// 如果右孩子不为空 入队! 
    		curr = pre->rchild;
    		if(curr != NULL){
    			stack[real++] = curr;
    			
    		}
    		// 如果队列不为空则从队列取出元素 
    		if( front != real) 
    			pre = stack[front++];
    		else //否则直接置空指针 
    			pre = NULL;
    		
    	}
    }
    
    int main(int argc, char** argv) {
    	Tree *root;
    	// 前序创建二叉树 
    	createTree(root);
    	// 层次遍历二叉树 
    	levelPrint(root);
    	return 0;
    }
    
    更多相关内容
  • 二叉树层次遍历算法 #include <stdio.h> #include <alloc.h> #define MaxSize 1000 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; 创建二叉树...
  • 文章目录1 bfs2 dfs3 二叉树层次遍历 1 bfs   广度优先搜索(bfs) 和深度优先搜索都是的图的经典搜索算法之一,我们这里先给出一些模板。简单理解就是树的层次遍历,对于图的时候,也是按层,具体的就是节点与...
  • (数据结构)二叉树层次遍历

    千次阅读 2022-03-30 21:05:43
    二叉树层次遍历 二叉树层次遍历的实现思想是:通过队列数据结构,从树的根结点开始,依次将其左孩子和右孩子入队;而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后...

    二叉树层次遍历

            二叉树层次遍历的实现思想是:通过队列数据结构,从树的根结点开始,依次将其左孩子和右孩子入队;而后每次队列中一个结点出队,都将其左孩子和右孩子入队,直到树中所有结点都出队,出队结点的先后顺序就是层次遍历的最终结果

    图1 二叉树

    以上图 1 为例,层次遍历的过程如下:

    1. 首先,根结点 1 入队
    2. 根结点 1 出队,出队的同时,将左孩子 2 和右孩子 3 分别入队
    3. 队头结点 2 出队,出队的同时,将结点 2 的左孩子 4 和右孩子 5 依次入队
    4. 队头结点 3 出队,出队的同时,将结点 3 的左孩子 6 和右孩子 7 依次入队
    5. 不断地循环,直至队列内为空

    因此,图 1 中二叉树采用层次遍历得到的序列为:1234567

    二叉树层次遍历代码实现

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct MyBiTNode{
        int data;  // 数据域
        struct MyBiTNode *lchild, *rchild;  // 左右孩子指针
    } BiTNode;
    
    BiTNode *CreateBiTree(BiTNode *T){
    	// 结点 1 
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = 1;
        // 结点 2
    	T->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->data = 2;
    	// 结点 3
    	T->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->data = 3;
    	// 结点 4 
    	T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->lchild->data = 4;
    	T->lchild->lchild->lchild = NULL;
    	T->lchild->lchild->rchild = NULL;
    	// 结点 5
    	T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->lchild->rchild->data = 5;
    	T->lchild->rchild->lchild = NULL;
    	T->lchild->rchild->rchild = NULL;
    	// 结点 6
    	T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->lchild->data = 6;
    	T->rchild->lchild->lchild = NULL;
    	T->rchild->lchild->rchild = NULL;
    	// 结点 7
    	T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
    	T->rchild->rchild->data = 7; 
    	T->rchild->rchild->lchild = NULL;
    	T->rchild->rchild->rchild = NULL;
    	return T;
    }
     
    // 初始化队头和队尾指针开始时都为 0
    int front = 0, rear = 0;
    
    // 入队函数
    void EnQueue(BiTNode **a, BiTNode *node){
        a[rear++] = node;
        // a[0] = Tree; rear = 1
        // a[1] = Tree->lchild; rear = 2
        // a[2] = Tree->rchild; rear = 3
        // a[3] = Tree->lchild->lchild; rear = 4
        // a[4] = Tree->lchild->rchild; rear = 5
        // a[5] = Tree->rchild->lchild; rear = 6
        // a[6] = Tree->rchild->rchild; rear = 7
    }
    
    // 出队函数 
    BiTNode *DeQueue(BiTNode **a){
        return a[front++];
        // a[0]; front = 1 
        // a[1]; front = 2
        // a[2]; front = 3
    }
    
    //输出函数 
    void displayNode(BiTNode *node){
        printf("%d ", node->data);
    }
    
    // 层次遍历函数
    void LevelOrderTraverse(BiTNode *Tree){
    	// 采用顺序队列,初始化创建队列数组
        BiTNode *a[20];
        // 创建临时指针 
        BiTNode *p;
        // 根结点入队
        EnQueue(a, Tree);
        // 当队头和队尾相等时,表示队列为空
        while(front < rear){
            // 队头结点出队
            p = DeQueue(a);  // Tree;Tree->lchild;Tree->rchild
            displayNode(p);  // 1 2 3
            // 将队头结点的左右孩子依次入队
            if(p->lchild != NULL) {
                EnQueue(a, p->lchild);
            }
            if (p->rchild != NULL) {
                EnQueue(a, p->rchild);
            }
        }
    }
    
    int main() {
        BiTNode *Tree = NULL;  // 结构体指针指向空 
        Tree = CreateBiTree(Tree);  // 传入结构体指针 
        
        LevelOrderTraverse(Tree);  // 层次遍历 
        return 0;
    }

    展开全文
  • 二叉树层次遍历 二叉树层次遍历的基本算法在本文中不提及。本文内容为,在二叉树层次遍历中,为何选用队列这样一种数据结构。 不使用额外数据结构 首先,假设我们不使用额外的数据结构,只使用 1 个指针: 访问第一...

    二叉树层次遍历

    二叉树层次遍历的基本算法在本文中不提及。本文内容为,在二叉树层次遍历中,为何选用队列这样一种数据结构。

    不使用额外数据结构

    首先,假设我们不使用额外的数据结构,只使用 1 个指针:

    访问第一层:没有任何问题,因为 root 是已知的。

    在这里插入图片描述

    访问第二层:也没有任何问题,因为我们知道第二层所有结点的 parent

    访问第三层:问题来了,我们不知道第三层所有结点的 parent

    那该怎么办呢?访问第三层的时候一定需要知道第二层结点的位置,于是我们就想,不如把第二层结点保存起来。这样,在遍历第三层的时候,就可以拿到第二层结点,通过每个第二层结点的 left 和 right 指针完成第三层的遍历。

    把刚刚的过程推广一下,若无法访问第 n 层,那么是由于无法获得 n - 1 层结点导致的。因此需要保存 n - 1 层结点的信息,而且是在遍历 n - 1 层结点保存的。

    那么问题又来了:使用什么数据结构保存第 n - 1 层结点信息?

    如何保存 n - 1 层结点

    咱们一个个来看:Stack、Queue、Set、Map。以访问上图中第 3 层结点(即 4 号和 5 号)为例:

    1. 如果使用 Stack,那么遍历完第 2 层后,栈中元素为 2 和 3。在遍历第 3 层时,需要取出栈中全部元素 2 和 3,并将所有第 3 层结点都遍历完,然后再一次性把结点放入栈中,以便遍历第 4 层。注意需满足所有一次性,不然会导致两层元素混杂在栈中,无法实现层次遍历。这样做其实并不简单,又需要额外的数据结构来存储。

    2. 如果使用 Queue,那么遍历完第 2 层后,队列中元素为所有第 2 层结点,即 2 和 3。在遍历第 3 层时,只需要每次从中取出一个结点,然后访问该结点的左右孩子,并将左右孩子放在队列中。这里只取出一个结点,而不需要全部取出的原因是:由于队列满足先进先出(FIFO)的特性,由于第 2 层结点在第 3 层结点之前进入队列,那么第 3 层结点一定会放在第 2 层结点之后,以保证第 2 层结点会先出队列

    3. 则不然,栈是后进先出(LIFO)的,先进去的后出来。假设我们从栈中取出 2 号结点后,将 4 和 5 放入栈中,那么 3号结点则会在栈较深的位置,比 4 和 5后出来。栈破坏了层与层之间的先后顺序,不能适用于层次遍历。

    4. Set 和 Map 并不会维持元素之间的先后顺序,它们要么基于哈希实现,要么基于元素实际值的大小实现,不会记录元素进入容器的先后顺序,因此同样不适合层次遍历。

    总结:父节点组成的队列

    因此,在遍历每个元素时,都需要将当前元素入队列。每个入队列的元素承担着访问下一层元素的使命,同时,每个元素都需要借助队列中的元素才能够访问到。不过,这里也有一个例外,对于整棵树的根节点,无需通过队列来获取。它从一开始就是已知的。

    展开全文
  • 主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
  • Java 二叉树层次遍历

    千次阅读 2020-06-06 16:28:41
    Java 二叉树层次遍历

    Java 二叉树层次遍历

    简介: 遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。

    设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有几种情况:DLR(称为先序遍历),LDR(称为中序遍历),LRD (称为后序遍历),层次遍历。

    **层次遍历:**按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)。

    如图二叉树的层次遍历结果为: 3,9,20,15,7
    在这里插入图片描述
    代码实现:

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(15);
        TreeNode n4 = new TreeNode(7);
        root.left = n1;
        root.right = n2;
        n2.left = n3;
        n2.right = n4;
    
        List<List<Integer>> rs = levelOrder(root);
        System.out.println(rs);
    }
    
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        if (root == null)
            return list;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
    
        while (!deque.isEmpty()) {
            int num = deque.size();
            List<Integer> subList = new LinkedList<Integer>();
            for (int i = 0; i < num; i++) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
                subList.add(node.val);
            }
            list.add(subList);
        }
        return list;
    }
    

    TreeNode.java文件:

    public class TreeNode {
    
    	public int val;
    	public TreeNode left;
    	public TreeNode right;
    
    	public TreeNode(int x) {
    		val = x;
    	}
    
    	public static int treeHeight(TreeNode root) {
    		if (null == root) {
    			return 0;
    		}
    		int l = treeHeight(root.left);
    		int r = treeHeight(root.right);
    
    		return (l > r) ? l + 1 : r + 1;
    	}
    
    }
    

    在这里插入图片描述

    展开全文
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    二叉树层序遍历 1、算法思想 用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点...此过程不断进行,当队列为空时,二叉树层次遍历结束...
  • 二叉树层次遍历 与二叉树先序、中序遍历使用栈类似,二叉树的层次遍历的实现是基于队列这个数据结构来实现的。 主要算法思想是首先建一个队列并将树的根节点入队,然后当树不为空的时候持续访问队首节点并将其左右...
  • 二叉树层次遍历也称广度优先遍历,是一种按照逐层遍历的二叉树遍历方式。广度优先遍历需要借助辅助队列来存取各个节点。实现方法如下: //层次遍历 void LevelOrder(BiTree T) { LinkQueue Q;//辅助队列 ...
  • # 求二叉树路径DFS class TreeNode: def __init__(self, val = None): self.left = None self.right = None self.val = val class BTree: def insert(self,root,node): #构建二叉排序树 if root is None: ...
  • 1.层次遍历 void LevelOrder(BTree *t){ Queue Q; initQueue(Q); EnQueue(Q,t); while(!Empty(Q)){ TNode*p=DeQueue(Q); if(p->lchird) EnQueue(Q,p->lchird); if(p->rchird) EnQueue(Q,p->...
  • 2、层次遍历二叉树。输入二叉树头节点的指针。先将头节点入队,将结点指针交给P,后出队。然后再将P左右孩子入队。循环至全部遍历。 注意递归创建过程: 因为先序创建二叉树是左右递归创建,所以一个结束符是结束了...
  • 前两篇解释了二叉树的有关逻辑概念及前中后序输出递归代码的实现,这篇将讲述二叉树层次遍历输出如何实现以及二叉树前序遍历输入的两种情况。
  • 数据结构-二叉树层次遍历

    万次阅读 多人点赞 2018-10-23 14:57:49
    首先介绍下二叉树层次遍历即按照顺序对树节点依次访问,如下图: 顺序遍历的结果为:ABCDEFGHIJK 我们可以借助一个队列来实现二叉树层次遍历;思路如下: 先将二叉树根节点入队,然后出队,访问该节点,...
  • 二叉树层次遍历--C语言

    万次阅读 多人点赞 2018-12-21 17:54:22
    今天写一下二叉树层次遍历层次遍历用到的数据结构是队列。   层次遍历算法中增加了三个int型数据,其中levelcount用于记录现在处理的是树的第几层;curlevel用于记录当前层还有几个节点没有被访问过;next...
  • 问题来源:二叉树层次遍历 问题描述:给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例子: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历...
  • C语言实现二叉树层次遍历

    千次阅读 2022-01-18 21:41:21
    对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下、从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历...
  • 故知道该题主要考察二叉树基本的层次遍历方法,需要打印出每层节点的关键字。 二叉树层次遍历实现思路是用一个队列记录每层节点,当记录第一层节点时,弹出第一层节点进行访问,访问的同时需要遍历对应节点的左右...
  • 层次遍历算法: void _PrintTree_f5(BiTree a) { LinkQueue b; b=InItQueue(); EnQueue(&b,a); while(!QueueEmpty(b)) { BiTree d; d=getFront(b); printf("%c\n",d->data); if(d->lchild)...
  • 二叉树层次遍历

    2016-09-26 09:57:04
    将图示的二叉树按照层次遍历,即得到遍历顺序为 8,6,10,5,7,9,11思想: 打印节点,如果该节点为空,则返回。 否则打印该节点,如果该节点存在孩子节点则存入队列,直到无孩子节点代码: 节点结构:class ...
  • 二叉树层次遍历详解

    2022-06-30 22:01:26
    二叉树层次遍历
  • 二叉树层次遍历(用队列实现)

    千次阅读 2019-08-18 17:21:24
    void BinaryTreeLevelOrder(BTNode* root)//用队列层次遍历 { Queue qu; BTNode* cur; QueueInit(&qu);//有初始化就要销毁 QueuePush(&qu, root);//根节点入队 while (!QueueIsEmpty(&qu)) { cur = ...
  •  上面这个二叉树,那么层次遍历的输出应该是:1、2、3、4、5、6、7、8、9 2、解题思路  利用队列,依次将根,左子树,右子树存入队列,按照队列的先进先出规则来实现层次遍历。 3、编程实现 class Node(): #...
  • 二叉树层次遍历(js)

    2020-09-23 08:49:56
    二叉树层次遍历(js)] //二叉树 var node4 = {left: null, right: null, val: 4 }; var node5 = {left: null, right: null, val: 5 }; var node6 = {left: null, right: null, val: 6 }; var node7 = {left: null, ...
  • 7-1 二叉树层次遍历 (25 分) 编写程序,要求实现(1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 ...
  • 层次遍历用队列,但是如何记录层次是一个需要思考的地方。一种方法是提供两个变量记录本层节点数和下层节点数,还有一种很巧妙的方法,记录队列中元素的数量,就是当前层次节点数。 题解: 这道题思路是使用层次遍历...
  • 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的...
  • 二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;父节点被访问的次序位于左右孩子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,390
精华内容 21,756
关键字:

二叉树的层次遍历