精华内容
下载资源
问答
  • 二叉树层次遍历

    2017-04-20 16:16:48
    对一棵二叉树进行层次遍历 实现思路: 利用队列,在队尾增加,队头删除。在访问每一层时,先记住这一层的rear ,然后访问该层的节点,同时访问结点的左右子树增加在在队尾。当访问到该层的最后一个节点时,记住该...

    问题描述:

    对一棵二叉树进行层次遍历

    实现思路:

    利用队列,在队尾增加,队头删除。在访问每一层时,先记住这一层的rear ,然后访问该层的节点,同时访问结点的左右子树增加在在队尾。当访问到该层的最后一个节点时,记住该队列rear的值。进行下一层的访问。

    代码:

    /**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
     class Solution {
        /**
         * @param root: The root of binary tree.
         * @return: Level order a list of lists of integer
         */
    public:
        vector<vector<int>> levelOrder(TreeNode *root) {
            // write your code here
            TreeNode *Q[100000];
            TreeNode *q;
            vector<vector<int>>vv;  
            int front,rear;
            int a;
            front=rear=-1;
            if(root==NULL) return vv;
            Q[++rear]=root;
            while(front!=rear) {
                vector<int> v;
                while(front<a) {
                q=Q[++front];
                v.push_back(q->val);
                if(q->left!=NULL) Q[++rear]=q->left;
                if(q->right!=NULL) Q[++rear]=q->right;}
                vv.push_back(v);
                a=rear;
            }
            return vv;
        }
    };

    感想:

    进行层次遍历时,利用队列,要先记住该层的节点访问完时此时a=rear的值,同时访问该层节点时还要把该层节点的左右儿子的节点的值加入队列中同时rear变化。当访问完该层节点时,同时a=此时的rear的值。接着访问下一层。


    展开全文
  • 二叉树层次遍历

    万次阅读 2015-04-23 09:16:14
    任务要求:输入一棵二叉树进行层次遍历,每个节点都按照从根节点到他的移动序列给出(L表示左,R表示右)。在输入中,每个节点的左右括号之间没有空格,相邻节点之间用一个空格隔开。每棵数的输入用一队空括号 () ...
    

           下面是对层次遍历的一个实例,如果对二叉树不太了解请点击这里,另外对于二叉树其他的三种遍历方式:请点击这里

    任务要求:输入一棵二叉树,进行层次遍历,每个节点都按照从根节点到他的移动序列给出(L表示左,R表示右)。在输入中,每个节点的左右括号之间没有空格,相邻节点之间用一个空格隔开。每棵数的输入用一队空括号 () 表示结束(这对括号本身并不代表一个节点),如图所示。

    (画的略丑)

    注意:如果从根到某个叶节点的路径上有的节点没有在输入中给出,或者给出超出了一次应当输出 -1.节点数不超过 256.

    样例输入:

    (11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

    (3,L) (4,R) ()

    样例输出:

    5 4 8 11 13 4 7 2 1

    -1

    代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXN 1500 + 100
    typedef struct TNode    //定义树结构
    {
        bool is_value;      //是否被赋值过
        int v;              //节点值
        TNode *left, *right;//左儿子和右儿子
    }Node;
    Node* root; //二叉树的根节点
    bool failed;
    int ans[MAXN],cnt;
    //功能:申请新节点并初始化
    Node* newnode(){
        Node* u = (Node*)malloc(sizeof(Node));
        if(u != NULL ){
            u->is_value = false;
            u->left = u->right = NULL;
        }
        return u;
    }
    //功能:程序运行结束之前先释放内存
    void remove_tree(Node* u){
        if(u == NULL) return ;
        remove_tree(u->left);
        remove_tree(u->right);
        free(u);
    }
    //功能:将给定的序列加入树,若不存在则使用newnode创建新节点
    void addnode(int v,char *s){
        int nLen = strlen(s);
        Node* u = root;             //从根节点往下走
        for(int i = 0; i < nLen; i++){
            if(s[i] == 'L'){
                if(u->left == NULL) u->left = newnode();    //节点不存在,建立新节点
                u = u->left;                    //往左走
            }else if(s[i] == 'R'){
                if(u->right == NULL) u->right = newnode();
                u = u->right;                   //往右走
            }
        }           //忽略其他情况,即最后那个多余的括号
        if(u->is_value) failed = true;  //已经赋过值,表明输入有误
        u->v = v;
        u->is_value = true;
    }
    void input_tree(){
        char s[MAXN];   //保存读入节点
        failed = false;
        root = newnode(); //创建根节点
        while(scanf("%s",s),strcmp(s,"()")){ //读到结束标志退出循环
            int v;
            sscanf(&s[1],"%d",&v);    //读入节点值
            addnode(v,strchr(s,',')+1);  //查找逗号,插入节点
        }
        return ;
    }
    bool bfs(){
        Node *q[MAXN],*u;
        q[0] = root;
        int front = 0, rear = 1;
        while(front < rear){
            u = q[front++];
            if(!u->is_value) return false;  //没有被赋过值,表明输入有误
            ans[cnt++] = u->v;                //增加到输出序列的尾部
            if(u->left != NULL) q[rear++] = u->left; //把左儿子放入队列
            if(u->right != NULL) q[rear++] = u->right;//把右儿子放入队列
        }
        return true;        //输入正确
    }
    int main(){
        while(1){
            cnt = 0;
            input_tree();
            if(!failed&&bfs()){      //判断是否有重复输入或者节点中断
                for(int i = 0; i < cnt; i++){   //按照层次遍历输出二叉树
                    if(i) printf(" ");
                    printf("%d",ans[i]);
                }
                printf("\n");
            }
            else
                printf("-1\n");
        }
        return 0;
    }
    

    展开全文
  • 题目的意思就是说第1层(根结点)从左边开始遍历,在第二层则从右边开始遍历,第三层又从左边开始如此递归下去,直到遍历完整棵二叉树; 如给定个二叉树的树组[1,2,3,4,null,null,5],null表示对应节点为空,则应该...

    题目的意思就是说第1层(根结点)从左边开始遍历,在第二层则从右边开始遍历,第三层又从左边开始如此递归下去,直到遍历完整棵二叉树;

    如给定一个二叉树的树组[1,2,3,4,null,null,5],null表示对应节点为空,则应该返回[[1],[3,2],[4,5]];详情可参考leetcode;
    二叉树节点的定义如下:

    public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }

    具体的解决思路:用一个flag来标记是将当前的节点前插到还是后插到当前层的list中,遍历完一层后,flag赋值为它的非。其余思想和二叉树的层次遍历一样,用队列来保存需要访问的元素,直到队列为空;

    LinkdeList中的add()方法可以指定插入的地点,默认add(object)是将元素插入到list已经存在的元素的后面,假设当前list中的元素为{1,2},则当我们执行完方法add(4)后,list中的元素位置为{1,2,4};;当我们指定插入的位置为0里add(0,object),则将元素插入到已有元素的前面,我们继续执行完add(0,5)后,则list中的元素就变为{5,1,2,4};

    具体的代码如下:

    public class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result=new LinkedList<List<Integer>>();
            Queue<TreeNode> nodeQueue=new LinkedList<TreeNode>();
            boolean flag=true;
            if(null==root){
                return result;
            }
            nodeQueue.offer(root);
            while(0!=nodeQueue.size()){
                int size=nodeQueue.size();
                List level=new LinkedList<Integer>();
                for(int i=0;i<size;i++){
                     root=nodeQueue.remove();
                     if(null!=root.left){
                        nodeQueue.offer(root.left);
                     }
                     if(null!=root.right){
                        nodeQueue.offer(root.right);
                     }
                    if(flag){
                      level.add(root.val);
                    }else{
                     level.add(0,root.val);
                    }
                }
                flag=!flag;
                result.add(level);
            }
            return result;
        }
    }

    代码在leetcode编译通过,我就不贴运行结果了

    转载于:https://www.cnblogs.com/WoodJim/p/4690545.html

    展开全文
  • 题目给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 样例给一棵二叉树 {3,9,20,#,#,15,7} : 返回他的分层遍历结果: 挑战挑战1:只使用一个队列去实现它 挑战2:用DFS算法来做 题解 1.单队列实现...

    二叉树的层次遍历
    1. 题目

      给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)

    2. 样例

      给一棵二叉树 {3,9,20,#,#,15,7} :
      这里写图片描述
      返回他的分层遍历结果:
      这里写图片描述

    3. 挑战

      挑战1:只使用一个队列去实现它
      挑战2:用DFS算法来做

    4. 题解

    1.单队列实现
    在对节点队列进行遍历时,要提前保存队列的长度n,而不要在循环中去动态获取。

    /**
     * Definition of TreeNode:
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left, right;
     *     public TreeNode(int val) {
     *         this.val = val;
     *         this.left = this.right = null;
     *     }
     * }
     */
    
    
    public class Solution {
        /**
         * @param root: The root of binary tree.
         * @return: Level order a list of lists of integer
         */
        public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
            ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
            if (root == null)
            {
                return list;
            }
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            while (!q.isEmpty())
            {
                ArrayList<Integer> arr = new ArrayList<Integer>();
                int n = q.size();
                for (int i=0;i<n;i++)
                {
                    TreeNode t = q.poll();
                    arr.add(t.val);
                    if (t.left != null)
                    {
                        q.add(t.left);
                    }
                    if (t.right != null)
                    {
                        q.add(t.right);
                    }
                }
                list.add(arr);
            }
    
            return list;
        }
    }

    2.DFS法

    /**
     * Definition of TreeNode: public class TreeNode { public int val; public
     * TreeNode left, right; public TreeNode(int val) { this.val = val; this.left =
     * this.right = null; } }
     */
    
    public class Solution
    {
        /**
         * @param root
         *            : The root of binary tree.
         * @return: Level order a list of lists of integer
         */
        public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root)
        {
            ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
            if (root == null)
            {
                return results;
            }
            int maxLevel = 0;
            while (true)
            {
                ArrayList<Integer> level = new ArrayList<Integer>();
                dfs(root, level, 0, maxLevel);
                if (level.size() == 0)
                {
                    break;
                }
    
                results.add(level);
                maxLevel++;
            }
    
            return results;
        }
    
        private void dfs(TreeNode root, ArrayList<Integer> level, int curtLevel,
                int maxLevel)
        {
            if (root == null || curtLevel > maxLevel)
            {
                return;
            }
    
            if (curtLevel == maxLevel)
            {
                level.add(root.val);
                return;
            }
    
            dfs(root.left, level, curtLevel + 1, maxLevel);
            dfs(root.right, level, curtLevel + 1, maxLevel);
        }
    }

    Last Update 2016.9.22

    展开全文
  • 原理 先序遍历 又可叫前根序遍历,先遍历根节点,再遍历根节点的左子树,然后遍历根节点的右子树...棵二叉树按从上到下,层按从左到右的顺序进行遍历。这里我们需要借助队列:先访问节点的孩子节点也应比后
  • 二叉树的锯齿形层次遍历

    千次阅读 2016-04-17 10:42:08
    题目描述:给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行) 样例: 如果之前的二叉树的层次遍历(详见我的博文:点击打开链接)你已经完全搞懂的话,这道题...
  • 1、实验题目 按层次(从上到下,从左到右的顺序)输入树的...要求构造一棵如下的二叉树,当二叉树构造成功后,需要进行先序遍历,后序遍历,中序遍历。   2、按层次构造树的两种方法 对于如下的一棵
  • 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度 题目分析 本题目就是最简单的二叉树遍历,我们可以用递归的方法,分别二叉树的左右...
  • 二叉树遍历

    2013-11-11 20:40:09
    建立一棵二叉树,试编程实现二叉树的如下基本操作:1. 按先序序列构造一棵二叉链表表示的二叉树T;2. 棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列;
  • 二叉搜索树在动态查表中有特别的用处,一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列, 构造树的过程即为无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点,在进行 插入操作...
  • 【问题描述】设计一个能够链式存储的二叉树进行先序、中序、后序遍历和层次遍历的演示程序。 【基本要求】从键盘输入数据,创建一棵二叉树,然后将结果输出。 【测试数据】输入的二叉树见教材127页图6.8(b)。 ...
  • 二叉树遍历   所谓遍历(Traversal)是指沿着某条搜索路线,依次树中每个...  从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行...
  • 白书介绍了对一棵二叉树进行层次遍历的过程,经过我的总结和优化之后,发表一篇博客在这里,留着忘记的时候回来看看。 题目如下: 按照某种方式输入一棵二叉树,然后从上到下、从左到右(按照层次)输出各结点...
  • 题目给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行) 样例给出一棵二叉树 {3,9,20,#,#,15,7}, 返回其锯齿形的层次遍历为: 题解 隔行层序遍历结果进行...
  • 9.2二叉树遍历

    2020-08-19 13:17:26
    一棵二叉树分为3个部分:根节点、左子树、右子树,且左子树和右子树同样进行这样的划分,这样树的遍历就可以分解为这3个部分的遍历。读者首先要记住一点,无论是这3种遍历的哪一种,左子树一
  • 主要思路是利用二叉树层次遍历的原理开始对二叉树进行层次遍历,特殊点在于遍历的时候将NULL也入队作为标记,如果当遍历到NULL的时候队列中仍然后feiNULL元素未被遍历,说明该二叉树中有非空点在空点的右边,即不是...
  • 在算法中,需要每个输入的字符进行判断,如果对应的字符是‘#’,则在相应的位置上构造一棵二叉树;否则,创建一个新结点。整个算法结构以先序遍历递归算法为基础,二叉树中结点之间的指针连接是通过指针参数在...
  • 所谓遍历(Traversal)是指沿着某条搜索路线,依次树中每个结点均做次且仅做次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之,是二叉树上进行其它运算之基础。 、先序...
  • (1)将一棵二叉树的所有结点存储在一维...(3)写出用二叉链表存储的二叉树进行层次遍历算法。 (4)求二叉树的所有叶子及结点总数。 //Sinhaeng Hhjian #include&lt;stdio.h&gt; #include&lt;st...
  • 怎么办呢,由于题目保证最终答案一定在int范围内,这时候在对一层的节点进行编号的时候,完全可以减去一个数字,最好的选择就是一个点的编号再减1。 /** * Definition for a binary tree node. * struct TreeNode ...
  • 我们首先来看怎样对一二叉树进行层序遍历,下图所示的二叉树层次遍历的结果为[a,b,c,d,e],在这个过程中,我们首先保存根节点a,然后遍历a的左右节点b,d并保存下来,然后遍历b的左右子节点并保存,然后遍历d的子...
  • 2. 棵二叉树进行遍历:中序、后序以及层次遍历序列,分别输出结点的遍历序列; 3. 求二叉树的深度/叶结点数目。 /* 输入二叉树的先序序列 例如:"abc de g f " --------------- */ #include #
  • 、【实验目的】 1、 了解二叉树的前序、中序、后序和层次序列排列;...创建个二叉树,动态二叉树进行分析,将其用静态二叉链表表示。二叉树的动态二叉链表结构中的每个结点有三个字段:dat...
  • 、【实验目的】 了解二叉树的前序、中序、后序和层次序列排列...创建个二叉树,动态二叉树进行分析,将其用静态二叉链表表示。二叉树的动态二叉链表结构中的每个结点有三个字段:data,lchild,rchild。...
  • 题目内容:二叉搜索树在动态查表中有特别的用处,一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列,构造树的过程即为无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点,在进行...

空空如也

空空如也

1 2 3 4 5
收藏数 98
精华内容 39
关键字:

对一棵二叉树进行层次遍历