精华内容
参与话题
问答
  • 二叉树的层序遍历

    2019-04-21 09:12:28
    设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是...

    1. 定义

    • 设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

    • 层序遍历为广度优先遍历,需要队列实现。

    2. 普通的层序遍历

    • 思路

      • 启动 -> 根入队列
      • 找下线(去除空节点)
        • 取队首
        • 找左右孩子,并将其入队列
        • 左孩子出队列,左孩子的左右孩子入队列
        • 右孩子出队列,右孩子的左右孩子入队列
        •     ......
    • 终止条件

      • 队列为空
    public class LevelOrderTraversal {
        private static class Node {
            int value;
            //左子树
            Node left;
            //右子树
            Node right;
    
            Node(int v) {
                this.value = v;
            }
        }
        public static void levelOrderTraversal(Node root) {
            if(root==null){
                return;
            }
            //存放节点
            LinkedList<Node> queue=new LinkedList();
            //根节点放入队列
            queue.addLast(root);
            //若队列不为空,则一直 出一个进*个(左右子树为空则不进入)
            while(!queue.isEmpty()) {
                Node out=queue.pollFirst();
                System.out.println(out.value);
                //找下线
                if(out.left!=null){
                    queue.addLast(out.left);
                }
                if(out.right!=null){
                    queue.addLast(out.right);
                }
            }
        }
    }

    3. 二维的层序遍历

    给定一个二叉树,返回其按层次遍历的节点值。(逐层地,从左到右访问所有节点)

    • 思路

      • 1.创建一个NodeLevel类,存放节点和层数
      • 2.使用List<List<Integer>>类型创建的list来存储结果,类似于{ {} {} {} }
      • 3.若为空树,直接返回{}
      • 4.创建一个LinkedList类型的队列,用于存放与取出节点
      • 5.将根节点存入队列
      • 6.若队列不为空,一直循环操作
        • a.取出根节点
        • b.若层数等于list.size(),即大括号中的第几个小括号。则新建一个小括号,并将节点放入;否则,直接将节点放入
        • c.当根节点的左孩子不为空时,存入左孩子,层数加1
        • d.当根节点的右孩子不为空时,存入右孩子,层数加1
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    /**
     * Author:qqy
     */
    public class LevelOrder {
        private static class Node {
            int value;
            //左子树
            Node left;
            //右子树
            Node right;
    
            Node(int v) {
                this.value = v;
            }
        }
    
        public List<List<Integer>> levelOrder(Node root) {
            List<List<Integer>> list=new ArrayList<>();
            if(root==null){
                return list; //{}
            }
    
            class NodeLevel{
                int level;
                Node node;
    
                NodeLevel(Node node,int level){
                    this.node=node;
                    this.level=level;
                }
            }
    
            //建一个队列
            LinkedList<NodeLevel> queue=new LinkedList<>();
            //将根结点放入队列
            queue.addLast(new NodeLevel(root,0));
            while(!queue.isEmpty()){
                NodeLevel out=queue.pollFirst();
                //弹出的节点
                Node node=out.node;
                //弹出的层
                int level=out.level;
                if(list.size()==level){
                    list.add(new ArrayList<>());
                }
                list.get(level).add(node.value);
    
                if(node.left!=null){
                    queue.addLast(new NodeLevel(node.left,level+1));
                }
                if(node.right!=null){
                    queue.addLast(new NodeLevel(node.right,level+1));
                }
            }
            return list;
        }
    }

     

    展开全文
  • 我们来看看下图的二叉链表 如何实现层序遍历层序遍历顺序:ABECDG A为B、E的双亲结点,遍历顺序是 根-&gt;左-&gt;右 是不是。 而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的...

    实现思路

    我们来看看下图的二叉链表 如何实现层序遍历

    层序遍历顺序:ABECDG
    A为B、E的双亲结点,遍历顺序是 根->左->右 是不是。
    而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。
    A->出队
    队列:E、B
    B->出队
    队列:D、C、E
    E->出队
    队列:G、D、C
    C->出队
    队列:G、D
    D->出队
    队列:G
    G->出队
    队列为空,层序遍历完毕

    二叉树层序遍历算法代码

    层序遍历函数

    层序遍历核心代码,利用了一个自己底层封装的顺序队列如果想知道怎么实现的呢,请看线性表:顺序队列算法实现

    //一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }

    完整代码

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    typedef char ElemType;
    typedef struct BiNode
    {
    	ElemType data;
    	struct BiNode* lchild;
    	struct BiNode* rchild;
    }BiNode, *BiTree;
    
    //创建二叉链表
    void CreateBiTree(BiTree* tree) 
    {
    	char c;
    	scanf("%c", &c);
    	if (c == ' ')
    	{
    		*tree = NULL;
    		return;
    	}
    	*tree = malloc(sizeof(BiNode));
    	(*tree)->data = c;
    	CreateBiTree(&(*tree)->lchild);
    	CreateBiTree(&(*tree)->rchild);
    	return;
    }
    //二叉链表 递归前序遍历
    void PreTraverse(BiTree tree)
    {
    	if (tree == NULL)
    	{
    		return;
    	}
    	printf("%c ", tree->data);
    	PreTraverse(tree->lchild);
    	PreTraverse(tree->rchild);
    }
    
    //一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
    //直到队列为空
    void SeqTraverse(BiTree tree)
    {
    	SeqQueue queue = Init_SeqQueue();
    	Push_SeqQueue(queue, tree);
    	while (!IsEmpty_SeqQueue(queue))
    	{
    		BiTree root = Pop_SeqQueue(queue);
    		printf("%c ", root->data);
    		if (root->lchild)
    			Push_SeqQueue(queue, root->lchild);
    		if(root->rchild)
    			Push_SeqQueue(queue, root->rchild);
    	}
    	printf("\n");
    }
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请前序遍历输入结点:");
    	CreateBiTree(&tree);
    	printf("前序遍历:");
    	PreTraverse(tree);
    	printf("\n层序遍历:");
    	SeqTraverse(tree);
    	
    	return 0;
    }
    

    代码运行检测

    我们构建如下图的二叉树,注意创建二叉树输入序列为:ABC__D__E_G__,_代表一个空格哟。

    运行结果

     

    展开全文
  • 二叉树的层序遍历(两种方法实现)

    万次阅读 多人点赞 2018-06-24 23:51:59
    两种方法实现二叉树的层序遍历 1、说明 二叉树的层序遍历是面试经常会被考察的知识点,甚至要求当场写出实现过程。 层序遍历所要解决的问题很好理解,就是按二叉树从上到下,从左到右依次打印每个节点中存储的...

    两种方法实现二叉树的层序遍历

    1、说明

    二叉树的层序遍历是面试经常会被考察的知识点,甚至要求当场写出实现过程。

    层序遍历所要解决的问题很好理解,就是按二叉树从上到下,从左到右依次打印每个节点中存储的数据。如下图:

    这里写图片描述

    先序遍历:A → B → D → C
    中序遍历:B → D → A → C
    后续遍历:D → B → C → A
    层序遍历:A → B → C → D

    2、实现

    队列实现:
    • 仔细看看层序遍历过程,其实就是从上到下,从左到右依次将每个数放入到队列中,然后按顺序依次打印就是想要的结果。

    • 实现过程
      1、首先将二叉树的根节点push到队列中,判断队列不为NULL,就输出队头的元素,
      2、判断节点如果有孩子,就将孩子push到队列中,
      3、遍历过的节点出队列,
      4、循环以上操作,直到Tree == NULL。

    void FloorPrint_QUEUE(pTreeNode &Tree) //层序遍历_队列实现
    {
        queue < pTreeNode> q;
        if (Tree != NULL)
        {
            q.push(Tree);   //根节点进队列
        }
    
        while (q.empty() == false)  //队列不为空判断
        {
            cout << q.front()->data << " → "; 
    
            if (q.front()->leftPtr != NULL)   //如果有左孩子,leftChild入队列
            {
                q.push(q.front()->leftPtr);   
            }
    
            if (q.front()->rightPtr != NULL)   //如果有右孩子,rightChild入队列
            {
                q.push(q.front()->rightPtr);
            }
            q.pop();  //已经遍历过的节点出队列
        }
    }
    数组实现:
    • 实现过程
      1、创建一个指针数组,保存二叉树结构体指针,
      2、保存二叉树根节点,再申请变量 in、out ,控制数组,在遍历过程中,始终能找到节点和该节点的前一个节点,
      3、循环以上过程。
    void FloorPrint(pTreeNode Tree)  //层序遍历
    {
        pTreeNode temp[100];   //创建pTreeNode指针类型的指针数组
        int in = 0;
        int out = 0;
    
        temp[in++] = Tree;  //先保存二叉树根节点 
    
        while (in > out)
        {
            if (temp[out])
            {
                cout << temp[out]->data << " → ";
                temp[in++] = temp[out]->leftPtr;
                temp[in++] = temp[out]->rightPtr;
            }
            out++;
        }
    }

    3、完整代码

    bintree.h

    #ifndef __BINTREE_H__
    #define __BINTREE_H__
    
    #include<iostream>
    #include<cstring>
    #include<cassert>
    #include<queue>
    
    using namespace std;
    
    typedef char DataType;
    
    struct TreeNode {
    
        DataType data;    /* node data */
    
        struct TreeNode *leftPtr;   /* pointer to left subtree */
    
        struct TreeNode *rightPtr;  /* pointer to right subtree */
    };
    
    typedef struct TreeNode TreeNode;
    
    typedef TreeNode * pTreeNode;
    
    void CreateBinTree(pTreeNode *Tree);//创建二叉树
    
    void InitTreeNode(pTreeNode *Tree);//初始化
    
    void PreOrderPrint(pTreeNode Tree);//先序遍历
    
    void MidOrderPrint(pTreeNode Tree);//中序遍历
    
    void PostOrderPrint(pTreeNode Tree);//后续遍历
    
    void FloorPrint(pTreeNode Tree);//层序遍历
    
    void FloorPrint_QUEUE(pTreeNode &Tree);//层序遍历_队列实现
    
    #endif

    bintree.cpp

    #include"binterr.h"
    
    void InitTreeNode(pTreeNode *Tree)
    {
        *Tree = NULL;
    }
    
    void CreateBinTree(pTreeNode *Tree)
    {
        DataType ch;
        ch = getchar();
        if (ch == '#')
        {
            *Tree = NULL;
        }
        else
        {
            *Tree = (pTreeNode)malloc(sizeof(pTreeNode));
    
            if (NULL == (*Tree))
            {
                exit(0);
            }
            else
            {
                (*Tree)->data = ch;
                (*Tree)->leftPtr = NULL;
                (*Tree)->rightPtr = NULL;
                CreateBinTree(&(*Tree)->leftPtr);
                CreateBinTree(&(*Tree)->rightPtr);
            }
        }
    }
    
    
    void PreOrderPrint(pTreeNode Tree)
    {
        if (!Tree)
        {
            return;
        }
        cout << Tree->data << " → ";
        PreOrderPrint(Tree->leftPtr);
        PreOrderPrint(Tree->rightPtr);
    }
    
    void MidOrderPrint(pTreeNode Tree)//中序遍历
    {
        if (NULL != Tree)
        {
            PreOrderPrint(Tree->leftPtr);
            cout << Tree->data << " → ";
            PreOrderPrint(Tree->rightPtr);
        }
    }
    
    void PostOrderPrint(pTreeNode Tree)//后续遍历
    {
        if (NULL != Tree)
        {
            PreOrderPrint(Tree->leftPtr);
            PreOrderPrint(Tree->rightPtr);
            cout << Tree->data << " → ";
        }
    }
    
    void FloorPrint(pTreeNode Tree)  //层序遍历
    {
        pTreeNode temp[100];   //创建pTreeNode指针类型的指针数组
        int in = 0;
        int out = 0;
    
        temp[in++] = Tree;  //先保存二叉树根节点 
    
        while (in > out)
        {
            if (temp[out])
            {
                cout << temp[out]->data << " → ";
                temp[in++] = temp[out]->leftPtr;
                temp[in++] = temp[out]->rightPtr;
            }
            out++;
        }
    }
    
    void FloorPrint_QUEUE(pTreeNode &Tree) //层序遍历_队列实现
    {
        queue < pTreeNode> q;
        if (Tree != NULL)
        {
            q.push(Tree);   //根节点进队列
        }
    
        while (q.empty() == false)  //队列不为空判断
        {
            cout << q.front()->data << " → "; 
    
            if (q.front()->leftPtr != NULL)   //如果有左孩子,leftChild入队列
            {
                q.push(q.front()->leftPtr);   
            }
    
            if (q.front()->rightPtr != NULL)   //如果有右孩子,rightChild入队列
            {
                q.push(q.front()->rightPtr);
            }
            q.pop();  //已经遍历过的节点出队列
        }
    }

    test.cpp

    #include"binterr.h"
    
    void test()
    {
        pTreeNode T;
        InitTreeNode(&T);
    
        CreateBinTree(&T);  //创建一个二叉树
    
        cout << "前序遍历:" << endl;
        PreOrderPrint(T);    //前序遍历
    
        cout << "\n中序遍历:" << endl;
        MidOrderPrint(T);   //中序遍历
    
        cout << "\n后序遍历:" << endl;
        PostOrderPrint(T);   //后续遍历
    
        cout << "\n层序遍历:" << endl;
        FloorPrint(T);
    
        cout << "\n层序遍历——Queue:" << endl;
        FloorPrint_QUEUE(T);
    }
    
    int main(void)
    {
        test();
        return 0;
    }

    4、结果截图

    这里写图片描述

    展开全文
  • 递归实现: 计算二叉树的高度 逐层打印: 例如打印二叉树的第k层,可以看作以root-&gt;_left为根节点,打印它的k-1层,然后以root-&gt;_right为根节点,打印它的k-1层,直到k==1。...void _BTreeLevelOrder...

    递归实现:

    • 计算二叉树的高度
    • 逐层打印:
      例如打印二叉树的第k层,可以看作以root->_left为根节点,打印它的k-1层,然后以root->_right为根节点,打印它的k-1层,直到k==1。
    void _BTreeLevelOrder(BTNode* root, size_t i)
    {
        if (root == NULL || i == 0)
        {
            return;
        }
        if (i == 1)
        {
            printf("%d ", root->_data);
            return;
        }
        _BTreeLevelOrder(root->_left, i - 1);
        _BTreeLevelOrder(root->_right, i - 1);
    }
    
    void BTreeLevelOrder(BTNode* root)
    {
        if (root == NULL)
            return;
        int dep = BTreeDepth(root);
        for (int i = 1; i <= dep; i++)
        {
            _BTreeLevelOrder(root, i);
        }
    
    }

    非递归实现:

    • 运用队列来实现非递归,让root节点入队列,然后出队列(将要出队列的节点记为front),打印节点,判断front的两个节点是否为空,若不为空则入队列,重复上述操作直到队列为空。
    void BTreeLevelOrderNonR(BTNode* root)
    {
        Queue q;
        QueueInit(&q);
        if (root)
            QueuePush(&q, root);
        while (QueueEmpty(&q) != 0)
        {
            BTNode* front = QueueFront(&q);
            printf("%d ", front->_data);
            QueuePop(&q);
            if (front->_left)
            {
                QueuePush(&q, front->_left);
            }
            if (front->_right)
            {
                QueuePush(&q, front->_right);
            }
        }
        printf("\n");
    }

    非递归层序遍历的应用:判断二叉树是否是完全二叉树

    • 入队列的时候不用判断节点是否为空,直接入队列;出队列的时候如果front==NULL,停止入队列,判断队列里的元素是否全为NULL,若是则是完全二叉树。

    这里写图片描述

    int IsCompleteBTree1(BTNode* root)
    {
        Queue q;
        QueueInit(&q);
        if (root)
            QueuePush(&q, root);
        while (QueueEmpty(&q) != 0)
        {
            BTNode* front = QueueFront(&q);
            QueuePop(&q);
            if (front == NULL)
            {
                break;
            }
            else
            {
                QueuePush(&q, front->_left);
                QueuePush(&q, front->_right);
            }
        }
        while (QueueEmpty(&q) != 0)
        {
            BTNode* front = QueueFront(&q);
            if (front)
            {
                return 0;
            }
            QueuePop(&q);
        }
        return 1;
    }
    
    • 设置flag,初始化flag为1,如果front的孩子不为空:如果flag为0,返回0;如果flag为1,将front的孩子入队列。如果front的孩子为空,则置flag为0。队列为空还没有返回0,则返回1。配合下图进行理解
      这里写图片描述
    int IsCompleteBTree2(BTNode* root)
    {
        Queue q;
        QueueInit(&q);
        if (root)
            QueuePush(&q, root);
        int flag = 1;
        while (QueueEmpty(&q) != 0)
        {
            BTNode* front = QueueFront(&q);
            QueuePop(&q);
            if (front->_left)
            {
                if (flag == 0)
                {
                    return 0;
                }
                QueuePush(&q, front->_left);
            }
            else
                flag = 0;
            if (front->_right)
            {
                if (flag == 0)
                {
                    return 0;
                }
                QueuePush(&q, front->_right);
            }
            else
                flag = 0;
        }
        return 1;
    }

    关于队列的操作:
    https://github.com/canglaodexiaohai/data-structure/blob/master/%E9%98%9F%E5%88%97

    展开全文
  • 层序遍历

    千次阅读 2019-09-13 08:36:36
    首先我们先了解一下什么是层序遍历层序遍历:进行层序遍历时,对某一层的节点访问完后,再按照他们的访问次序对各个节点的左孩子和右孩子顺序访问,这样一层一层进行,先访问的节点其左右孩子也要先访问,这正好...
  • 二叉树链式结构的遍历 所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算...
  • 层序遍历Java实现

    千次阅读 2019-10-05 10:28:11
    层序遍历Java实现 层序遍历是树的一种遍历方法 遍历过程 从根节点A开始,逐层从左到右遍历节点 遍历结果为A,B,C,D,E,F,G 代码实现 二叉树类创建 一个二叉树的节点,应具有节点值、左子树根节点引用和右子树根...
  • 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7...
  • 遍历一棵二叉树常用的有四种方法,前序(PreOrder)、中序(InOrder)、后序(PastOrder)还有层序(LevelOrder)。 前中后序三种遍历方式都是以根节点相对于它的左右孩子的访问顺序定义的。例如根-&gt;左-&...
  • 假设要构造的二叉树层序遍历序列存在一个数组里 1.只要数组不为空,就先入队数组首元素,并用这个值创建二叉树的root。 2.然后进入循环,队列不为空,就拿队头元素,对头再出队。队列为空,结束循环。 3.只要数组...
  • 层序遍历二叉树

    2017-01-14 13:15:19
    输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入 8 / / 6 10 / / / / 5 7 9 11 输出8 6 10 5 7 9 11。 queue m_queue; void visitByLevel(TNode* root) { ... m_
  • 在之前的多篇文章中,已经探讨过层序遍历二叉树了,本文稍作补充,讲述了借助循环队列来实现的情况。 具体实现如下:#include using namespace std; #define MAXSIZE 50typedef struct node { char data; struct...
  • 层序遍历二叉树 Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 ...
  • problem address Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], ...
  • 层序遍历二叉树指定的某层

    千次阅读 2016-06-02 14:58:01
    题目:写一个函数,打印二叉树中某层次的节点(从左到右),其中根节点为第0层,函数原型为int PrintNodeAtLevel(Node* root, int level),成功返回1,失败返回0。(一)递归解法 思路分析:假设要求访问二叉树中第...
  •  我们首先来看怎样对一颗二叉树进行层序遍历,下图所示的二叉树层次遍历的结果为[a,b,c,d,e],在这个过程中,我们首先保存根节点a,然后遍历a的左右节点b,d并保存下来,然后遍历b的左右子节点并保存,然后遍历d的子...
  • 层序遍历二叉树-C语言 具体代码 #include<stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef struct Node{ int data; struct Node *rchild,*lchild; }Node,*Tree; int TreeSize=0; ...
  • //层序遍历用队列,队列中不会出现null //删本身,进孩子 public static void levelOrderTraversal(TreeNode root) { //if (root == null) { // return; //} Queue<TreeNode> queue =...
  • 层序遍历二叉树的过程和层序生成二叉树的过程类似,都是要借助一个队列来实现。具体过程是: 将根结点入队 取出队首结点,访问该结点 若该结点的左孩子非空,则将左孩子入队 如果右孩子非空,将右孩子入队 重复过程2...
  • 比较简单,直接上代码 ... import java.util.LinkedList; /** * 层序遍历数组 * Author : BlueSky 2019.11.15 * 思路:利用队列实现 */ public class LayerTree { public void foreach(Tr...

空空如也

1 2 3 4 5 ... 20
收藏数 23,540
精华内容 9,416
关键字:

层序遍历