精华内容
下载资源
问答
  • public List<Integer> levelorder(Node root) { LinkedList<Node> input = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); ... in.
    public List<Integer> levelorder(Node root) {
    		 LinkedList<Node> input = new LinkedList<>();
    		 LinkedList<Integer> output = new LinkedList<>();
    	        if (root == null) {
    	            return output;
    	        }
    
    	        input.add(root);
    	        while (!input.isEmpty()) {
    	            Node node = input.pop();
    	            output.add(node.val);
    	            if (node.children != null) {
    		            for (Node item : node.children) {
    		            	input.add(item);
    		            }
    	            }
    	            
    	        }
    	        return output;
    	    }

     

    展开全文
  • 一个多叉树的层次遍历算法

    千次阅读 2008-12-09 21:48:00
    多叉树的层次遍历 这个在网上有完整程序的好像不多.这次我就把写的贴出来, 有兴趣的朋友一起来研究下. TreeNode.h 文件 #ifndef __TREENODE_ #define __TREENODE_ #include "StdAfx.h" #include #include #...
     最近学习c++,越看越觉得以前所学只是皮毛.这几天正好有空闲就写点小算法玩玩. 
    多叉树的层次遍历 这个在网上有完整程序的好像不多.这次我就把写的贴出来,
    有兴趣的朋友一起来研究下.
    TreeNode.h 文件
    #ifndef __TREENODE_
    #define __TREENODE_

    #include "StdAfx.h"
    #include <string>
    #include <list>
    #include <iostream>
    #include <queue>

    using namespace std;

    class TreeNode
    {
    private:
    long selfID;
    string nodeName;

    list<TreeNode*> *p_childList;
    public:
    TreeNode();

    ~TreeNode();

    /*向当前节点中插入一个子节点*/
        void insertChildNode(TreeNode *treeNode);

    /*遍历树,层次遍历*/
        void LevelTraverse() ;

    //判断某个节点是否为叶子节点
    bool isLeaf();

    //返回当前节点的孩子集合
    list <TreeNode*>* getChildList();

    long getSelfId();

    void setSelfId(long selfID);

    string getNodeName();

    void setNodeName(string &nodeName);
    };


    //返回当前节点的孩子集合
    inline list <TreeNode*>* TreeNode::getChildList()
    {
    return p_childList;
    }

    inline long TreeNode::getSelfId()
    {
    return selfID;
    }

    inline void TreeNode::setSelfId(long selfID)
    {
    this->selfID = selfID;
    }

    inline string TreeNode::getNodeName()
    {
    return nodeName;
    }

    inline void TreeNode::setNodeName(string &nodeName)
    {
    this->nodeName = nodeName;
    }

    #endif

    TreeNode.cpp 文件

    #include "stdafx.h"
    #include "TreeNode.h"

    TreeNode::TreeNode()
    {
    selfID = 0 ;

    nodeName = "";

    p_childList = NULL;

    }

    TreeNode::~TreeNode()
    {
    delete p_childList;
    }


    //判断某个节点是否为叶子节点
    bool TreeNode::isLeaf()
    {
    if (NULL == p_childList)
    {
      return true;
    }
    else
    {
      return false;
    }

    }

    /*向当前节点中插入一个子节点*/
    void TreeNode::insertChildNode(TreeNode *treeNode)
    {
    if (NULL==treeNode)
    {
      cout<<"treeNode is null !"<<endl;
      return;
    }
    if (isLeaf())
    {
      p_childList = new list<TreeNode*>;
    }
    p_childList->push_back((TreeNode*)treeNode);
    }

    /*遍历树,层次遍历*/
    void TreeNode::LevelTraverse()
    {
    queue<TreeNode*> queue ;

    queue.push((TreeNode*)this);

    TreeNode *p = NULL;

    while (!queue.empty())
    {
      p = queue.front();
      queue.pop();
      cout<<"treenode is: "<<p->getSelfId()<<endl;
      if (NULL!= p->getChildList())
      {
       list<TreeNode*>::iterator it = (p->getChildList())->begin();
       while(it!= (p->getChildList())->end())
       {
        queue.push((*it));
        ++it;
       }
      }
    }
    }

    测试代码:
    #include "stdafx.h"
    #include "TreeNode.h"
    int main(int argc, char* argv[])
    {
    TreeNode root;
    root.setSelfId(0);
    TreeNode *node1 = new TreeNode();
    TreeNode *node2 = new TreeNode();
    TreeNode *node3 = new TreeNode();
    TreeNode *node10 = new TreeNode();

    node10->setSelfId(10);

    node1->setSelfId(1);
    node2->setSelfId(2);
    node3->setSelfId(3);
    root.insertChildNode(node1);
    root.insertChildNode(node2);
    root.insertChildNode(node3);
    root.insertChildNode(node10);

    TreeNode *node4 = new TreeNode();
    TreeNode *node5 = new TreeNode();
    node4->setSelfId(4);
    node5->setSelfId(5);
    node1->insertChildNode(node4);
    node1->insertChildNode(node5);

    TreeNode *node6 = new TreeNode();
    TreeNode *node7 = new TreeNode();
    TreeNode *node8 = new TreeNode();

    node6->setSelfId(6);
    node7->setSelfId(7);
    node8->setSelfId(8);
    node4->insertChildNode(node6);
    node4->insertChildNode(node7);
    node4->insertChildNode(node8);

     //遍历
    root.LevelTraverse();
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    delete node8;
    return 0;
    }
    打印出来的结果是:

    0 1 2 3 10 4 5 6 7 8 (其中10是故意用来测试的)

    这个只是简单的测试,大家可以用模板来实现.
    这个算法有几个关键的地方: 
    1. list 中存放的是指针,好处就不用说了.如果不用指针的话,在delete时候会出现问题.原因大家也清楚.
    2. 用队列比 栈 实现起来要方便
    展开全文
  • 给出树的自下而上,自右到左的层次遍历算法 算法实现 void LevelOrder(BiTree T){ InitQueue(Q); InitStack(S); BiTree p; EnQueue(Q, T); while(!IsEmpty(Q)){ //自上而下,自左往右遍历 DeQueue(Q, p); ...

    问题:

    给出树的自下而上,自右到左的层次遍历算法

    算法实现

    void LevelOrder(BiTree T){
        InitQueue(Q);
        InitStack(S);
        BiTree p;
        EnQueue(Q, T);
        while(!IsEmpty(Q)){					//自上而下,自左往右遍历
            DeQueue(Q, p);
            Push(S, p);
            if(p->lchild != NULL){
                EnQueue(Q, p->lchild);
            }
            if(p->rchild != NULL){
                EnQueue(Q, p->rchild);
            }
        }
        while(!IsEmpty(Q)){					//逐个退栈,实现逆序:自下而上,自右到左
            Pop(S, p);
            visit(p->data);
        }
    }
    
    展开全文
  • 算法树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。对于这类题目,典型算法就是先将树按照层次存...

    算法:

    树的层次遍历是树的基本操作之一,包括二叉树的层次遍历,多叉树的层次遍历,以及二叉树层次遍历的变形题目,层次遍历+每一层的节点的翻转等操作。

    对于这类题目,典型算法就是先将树按照层次存入数组当中,然后统一对每一层的数据进行数据处理。

    题目1:

    102. 二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    代码实现:

    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
     /* 
     方法1:非递归操作
     */
     /*
    func levelOrder(root *TreeNode) [][]int {
        if root == nil {
            return nil
        }
        var stack []*TreeNode
        var result [][]int
        stack = append(stack,root)
        for {
            if len(stack) == 0 {
                break;
            }
            res,stack1 := helper(stack)
            if len(res) != 0 {
                result = append(result,res)
            }
            stack = stack1
        }
        return result
    }
    func helper(stack []*TreeNode)(res []int, stackRes []*TreeNode){
        if len(stack) == 0{
            return
        }
       
        for i:=0;i<len(stack); i++{
            node := stack[i]
            if node == nil {
                continue
            }
            res = append(res,node.Val)   
            stackRes = append(stackRes,node.Left)
            stackRes = append(stackRes,node.Right)
        }
        
        return
    }
    */
    /*
    解法:队列来操作,
    树的层次遍历,从左到右遍历树的每一层存入对应的数组即可
    */
    /*
    方法2:递归操作
    利用二叉树的先序遍历方法,也就是先访问根节点,在访问做左孩子,然后访问右孩子。
    */
    func levelOrder(root *TreeNode) [][]int {
        return preOrder(root, 0, [][]int{})
    }
    
    
    func preOrder(root *TreeNode, level int, res [][]int) [][]int  {
        if root == nil {
            return res
        }
        // 1.根节点的处理
        // 这里因为level从0开始计算的缘故,len放进去值之后就是1,所以==的时候,便是是新的一层开始
        if level == len(res) { 
            res = append(res,[]int{root.Val})
        } else {
            res[level] = append(res[level],root.Val)
        }
        // 2.左孩子节点的处理
        res = preOrder(root.Left,level+1,res)
        // 3.右孩子节点的处理
        res = preOrder(root.Right,level+1,res)
        return res
    }
    

    执行结果:

    题目2:

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

    代码实现:

    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    
    
    func levelOrderBottom(root *TreeNode) [][]int {
        r := [][]int{}
        order(root,0,&r)
        for i,j:= 0, len(r)-1;i<j;{
            r[i],r[j] = r[j],r[i]
            i++
            j--
        }
        return r
    }
    func order(root *TreeNode,level int,res *[][]int)  {
        if root == nil {
            return
        }
        if len(*res)-1 < level {
            *res = append(*res,[]int{root.Val})
        } else {
            (*res)[level] = append((*res)[level],root.Val)
        }
        
        order(root.Left,level+1,res)
        order(root.Right,level+1,res)
        return 
    }
    

    执行结果:

    题目3:

    https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

    代码实现:

    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func zigzagLevelOrder(root *TreeNode) [][]int {
        if root == nil {
            return nil
        }
        res := [][]int{}
        levelOrder(root,0, &res)
        for i:=0; i< len(res); i++ { 
            if i%2 == 1{
                j,k:=0,len(res[i])-1
                for j < k{
                    res[i][j],res[i][k] = res[i][k],res[i][j] 
                    j++
                    k--
                }
            }
        }
        return res
    }
    
    
    func levelOrder(root *TreeNode, l int, res *[][]int) {
        if root == nil {
            return 
        }
        if len(*res)-1 < l  {
            *res = append(*res,[]int{root.Val})
        } else {
            (*res)[l] = append((*res)[l],root.Val)
        }
        levelOrder(root.Left,l+1,res)
        levelOrder(root.Right,l+1,res)
     
        return 
    }
    // 需要: 先按照层次去遍历存储,然后统一的做整理,调整需要转换的对应层次
    

    结果输出:

    题目4.

    https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

    代码实现:

    /**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Children []*Node
     * }
     */
    
    
    func levelOrder(root *Node) [][]int {
        if root == nil {
            return nil
        }
        res := [][]int{}
        levelOrderOk(root,0,&res)
        return res
    }
    
    
    func levelOrderOk(root *Node,l int, res *[][]int){
        if len(*res)-1 < l {
            *res = append(*res,[]int{root.Val})
        } else {
            (*res)[l] = append((*res)[l],root.Val)
        }
        for _,t := range root.Children {
            levelOrderOk(t,l+1,res)
        }
        return 
    }
    

    执行结果:

    展开全文
  • 树的层次遍历与树的的深度遍历,都是用非递归的方法实现的
  • JAVA实现二叉树前序遍历、中序遍历、后序遍历和层次遍历算法 如图所示一颗二叉树,用JAVA实现二叉树前序遍历、中序遍历、后序遍历和层次遍历算法 定义节点 public class TreeNode { int data; TreeNode...
  • 【二叉树的层次遍历算法】  实现二叉树的层次遍历算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。  请利用二叉树算法库。[参考解答](btreee.h见算法库)#include #include ...
  • 树的层次遍历

    2019-10-02 17:19:24
    说到树的层次遍历,就应该提到广度优先搜索算法------广度优先搜索算法(Breadth-First-Search),又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种图形搜索算法。 可以说树层次遍历是广度优先遍历的一种直接...
  • 对于树的层次遍历是基本操作,话不多说,直接进正题..... 比如实现下面这个树的层次遍历 树的层次遍历.png 实现的结果应该是 [1],[2,3],[4,5,6,7] 实现该算法主要有以下四个步骤 先将树的根结点放入到队列中 ...
  • 树的遍历之层次遍历

    2019-12-30 19:35:53
    Leetcode 题 分析: 考察树的层次遍历 算法 int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) { if(!root) { *returnSize=0; return 0; } int **res=(in...
  • 本篇文章主要来讨论: 树的层次遍历 102. 二叉树的层序遍历 107. 二叉树的层序遍历 II 429. N 叉树的层序遍历 前中后序遍历使用的是DFS(深度优先搜索),而层次遍历使用的是BFS(广度优先遍历) DFS 要用到栈 BFS 要...
  • 二叉树的层次遍历算法 二叉树算法库请点击徐吉平二叉树算法库 /* * Copyright (c) 2015, 烟台大学计算机与控制工程学院 * All rights reserved. * 文件名称:main.cpp,btree.h,btree.cpp * 作者:徐吉平 * ...
  • 栈的应用:树的层次遍历、图的广度优先遍历、OS的FCFS策略树的层次遍历:图的广度优先遍历OS的FCFS策略: 树的层次遍历算法思想: 1、先遍历头节点1,头节点1入队 2、在遍历头节点的孩子节点23,让孩子节点23入队...
  • BFS算法(类似与树的层次遍历)

    千次阅读 2017-09-29 21:02:45
    //类似于树的层次遍历,借助于队来实现 bool visited[MaxV] void BFSTraverse(Graph G) //首先对图遍历,并标记visited为fasle(未访问状态)设访问结点函数为visit(); { for(int i = 0,i < G.vexn
  • #include #include #define N 30 typedef struct TNode *BiT; typedef struct SNode *Stack;... //从根节点开始,输出根节点,并将其入栈... printf("树的层次遍历:"); levelTraverse(T); return 0; }
  • 二叉树的层次遍历 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9...
  • 使用队列实现树的层次遍历

    千次阅读 2018-11-15 16:41:27
    对于树的层次遍历是基本操作,话不多说,直接进正题… 比如实现下面这个树的层次遍历 实现的结果应该是 [1],[2,3],[4,5,6,7] 实现该算法主要有以下四个步骤 先将树的根结点放入到队列中 计算每层的结点数目 遍历一...
  • /* ... *All rights reserved. *文件名称:ouyangdingtian.cpp *作 者:王百琛 *完成日期:2017年11月2日 ... *问题描述:层次遍历算法的验证 *输入描述:一棵 *程序输出:先序,中序,后序算法
  • 问题描述:层次遍历算法的验证    输入描述:无    输出描述:层次遍历树的结果    */      //btree2.h    #include  #define MaxSize 100  typedef char ElemType;    typedef ...
  • 这里提出用非递归遍历的原因是:用递归遍历虽然方便,但是不能递归太深,否则会 stack overflow先序遍历这里有两种遍历方法void PreOrder1(Btree*b) { stack&lt;node*&gt;s; Btree *p; //...
  • 二叉树(续) 三种层次遍历算法

    千次阅读 2015-05-16 14:37:35
    前言 ... 对于二叉树的层次遍历,我们很容易想到,如果能够输出每一层的节点,那么整棵树的层次遍历就只需要不断调用它即可,如下图: 层次遍历的结果为:  12  5 18  2 9 15 19  17
  • 问题及代码: /* 烟台大学计算机学院 ...问题描述:层次遍历算法的验证 输入描述:无 输出描述:层次遍历树的结果 */ btree2.h #include #define MaxSize 100 typedef char E
  • 二叉树各种非递归遍历中,要数后序比较麻烦了,因为即使左子树为空,也不能马上出栈,而是要判断右子。以下就给出代码: typedef struct Tnode{ ElemType data; struct Tnode *lchild,*rchild;}BBTnode,*BBTree...
  • 说明将层次遍历出队列元素入栈,最后出栈即可得 b本篇以根节点为8二叉搜索8、5、10、3、7、9、11为例 typedef struct Tree { int Data; struct Tree *Lc; struct Tree *Rc; }Btree; //节点 typedef...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,090
精华内容 436
关键字:

树的层次遍历算法