精华内容
下载资源
问答
  • 按照层序遍历建树是树的基本操作之一。通常用创建队列,逐层加入元素检查某层是否满,直到发现空位置的方法解决。本代码增加一种输入’#'字符的情况,表明该节点存储的数据为空。 #构造二叉树并实现访问操作,输入#...

           按照层序遍历建树是树的基本操作之一。通常用创建队列,逐层加入元素检查某层是否满,直到发现空位置的方法解决。本代码增加一种输入’#'字符的情况,表明该节点存储的数据为空。

    #构造二叉树并实现访问操作,输入#代表树中相应节点的数据是none
    #本题的二叉树是用层序构建的
    
    #节点类
    class Node():
        def __init__(self,elem = 0):
            #节点存储的数据,加_以便【用property添加私有属性】
            self._elem = elem
            #左孩子
            self.lchild = None
            #右孩子
            self.rchild = None
        #property创建类中的_elem变量的一个属性:
        #如果elem存储#字符,那么节点虽然存在,但存储数据是空;否则,elem就存储输入的数据
        @property
        def elem(self):
            if self._elem is '#':
                return None
            return self._elem
    #二叉树类,包含添加元素和判断树是否存在的功能
    class Mytree():
        """初始化二叉树。没有输入根节点数据就建立空根节点,有输入就建立相应数据的根节点"""
        def __init__(self,root = None):
            self.root = root
        #为树添加节点,传入参数为普通数据
        def add(self, elem):
            #将输入转化为节点,便于连接
            node = Node(elem)
            # 如果树根是空的,把这个节点放在根
            if self.root == None:
                self.root = node
            #树不空,需要逐层从左向右遍历,直到找到空位置插入。
            else:
                #创建一个队列,队列元素是节点。
                queue = [self.root]
                #如果这个队列中有东西,就要检查这里面的左右孩子节点是不是空的,如果不空的话加入队列中
                while queue:
                    # 每次操作的循环只弹出队列第一个元素,检查。
                    #在还未遍历完某层时,后一个弹出元素是第一个弹出元素的右侧节点。
                    #遍历完某层、确定这层的节点都非空后,才会从队列弹出下一层的节点。
                    #检查节点时,先检查这个节点是不是空,顺便将左右孩子加入队列。
                    #以便以后发现当前检查的层的节点全部非空时可以通过队列进入下一层。
                    cur = queue.pop(0)
                    #当前节点左孩子为空,待插节点就安在左孩子
                    if cur.lchild == None:
                        cur.lchild = node
                        #插入完成,不可继续执行,退出函数
                        return
                    #左孩子不空,如果右孩子空,待插节点就安在右孩子
                    elif cur.rchild == None:
                        cur.rchild = node
                        #插入完成,不可继续执行,退出函数
                        return
                    #上两步都没有return,说明左右都不空。
                    #此时需将当前位置节点左右孩子先后加入队列中等待判断。
                    else:
                        queue.append(cur.lchild)
                        queue.append(cur.rchild)
                    
    
    #测试
    if __name__=='__main__':
        MyTree = Mytree()
        #输入层序遍历的列表,有'#'不转化成int类型。
        lista = list(input().split())
        #逐个将列表元素插入到树中
        for i in range(len(lista)):
            MyTree.add(lista[i])
    #检测程序,N为检测操作语句的数量
    N = int(input())
    for i in range(N):
         #每次输入一个python语句,eval用来执行,输入n次
         eval(input())
    

    测试结果:
    在这里插入图片描述

    展开全文
  • 二叉树遍历序列还原·已知中序遍历和层序遍历题目信息输入输出测试样例解答思路 题目信息 给出二叉树的中序遍历序列和层序遍历序列,编程还原该二叉树。 输入 第1行:二叉树的中序遍历序列 第2行:二叉树层序遍历...

    二叉树遍历序列还原·已知中序遍历和层序遍历

    题目信息

    给出二叉树的中序遍历序列和层序遍历序列,编程还原该二叉树。

    输入

    第1行:二叉树的中序遍历序列
    第2行:二叉树的层序遍历序列

    输出

    二叉树的前序遍历序列

    测试样例

    ABCDEFG
    DBAFEGC
    
    ABDCEFG
    

    解答

    #include <iostream>
    #include <stack>
    #include <string>
    #include <queue>
    
    using namespace std;
    
    struct BTreeNode
    {
        char data;
        BTreeNode *Left;
        BTreeNode *Right;
    };
    
    void Lev_Mid_Restore(string lev, string mid, BTreeNode *result)
    {//层序中序遍历还原
        int size = lev.size();
        BTreeNode *helper[size];
        for (int i = 0; i < size; i++)
        {
            helper[i] = new BTreeNode;
            helper[i]->data = 0;
            helper[i]->Left = NULL;
            helper[i]->Right = NULL;
        }
        /*            0  1  2  3  4  5  6  7
            helper    0  0  A  0  0  0  0  0
            Left      0  0  0  0  0  0  0  0
            Right     0  0  0  0  0  0  0  0
        */
        //此处用来构建根节点
        result->data = lev[0];
        result->Left == NULL;
        result->Right = NULL;
        //将根节点加入到上面的表格中
        int LevIndex = mid.find(lev[0]);
        helper[LevIndex] = result;
    
        bool flag = false;
        for (int i = 1; i < lev.size(); i++)
        {//开始从层序遍历中一个一个去读取字符
            flag = false;
            //把这个节点放到对应的数组位置中
            LevIndex = mid.find(lev[i]);
            helper[LevIndex]->data = lev[i];
            /*从当前节点X的左边开始找,如果找到一个非0的节点Y,
              就判断其右孩子是否为空,如果为空,则X是Y的右孩子,并且孩子配对成功,
              接下来就不需要再向右找了。
              如果Y已经有右孩子了,则从节点X的右边开始找
            */
            for (int p = LevIndex - 1; p >= 0; p--)
            {
                if (helper[p]->data != 0)
                {//特别提醒,此两个if不能并列放置,理由是因为,遍历的时候不能碰到之前的值,也就是所谓的中值
                    if (helper[p]->Right == NULL)
                    {
                        helper[p]->Right = helper[LevIndex];
                        flag = true;
                    }
                    break;//一旦碰到要立马停止
                }
            }
            if (flag)
            {
                continue;
            }
            /*从当前节点X的右边还是找,如果找到一个非0的节点Y
              判断其左孩子是否为空,如果为空,则X是Y的左孩子
              如果Y已经有左孩子了,则说明这个中序/层次遍历序列有问题
            */
            for (int p = LevIndex + 1; p < size; p++)
            {
                if (helper[p]->data != 0)
                {
                    if (helper[p]->Left == NULL)
                    {
                        helper[p]->Left = helper[LevIndex];
                        flag = true;
                    }
                    break;
                }
            }
            //因为既然到了这一步,还没有配对成功,就说明给的中序/层次遍历序列有问题
            if (!flag)
            {
                cout << "error: " << lev[i] << endl;
                break;
            }
        }
    }
    
    void preorderTree(BTreeNode *Node)
    {//前序遍历(根左右)
        if (Node != NULL)
        {
            cout << Node->data;
            preorderTree(Node->Left);
            preorderTree(Node->Right);
        }
    }
    
    int main()
    {
        //freopen("/Users/zhj/Downloads/test.txt", "r", stdin);
        string lev, mid;
        cin >> lev >> mid;
        BTreeNode *Root = new BTreeNode;
        Lev_Mid_Restore(lev, mid, Root);
        preorderTree(Root);
    }
    

    思路

    这里我们假设
    中序为:DBAFEGC
    层序为:ABCDEFG
    在这里插入图片描述
    这里我们使用一个HLP数组用来存放节点指针,其对应于中序遍历字符串
    (1) 起始状态

    MIDDBAFEGC
    0123456
    HLP0000000
    L0000000
    R0000000

    这里的L/R代表了该节点是否有左右孩子,HLP存放的是节点指针
    (2) [A]BCDEFG
    因为是层序遍历,所以此时的A便是该序列的根节点,所以我们查找A在MID中的位置,创建一个节点到对应位置,这里我们就找到了此时的根节点,初创建的节点没有左右孩子。

    MIDDBAFEGC
    0123456
    HLP00A0000
    L0000000
    R0000000

    (2) A[B]CDEFG
    此时我们拿到了B这个节点,因为同辈节点只能有一个,所以B节点一定是A节点的子节点,此时我们找到B在MID中的位置,并先向左面找有没有非0的指针,在这里我们没有找到。然后从B的右边开始找有没有非0的指针,找到了A。发现A没有孩子节点,那么令B为A的左孩子。

    MIDDBAFEGC
    0123456
    HLP0BA0000
    L002B0000
    R0000000

    (3) AB[C]DEFG
    同上找到C,发现C是A的右孩子

    MIDDBAFEGC
    0123456
    HLP0BA000C
    L002B0000
    R006C0000

    (4) ABC[D]EFG
    同上找到D,发现D是B的左孩子

    MIDDBAFEGC
    0123456
    HLPDBA000C
    L00D2B0000
    R006C0000

    (5) ABCD[E]FG
    这里有些不同,因为E向左找发现A已经有了右孩子,所它必须向
    右找,结果发现E是C的左孩子。

    MIDDBAFEGC
    0123456
    HLPDBA0E0C
    L00D2B0004E
    R006C0000

    (6) ABCDE[F]G
    同上,F做不了A的右孩子,只能做了E的左孩子

    MIDDBAFEGC
    0123456
    HLPDBAFE0C
    L00D2B03F04E
    R006C0000

    (7) ABCDEF[G]
    G向左找,发现G可以做E的右孩子

    MIDDBAFEGC
    0123456
    HLPDBAFEGC
    L00D2B03F04E
    R006C05G00

    到此为止ABCDEFG的关系都已经建立好了,二叉树还原完成。
    此时也可以根据类似于静态数组存储方式来构建二叉树:静态数组存储构建二叉树,或者根据本题目中给出的解答方式也可。
    至于为什么我们一定要先从左开始找,然后再向右找,也许是因为二叉树的中序遍历它本身就是从左到右的吧。

    相关题目

    二叉树先序,中序,后序,层序遍历还原

    展开全文
  • //层序遍历首先考虑什么是层序遍历 // 是需要一层一层的进行打印 /*1.我们先创建一个队列(先进先出) 2.当根节点不为null的时候,我们将root放入队列中。 3.这个时候我们需要使用循环来遍历 遍历的条件就为这个...
        //层序遍历首先考虑什么是层序遍历
        // 是需要一层一层的进行打印
        /*1.我们先创建一个队列(先进先出)
        2.当根节点不为null的时候,我们将root放入队列中。
        3.这个时候我们需要使用循环来遍历  遍历的条件就为这个队列不为空
        4.此时栈中只有一个根节点我们将这个根节点记录并pop然后打印
        5.打印完后你会发现我们已经将第一层输出了,我们需要将每一层输出
        输出的话就用刚才记录下的cur的节点如果不为空将其的左右子树依次放入队列中(再次提醒队列的性质)
        不断的进行pop和打印最后就会将我们所有的元素按层进行遍历
        * */
        void levelOrderTraversal(Node root) {
            Queue<Node> queue=new LinkedTransferQueue<>();
            if (root!=null){
                queue.offer(root);
            }
            while (!queue.isEmpty()){
                Node cur=queue.poll();
                System.out.print(cur.value+" ");
                //这个循环加这两个判断是非常合适的
                // 不空就放入,空就跳过,一个循环pop一个非常厉害
                if (cur.left!=null){
                    queue.offer(cur.left);
                }
                if (cur.right!=null){
                    queue.offer(cur.right);
                }
            }
        }
    
        //二叉树的分层遍历
        /*
        * 1.首先我们需要分析是一个嵌套式。
        * 2.使用到的方法就是队列,然而每组循环结束后,队列中所存在的元素就是这一层元素
        * 3.将需要打印的每一组元素放在一个数组中
        * 4.然后我们将这些数组再放到一个二维数组中
        * */
        List<List<Character>> levelOrder(Node root) {
            List<List<Character>> ret = new ArrayList<>();
            Queue<Node> queue = new LinkedList<>();
            if (root != null) {
                queue.add(root);
            }
            while (!queue.isEmpty()) {
                int count = queue.size();//记录我们目前元素有几个方便在出栈过程中的循环次数
                List<Character> list = new ArrayList<>();
                while (count > 0) {
                    Node cur = queue.poll();
                    System.out.print(cur.value + " ");
                    list.add(cur.value);
                    if (cur.left != null) {
                        queue.add(cur.left);
                    }
                    if (cur.right != null) {
                        queue.add(cur.right);
                    }
                    count--;
                }
                ret.add(list);
            }
            return ret;
        }
    
    展开全文
  • 由完全二叉树层序遍历(上述的numbers[])构建完全二叉树,并输出其前序遍历已验证正确性。 二、2种方法实现 1.递归实现(DFS) (1)常识 :若给一棵完全二叉树(n个结点)的每个结点按层序遍历顺序进行编号(从1开始),记...

    一、问题描述
    input :

    #define emp -1
    int numbers[] = {4, 2, 7, 1, emp, emp, 9};
    

    output:
    由完全二叉树的层序遍历(上述的numbers[])构建完全二叉树,并输出其前序遍历已验证正确性。

    二、2种方法实现
    1.递归实现(DFS)
    (1)常识 :若给一棵完全二叉树(n个结点)的每个结点按层序遍历顺序进行编号(从1开始),记一结点的编号为a(1 ≤ a ≤ n),若其左孩子存在(∈[1, n]),则编号为 2 ∗ a 2 * a 2a,若其右孩子存在(∈[1, n]),则编号为 2 ∗ a + 1 2 * a + 1 2a+1
    (2)核心代码如下:

    void createFullBT_DFS(Node *&root, int numbers[], int len, int i) {
        if(i <= len) {
            root->value = numbers[i - 1];
            if(2 * i <= len && numbers[2 * i - 1] != emp) {
                root->left = createNode();
                createFullBT_DFS(root->left, numbers, len, 2 * i);
            }
            if((2 * i + 1) <= len && numbers[2 * i] != emp) {
                root->right = createNode();
                createFullBT_DFS(root->right, numbers, len, 2 * i + 1);
            }
        }
    }
    

    2.队列实现
    (1)思路:和用队列实现层次遍历的思路相似
    (2)核心代码如下:

    void createFullBT_queue(Node *&root, int numbers[], int len) {
        if(len == 0)
            return;
        else {
            queue<Node *> Q;
            int i = 0;
            root = createNode();
            root->value = numbers[i++];
            Q.push(root);
            while(!Q.empty()) {
                Node *temp = Q.front();
                Q.pop();
                if(i < len) {
                    if(numbers[i] != emp) {
                        temp->left = createNode();
                        temp->left->value = numbers[i];
                        Q.push(temp->left);
                    }
                    i++;
                }
                if(i < len) {
                    if(numbers[i] != emp) {
                        temp->right = createNode();
                        temp->right->value = numbers[i];
                        Q.push(temp->right);
                    }
                    i++;
                }
            }
        }
    }
    

    三、完整代码

    #include <iostream>
    #include <queue>
    using namespace std;
    #define emp -1
    struct Node {
        int value;
        Node *left;
        Node *right;
    };
    
    Node* createNode() {
        Node *node = new Node;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
    
    //采用递归实现
    void createFullBT_DFS(Node *&root, int numbers[], int len, int i) {
        if(i <= len) {
            root->value = numbers[i - 1];
            if(2 * i <= len && numbers[2 * i - 1] != emp) {
                root->left = createNode();
                createFullBT_DFS(root->left, numbers, len, 2 * i);
            }
            if((2 * i + 1) <= len && numbers[2 * i] != emp) {
                root->right = createNode();
                createFullBT_DFS(root->right, numbers, len, 2 * i + 1);
            }
        }
    }
    
    //采用队列实现;
    void createFullBT_queue(Node *&root, int numbers[], int len) {
        if(len == 0)
            return;
        else {
            queue<Node *> Q;
            int i = 0;
            root = createNode();
            root->value = numbers[i++];
            Q.push(root);
            while(!Q.empty()) {
                Node *temp = Q.front();
                Q.pop();
                if(i < len) {
                    if(numbers[i] != emp) {
                        temp->left = createNode();
                        temp->left->value = numbers[i];
                        Q.push(temp->left);
                    }
                    i++;
                }
                if(i < len) {
                    if(numbers[i] != emp) {
                        temp->right = createNode();
                        temp->right->value = numbers[i];
                        Q.push(temp->right);
                    }
                    i++;
                }
            }
        }
    }
    
    void preOrder(Node *root) {
        if(root != NULL) {
            cout << root->value << " ";
            preOrder(root->left);
            preOrder(root->right);
        }
    }
    
    int main() {
        int numbers[] = {4, 2, 7, 1, emp, emp, 9};   //已知完全二叉树的层序遍历,构建完成二叉树。
        int len = sizeof(numbers) / sizeof(numbers[0]);
        //递归实现
        //Node *root = createNode();
        //createFullBT_DFS(root, numbers, len, 1);
        //队列实现
        Node *root = NULL;
        createFullBT_queue(root, numbers, len);
        //验证建树是否正确;
        preOrder(root);
        return 0;
    }
    

    运行结果如下所示:
    在这里插入图片描述

    展开全文
  • 先根,后子树;先左子树,后右子树 ...g的子树的根节点入队(为空)结束层序遍历,整个过程就是一层层的遍历,依靠一个队列来存放临时查找的结点。 二叉树线索化 问题的提出:当以二叉链表作为存...
  • 先根,后子树;先左子树,后右子树 二叉树的根节点 a 入队 a 的子树,根节点 b 和 c 分别入队 然后 b 的子树的根节点入队(为空...g的子树的根节点入队(为空)结束层序遍历,整个过程就是一层层的遍历...
  • 并用C语言实现了根据前序扩展序列创建二叉树,前序遍历、中序遍历、后序遍历的递归遍历和非递归遍历,层序遍历以及打印二叉树的叶子结点,求二叉树的高度,根据前序序列、中序序列建立二叉树和根据中序序列、后序...
  • sdut原题链接数据结构实验之二叉树五:层序遍历 Time Limit: 1000MS Memory Limit: 65536KBProblem Description 已知一个按先序输入的字符序列,如abd,,eg,,,cf,,,(其中,表示空结点)。请建立二叉树并求二叉树的...
  • 请高手解释一下二叉树的层次遍历的精髓,最好是能用数学思维的,不只是设计一个算法层序遍历二叉树(同一层从左到右访问)。思想:用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 void HierarchyBiTree...
  • int Btdepth(Bitreee T){ if(!T) return 0; //如果是空树,则高度为1; int front =-1,rear=-1; //定义顺序队列,队列元素是二叉树结点指针,用于层序访问链式二叉树; BiTree Q[MaxSize]; ...
  • 给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。 示例: 二叉树:[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其层次遍历结果: [ [3], [9,20], [15,...
  • 层序遍历二叉树

    千次阅读 2014-11-23 16:18:45
    层序遍历二叉树直接输入数据,建立二叉排序树,利用队列层序输出即可,没什么难度 贴下自己的代码 //功能:层序遍历二叉树 //时间:2014-11-23 #include #include using namespace std; //二叉链表数据结构...
  • 在学习树的过程中发现,他们都有一个共同的特点,无论是在创建时还是遍历时,都是需要先父母再左孩子右孩子的...1.层序遍历 思路:刚才分析时我们发现可用队列,第一步,若根节点不为空我们先让根节点入队,判断他的左
  • 1024,节点编号1~N)的层序和中序遍历,输出T从左向右叶子节点以及树先序和后序遍历序列 输入描述: 输入两行,分别代表层序和中序遍历结果,节点编号按单个空格分开 输出描述: 依次输出 从左向右叶子节点 ,先序, ...
  • 通过上机实践,帮助学生进一步掌握指针变量和动态变量的含义,掌握二叉树的结构特性,以及各种存储结构的特点及适用范围,掌握用指针类型描述、访问和处理二叉树的...2 先建立二叉树的二叉链表存储结构,再遍历它。
  • 层序遍历意思就是按照从上往下,从左往右的顺序遍历二叉树的元素。 实现二叉树层序遍历需要用到二叉树和队列。 总体思路: 判断当前队列是否为空 队列为空:结束。队列非空:取出队列第一个元素 将取出的元素的两...
  • 1.完全二叉树的概念是在层序遍历的基础上建立的,层序遍历就是从上而下一层层遍历,每层是从左到右遍历。 2.如果有一个节点的左孩子不存在,右孩子却存在,那么必定不是完全二叉树 3.当出现某一个节点的左右孩子不是...
  • 1 已知二叉树以二叉链表作为存储结构,写一个算法按层序遍历它,通过程序在终端屏幕上打印出它的层序序列。 2 先建立二叉树的二叉链表存储结构,再遍历它。 3 利用队列完成算法。
  • 01 如何实现二叉树 首先定义树的结点 public class Node { public int data; public Node left; public Node right; public Node (int data){ this.data=data; this.left=null; this.right...
  • 二叉树递归创建:本质上和二叉树递归遍历一样,但是当需要知道何时节点孩子为空,因此这里用#做分隔符。先序建立:先给当前节点分配数据,然后创建左子树,然后创建又子树。 public Node createTree(){//递归先序...

空空如也

空空如也

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

层序遍历建立二叉树