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

    2020-09-06 19:43:25
    #include <iostream>...//新定义二叉树类型 typedef ElementType int; //用0表示没有结点 #define NoInfo 0 struct TNode{ ElementType data; BinTree left; BinTree Right; }; BinTree
    1. 树种结点的输入顺序:层序创建–>按树的从上至下从左右的顺序输入,各层的空结,点输入数值0。在构造二叉树过程中,需要一个队列暂时存储各结点的地址。
    2. 创建过程:
      1)输入第一个数据:
      若为0,表示是此树为空,将空指针赋值给根指针,树构 造完毕。
      若不为0,动态分配一个结点单元,并存入数据,同时将该结点地址放入队列。
      2)若队列不为空,从队列中取出一个结点地址,并建立该结点的左孩子:
      从输入序列中读入下一数据:
      若读入的数据为0,将出队结点的左孩子指针置空;否则,分配一个结点单元,存入所读数值,并将其置为出队结点的左孩子,同时将此孩子地址入队;
      接着再从输入序列中读入下一个数据:
      若读入的数据为0,将出队结点的右孩子指针置空;否则分配一个结点单元,存入所读数值,并将其置为出队结点的右孩子,同时将此孩子地址入队。
      3)重复 2)过程,直到队列为空,再无结点出队,构造过程到此结束。
      4)返回根结点地址
    #include <iostream>
    using namespace std;
    
    typedef struct TNode *Position;
    typedef Position BinTree;//新定义二叉树类型
    typedef ElementType int;
    //用0表示没有结点
    #define NoInfo 0 
    
    struct TNode{
        ElementType data;
        BinTree left;
        BinTree Right;
    };
    
    BinTree CreateBinTree(){
        ElementType data;
        BinTree BT, T;//BT用来创建新的结点, T用来接收出队结点
        Queue Q = CreateQueue();//创建空队列
        
        //建立第一个结点,即根结点
        scanf("%d", &data);
        
        if(data != NoInfo){
            //分配根结点单元,并将结点地址入队
            BT = (BinTree)malloc(sizeof(struct TNode));
            BT->data = data;
            BT->left = BT->Right = NULL;
            
            AddQ(Q, BT);
        }
        else
            return NULL;//若第一个数据是0,就返回空树
        
        while(!IsEmpty(Q)){//队列不空时,循坏
            T = Delete(Q);//从队列中取出一结点地址
            scanf("%d", &data);//读取T的左孩子
            if(data == NoInfo) 
                T->left = NULL;
            else{//分配新结点,出队结点的最孩子;新结点入队
                T->left = (BinTree)malloc(sizeof(struct TNode));
                T->left->data = data;
                T->left->left = T->left->right = NULL;
                AddQ(Q, T->left);
            }
            
             scanf("%d", &data);//读取T的右孩子
            if(data == NoInfo) 
                T->right = NULL;
            else{//分配新结点,出队结点的最孩子;新结点入队
                T->right = (BinTree)malloc(sizeof(struct TNode));
                T->right->data = data;
                T->right->left = T->right->right = NULL;
                AddQ(Q, T->right);
            }
            
        }
        
        return BT;//返回头结点地址
        
    }
    
    展开全文
  • public class Tree {//头节点private Nodehead;public NodegetHead() {return head;}public void setHead(Node head) {this....}/*** 层遍历* @param head 头节点*/public void floorPrint(Node head){//创建一个队...

    public class Tree {

    //头节点

    private  Nodehead;

    public NodegetHead() {

    return head;

    }

    public void setHead(Node head) {

    this.head = head;

    }

    /**

    * 层遍历

    * @param head  头节点

    */

    public  void  floorPrint(Node  head){

    //创建一个队列

    List queue=new LinkedList();

    queue.add(head);

    //队列不是空的,就一直循环

    while(!queue.isEmpty()){

    Node  n = ((LinkedList)queue).pop();

    //打印元素值

    System.out.println(n.getValue());

    if(Objects.nonNull(n.getLeft())){

    queue.add(n.getLeft());

    }

    if(Objects.nonNull(n.getRight())){

    queue.add(n.getRight());

    }

    }

    }

    public static  void main(String[]  args){

    Node  head =new Node("a");

    Node  son1 =new Node("b");

    Node  son2 =new Node("c");

    head.setLeft(son1);

    head.setRight(son2);

    Node  son3 =new Node("d");

    Node  son4 =new Node("e");

    son1.setLeft(son3);

    son1.setRight(son4);

    Node  son5 =new Node("f");

    Node  son6 =new Node("g");

    son2.setLeft(son5);

    son2.setRight(son6);

    Tree  t =new Tree();

    t.floorPrint(head);

    }

    }

    展开全文
  • 103. 二叉树的锯齿形层次遍历给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / 9 ...

    2764f5f372fec66ad1d788275cd84376.png

    103. 二叉树的锯齿形层次遍历

    给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

    示例: 给定二叉树 [3,9,20,null,null,15,7],

        3
       / 
      9  20
        /  
       15   7

    返回锯齿形层次遍历如下:

    [
      [3],
      [20,9],
      [15,7]
    ]

    作者:力扣 (LeetCode) 链接:https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    题解:

    本题还是基于层序遍历的框架,题目所说的锯齿遍历,就是一行是正序,一行是反序,这种情况设置一个count变量,来隔行判断本行应该正序还是反序存储。

    具体代码如下:

    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result = new LinkedList<>();
            if (root == null) {
                return result;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int count = 0;
    
            while (!queue.isEmpty()) {
                LinkedList<Integer> temp = new LinkedList<>();
                int len = queue.size();
                for (int i = 0; i < len; i++) {
                    TreeNode node = queue.poll();
                    if (count % 2 != 0) {
                        //头插元素,即逆序
                        temp.add(0, node.val);
                    } else {
                        temp.add(node.val);
                    }
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                count++;
                result.add(temp);
            }
            return result;
        }
    }
    展开全文
  • 前两天说过二叉树的前序遍历、中序遍历、后续遍历,把剩下的也都说了吧,二叉树遍历系列四,层次遍历。题目链接:二叉树层次遍历 - 力扣(LeetCode)​leetcode-cn.com题目描述:给定一个二叉树,返回其按层次遍历...

    d6357da87fb45db4a5ab69b7c052e81b.png

    前两天说过二叉树的前序遍历、中序遍历、后续遍历,把剩下的也都说了吧,二叉树遍历系列四,层次遍历。

    题目链接:

    二叉树的层次遍历 - 力扣(LeetCode)leetcode-cn.com
    bc242c77d1d18a31c14718fdaf5105c9.png

    题目描述:

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

    例如:
    给定二叉树: [3,9,20,null,null,15,7],

        3
       / 
      9  20
        /  
       15   7

    返回其层次遍历结果:

    [
      [3],
      [9,20],
      [15,7]
    ]

    解题思路:

    不同于之前前中后序使用栈的方法,层序遍历我们使用队列。如果一个节点有左右孩子,就把它的左右孩子 push 到队列中。

    代码如下:

    class Solution {
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
            if(!root) return {};
            vector<vector<int>> res;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()){
                vector<int> v;
                int size = q.size();
                for(int i = 0; i < size; ++i){
                    TreeNode* p = q.front();
                    v.push_back(p->val);
                    if(p->left) q.push(p->left);
                    if(p->right) q.push(p->right);
                    q.pop();
                }
                res.push_back(v);
            }
            return res;
        }
    };
    

    leetcode 里还有俩题也是关于二叉树的层次遍历的,一是二叉树的层次遍历 II,是把二叉树的元素按层次的顺序自底向上输出一遍,其实就是把本题最后的结果倒序一下就行了。二是二叉树的锯齿形层次遍历,就是先从左到右,再从右到左,注意按照奇偶性,倒序每一行的元素就行,其他部分和本题完全一致,所以就不单独写一篇了。

    如果有任何疑问,欢迎提出。如果有更好的解法,也欢迎告知。

    展开全文
  • 本以为树开始觉得差不多了,就是个递归或者用队列,没想到笔试居然要用层次遍历建立二叉树,然后按前序遍历输出,以前建树都是递归。所以这道题就gg,后来自己又想的做出来了 */ 题目意思是输入一个层次序列:0,1,2,3,...
  • java根据层次遍历建立二叉树

    千次阅读 2016-01-08 11:43:00
    层次遍历建立二叉树,这里使用的递归的方法,当然也可以建立一个队列来初始化这个二叉树! package Tree; import java.io.*; public class Erchashu { public static BTNode<Integer> BuildTree(int[] tree...
  • 给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。 Input 每个输入文件中一组数据。 第一行一个正整数N(1<=N<=30),代表二叉树的结点个数(结点编号为1~N)。接...
  • 二叉树采用二叉链表结构表示。设计并实现如下算法:输入某棵二叉树的广义表形式,建立二叉树,并按层次遍历二叉树
  • 1.二叉树层次遍历 2.二叉树结构图的打印 结语 1.二叉树层次遍历 主要用到队列操作,先入队根结点,再不断出队,判断出队结点是否有左右孩子,有则入队,直到队列空为止。 层次遍历挺简单,但是如果要输出结点...
  • 层次遍历构造二叉树 java

    千次阅读 2017-06-03 17:06:44
    层次遍历构造二叉树给定层次遍历的数组顺序,注意是完全二叉树形态的数组,空节点用 # 号代替。代码如下:// ----- import java.util.Scanner;class TreeNode { int val; TreeNode left; TreeNode right; ...
  • 层次遍历输出二叉树

    2020-08-14 22:22:06
    利用层次遍历算法,输出二叉树的各个结点.说明:需事先利用括号扫描法创建一个二叉链bt,该二叉树bt的括号表示法对应的字符串为"A(B(D(G),H),C(E(F,I)))" #include "stdio.h" #include "stdlib.h" #include "ctype.h...
  • C++层次遍历输入二叉树(用STL) 在设置队列的时候,注意类型是queue<Node *> Tqueue,如果不写星号,push时会创建一个新的节点入队,这样整棵树就不是连通的;而加了星号,是把指针地址入队,所以在操作的...
  • 中序遍历,层次遍历构建二叉树

    千次阅读 2017-03-01 10:37:59
    问题 C: 还原二叉树时间限制: 1 Sec内存限制: 128 MB提交: 324解决: 155提交状态题目描述给一棵二叉树的层序遍历序列和中序遍历序列,求这棵二叉树的先序遍历序列和后序遍历序列。输入每个输入文件中一组数据。...
  • 层次遍历构建二叉树

    千次阅读 2017-05-22 21:00:49
    struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };TreeNode* createTree(vector<string> nodes) { int len
  • 二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立二叉树。 前提知识: 约定: 约定二叉树的内容为int类型,并且都>=1,0...
  • /** 15 15 7 20 -1 -1 3 12 -1 -1 -1 -1 14 8 -1 -1 2 4 */ import java.util.*; public class Main2 { static int[] value ; static class TreeNode{ int val; TreeNode left,right;... t.
  • 给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式: 输入第一行给出一个正整数NN(\le 30≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。...
  • 掌握二叉树的二叉链表存储结构;...设计并实现如下算法:输入某棵二叉树的广义表形式,建立二叉树,并按层次遍历二叉树----队列形式   #include #include #include #define STACK_MAX_SIZ
  • 不管是二叉树建立 求前遍历 后遍历 还是层次遍历,都是利用中序遍历的性质 和一个前序遍历或后序遍历,讲一个节点的左支所有的数,右支所有的数,和该节点的数分开,然后根据题目重新排序; 前序遍历:该节点的...
  • bfs 和 队列学过数据结构的都知道,二叉树层次遍历层次遍历利用的数据结构是队列。那么,思考一下为什么层次遍历,要用到队列,而不是其他的数据结构,比如栈呢?换句话说,队列在二叉树层次遍历过程中起到了...
  • 给出一个层次遍历,和一个中序遍历的结果字符串 层次 A B C D E F G 中序 D B A F E G C 其对应的二叉树是:  A  / /  B C  / /  D E  / /  F G 【算法思想】 用LEV代表层次遍历MID代表中序...
  • 根据先序遍历和中序遍历创建二叉树
  • #include #include using namespace std; //二叉树结点结构 typedef struct BiTNode{ char ch; //结点数据 struct BiTNode *lchild; //左孩子 struct BiTNode *rchild;
  • 输出利用先序遍历创建的二叉树的层次遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...
  • 输出利用先序遍历创建的二叉树的层次遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...
  • 输出利用先序遍历创建的二叉树的层次遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的层次遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...
  • 层次遍历二叉树

    2015-06-29 23:17:51
    层次遍历二叉树 void CreateBiTree(BiTree &T) //先序法建立二叉树 { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTree)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch;...
  • 层次遍历数组建立二叉树

    千次阅读 2018-10-06 11:26:06
    层次遍历数组建立二叉树 约定:层次遍历数组中为空的结点记为0 解析 使用递归,检查每个结点的左右结点是否存在,存在即分配结点,并递归检查该结点。 void insert(TreeNode *p, vector&lt;int&gt; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,174
精华内容 8,469
关键字:

层次遍历创建二叉树