精华内容
下载资源
问答
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    二叉树层序遍历 1、算法思想 用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点...此过程不断进行,当队列为空时,二叉树层次遍历结束...

    二叉树层次遍历

    层次遍历基础需要了解二叉树、队列。
    二叉树基本运算:https://blog.csdn.net/weixin_42109012/article/details/92000919
    顺序队基本运算:https://blog.csdn.net/weixin_42109012/article/details/92104948

    1. 算法思想

    用一个队列保存被访问的当前节点的左右孩子以实现层次遍历。
    在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点开始,首先将根节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作:

    1. 访问该元素所指向的节点
    2. 若该元素所指节点的左右孩子节点非空,则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行,当队列为空时,二叉树的层次遍历结束。

    2. 原理解释

    2.1. 二叉树图

    一个二叉树,层次遍历就是每一行每一行的取出数据。
    这个图的结果就是 ABCDEFGH
    在这里插入图片描述

    2.2. 层次遍历过程图

    就是先父节点进入队列,然后循环,出队时带入下一组子节点进队,没有就没有进入队列的,当队列为空时结束循环。
    在这里插入图片描述

    3. 代码实现

    3.1 实现步骤

    1、首先将二叉树的根节点进入队列中,判断队列不为NULL。
    2、打印输出该节点存储的元素。
    3、判断节点如果有孩子(左孩子、右孩子),就将孩子进入队列中。
    4、循环以上操作,直到 BT->lchild == NULL、BT->rchild=NULL。

    3.2 全部代码

    #define _CRT_SECURE_NO_WARNINGS // VS忽略警告,其它应该不需要
    
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_SIZE 128
    #define STR_SIZE 1024
    
    typedef struct Node {    // 定义二叉链
        char         data;   // 数据元素
        struct Node* lchild; // 指向左孩子节点
        struct Node* rchild; // 指向右孩子节点
    } BTNode;                // struct Node 的别名
    
    typedef struct Quene {      // 定义顺序队
        int     front;          // 队头指针
        int     rear;           // 队尾指针
        BTNode* data[MAX_SIZE]; // 存放队中元素
    } SqQueue;                  // struct Queue 的别名
    
    /**
     * 队列函数
     */
    void initQueue(SqQueue** q);             // 初始化队列
    bool emptyQueue(SqQueue* q);             // 判断队列空
    bool enQueue(SqQueue* q, BTNode* node);  // 入队
    bool deQueue(SqQueue* q, BTNode** node); // 出队
    
    /**
     * 二叉树函数
     */
    // void createBTNode2(BTNode** BT);                  // 创建二叉树
    int  createBTNode(BTNode** BT, char* str, int n); // 创建二叉树
    void preOrder(BTNode* BT);                        // 前序遍历
    void inOrder(BTNode* BT);                         // 中序遍历
    void postOrder(BTNode* BT);                       // 后序遍历
    void levelOrder(BTNode* BT);                      // 层次遍历
    
    /**
     * 画树函数
     */
    void draw_level(BTNode* node, bool left, char* str); // 画分支
    void draw(BTNode* root);                             // 画根节点
    
    /***************************************************************************
     * @date    2019/12/08
     * @brief   层次遍历二叉树
     * @param   BT  二叉树根节点
     ***************************************************************************/
    void levelOrder(BTNode* BT) {
        SqQueue* q;       // 定义队列
        initQueue(&q);    // 初始化队列
        if (BT != NULL) { // 根节点指针进队列
            enQueue(q, BT);
        }
        // 一层一层的把节点存入队列,当没有孩子节点时就不再循环
        while (!emptyQueue(q)) {      // 队不为空循环
            deQueue(q, &BT);          // 出队时的节点
            printf("%c", BT->data);   // 输出节点存储的值
            if (BT->lchild != NULL) { // 有左孩子时将该节点进队列
                enQueue(q, BT->lchild);
            }
            if (BT->rchild != NULL) { // 有右孩子时将该节点进队列
                enQueue(q, BT->rchild);
            }
        }
    }
    
    int main() {
        // 例子:ABDH###E##CF##G##
        BTNode* BT;
        printf("请输入字符串:");
        char* str = (char*)malloc(sizeof(char) * STR_SIZE);
        scanf("%s", str);
        if (strlen(str) == createBTNode(&BT, str, 0)) {
            printf("二叉树建立成功\n");
        }
        // printf("请输入字符串:");
        // createBTNode2(&BT);
        // draw(BT);
    
        printf("\n先序遍历结果:");
        preOrder(BT);
    
        printf("\n中序遍历结果:");
        inOrder(BT);
    
        printf("\n后序遍历结果:");
        postOrder(BT);
    
        printf("\n层序遍历结果:");
        levelOrder(BT);
    
        return 0;
    }
    
    // 初始化队列
    void initQueue(SqQueue** q) {
        if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {
            printf("内存分配失败!");
            exit(-1);
        }
        (*q)->front = (*q)->rear = -1; // 置 -1
    }
    
    // 判断队列是否为空
    bool emptyQueue(SqQueue* q) {
        // 首指针和尾指针相等,说明为空。空-返回真,不空-返回假
        if (q->front == q->rear) {
            return true;
        }
        return false;
    }
    
    // 进队列
    bool enQueue(SqQueue* q, BTNode* node) {
        // 判断队列是否满了。满(插入失败)-返回假,不满(插入成功)-返回真
        if (q->rear == MAX_SIZE - 1) {
            return false;
        }
        q->rear++;               // 头指针加 1
        q->data[q->rear] = node; // 传值
        return true;
    }
    
    // 出队列
    bool deQueue(SqQueue* q, BTNode** node) {
        // 判断是否空了。空(取出失败)-返回假,不空(取出成功)-返回真
        if (q->front == q->rear) {
            return false;
        }
        q->front++;                // 尾指针加 1
        *node = q->data[q->front]; // 取值
        return true;
    }
    
    // 创建二叉树
    int createBTNode(BTNode** BT, char* str, int n) {
        char ch = str[n++];  // 把第 n 个字符赋给ch,方便后面判断,字符下标后移
        if (ch != '\0') {    // 如果 ch 不等于结束符就继续创建,否则就结束
            if (ch == '#') { // 以 # 号代表 NULL,下面没有了
                *BT = NULL;
            } else {
                if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
                    printf("内存分配失败!");
                    exit(-1);
                } else {
                    (*BT)->data = ch;
                    n           = createBTNode(&((*BT)->lchild), str, n); // 左递归创建
                    n           = createBTNode(&((*BT)->rchild), str, n); // 右递归创建
                }
            }
        }
        // 返回 n,记录字符串使用到哪里了
        return n;
    }
    // 创建二叉树
    // void createBTNode2(BTNode** BT) {
    //     char ch;
    //     ch = getchar();
    //     if (ch == '#') {
    //         *BT = NULL;
    //     } else {
    //         if (!(*BT = (BTNode*)malloc(sizeof(BTNode)))) {
    //             printf("内存分配失败!");
    //             return;
    //         } else {
    //             (*BT)->data = ch;
    //             createBTNode2(&((*BT)->lchild)); // 分配成功则接着建立左子树和右子树
    //             createBTNode2(&((*BT)->rchild));
    //         }
    //     }
    // }
    
    // 先序遍历
    void preOrder(BTNode* BT) {
        if (BT != NULL) {           // 判断不为空
            printf("%c", BT->data); // 访问根节点
            preOrder(BT->lchild);   // 递归,先序遍历左子树
            preOrder(BT->rchild);   // 递归,先序遍历右子树
        }
    }
    
    // 中序遍历
    void inOrder(BTNode* BT) {
        if (BT != NULL) {
            inOrder(BT->lchild);
            printf("%c", BT->data);
            inOrder(BT->rchild);
        }
    }
    
    // 后序遍历
    void postOrder(BTNode* BT) {
        if (BT != NULL) {
            postOrder(BT->lchild);
            postOrder(BT->rchild);
            printf("%c", BT->data);
        }
    }
    
    /*****************************************************************************
    * @date   2020/4/19
    * @brief  水平画树
    * @param  node	二叉树节点
    * @param  left	判断左右
    * @param  str 	可变字符串
    *****************************************************************************/
    void draw_level(BTNode* node, bool left, char* str) {
        if (node->rchild) {
            draw_level(node->rchild, false, strcat(str, (left ? "|     " : "      ")));
        }
    
        printf("%s", str);
        printf("%c", (left ? '\\' : '/'));
        printf("-----");
        printf("%c\n", node->data);
    
        if (node->lchild) {
            draw_level(node->lchild, true, strcat(str, (left ? "      " : "|     ")));
        }
        //  "      " : "|     " 长度为 6
        str[strlen(str) - 6] = '\0';
    }
    
    /*****************************************************************************
    * @date   2020/4/19
    * @brief  根节点画树
    * @param  root	二叉树根节点
    *****************************************************************************/
    void draw(BTNode* root) {
        char str[STR_SIZE];
        memset(str, '\0', STR_SIZE);
    
        /**
         * 1. 在 windows 下,下面是可执行的
         * 2. 在 Linux   下,执行会报 Segmentation fault
         *      需要使用中间变量
         */
        if (root->rchild) {
            draw_level(root->rchild, false, str);
        }
        printf("%c\n", root->data);
        if (root->lchild) {
            draw_level(root->lchild, true, str);
        }
    }
    

    4. 结果展示

    创建二叉树是以 “#” 为结束符NULL。
    例子就是最上面的图:ABDH###E##CF##G##
    结果应该为:ABCDEFGH
    在这里插入图片描述

    展开全文
  • bfs 和 队列学过数据结构的都知道,二叉树的层次遍历。层次遍历利用的数据结构是...队列在二叉树层次遍历中的作用我们知道,二叉树的结构如下:/*** Definition for a binary tree node.* type TreeNode struct {*...

    bfs 和 队列

    学过数据结构的都知道,二叉树的层次遍历。

    层次遍历利用的数据结构是队列。

    那么,

    思考一下

    为什么层次遍历,要用到队列,而不是其他的数据结构,比如栈呢?换句话说,队列在二叉树的层次遍历过程中起到了什么作用呢?

    队列在二叉树层次遍历中的作用

    我们知道,二叉树的结构如下:

    /**

    * Definition for a binary tree node.

    * type TreeNode struct {

    * Val int

    * Left *TreeNode

    * Right *TreeNode

    * }

    */

    从结构中大致可以知道,二叉树的根跟左右还是是采用链表的形式联系的,父节点,保存了左右孩子的指针,所以,我们知道了父节点,必然也就知道了左右孩子的信息。

    但是,在一个二叉树中,同层之间的信息通过什么联系在一起的呢?

    7

    5 8

    2 6 9 12

    比如上图中的2,6,9,12,这时层次遍历的时候,我们如何保持同层之间的顺序呢?这个就应该是靠队列的作用了。

    队列的一个特点是,元素是先进先出,我们可以把同层的兄弟元素依次入队,然后,在出队的过程中再遍历左右孩子,循环以上操作即可。

    通过数组创建二叉树vs二叉树的层次遍历

    今天,做leetcode上的一道二叉树层次遍历的题目,由于需要在本地调试,所以想在本地创建一个二叉树,于是想到了,通过数组去创建一个二叉树,也就是将一个数组转化为完全二叉树。

    最后发现,原来,通过数组创建二叉树和二叉树的层次遍历其实存在着某种联系,他们是一个相反的过程。

    也就是通过数组创建二叉树是将数组转化为二叉树,而二叉树的层次遍历其实是将二叉树转化为数组的形式。

    确实很妙。

    下面给出代码

    python

    #!/usr/bin/python

    #-*- coding: UTF-8 -*-

    class node():

    def __init__(self,k=None,l=None,r=None):

    self.key=k;

    self.left=l;

    self.right=r;

    def create_tree_by_array(input_list):

    """

    通过数组创建二叉树,

    其实是层次遍历

    需要利用节点队列

    """

    def _createNode(item):

    if item is '#':

    return None

    else:

    return node(k=item)

    queue = []

    root = _createNode(input_list.pop(0))

    queue.append(root)

    while len(input_list) > 0:

    curNode = queue.pop(0)

    curNode.left = _createNode(input_list.pop(0))

    curNode.right = _createNode(input_list.pop(0))

    if curNode.left:

    queue.append(curNode.left)

    if curNode.right:

    queue.append(curNode.right)

    return root

    def traverse_tree_by_level(root):

    """

    层次遍历

    需要利用节点队列

    """

    queue = []

    output_list = []

    queue.append(root)

    output_list.append(root.key)

    while len(queue) > 0:

    curNode = queue.pop(0)

    if curNode.left:

    output_list.append(curNode.left.key)

    queue.append(curNode.left)

    if curNode.right:

    output_list.append(curNode.right.key)

    queue.append(curNode.right)

    print(output_list)

    def inorder(root): #中序遍历

    if root is None:

    return ;

    else:

    inorder(root.left);

    print(root.key,)

    inorder(root.right);

    tree_data_list = [3,9, 20, '#','#', 15,7]

    root=None; # 测试代码

    root=create_tree_by_array(tree_data_list);

    inorder(root);

    traverse_tree_by_level(root)

    golang

    package main

    import (

    "fmt"

    )

    type Node struct {

    Value int

    Left *Node

    Right *Node

    }

    func CreateNode(item int) *Node {

    if item == -1 {

    return nil

    }

    return &Node{item, nil, nil}

    }

    func CreateByBreadthFirstSearch(inputList []int) *Node {

    queue := []*Node{}

    root := CreateNode(inputList[0])

    queue = append(queue, root)

    inputList = inputList[1:]

    for len(inputList) > 0 {

    curNode := queue[0]

    queue = queue[1:]

    curNode.Left = CreateNode(inputList[0])

    if curNode.Left != nil {

    queue = append(queue, curNode.Left)

    }

    inputList = inputList[1:]

    curNode.Right = CreateNode(inputList[0])

    if curNode.Right != nil {

    queue = append(queue, curNode.Right)

    }

    inputList = inputList[1:]

    }

    return root

    }

    func (node *Node) BreadthFirstSearch() {

    if node == nil {

    return

    }

    output_list := []int{}

    queue := []*Node{node}

    for len(queue) > 0 {

    curNode := queue[0]

    queue = queue[1:]

    output_list = append(output_list, curNode.Value)

    if curNode.Left != nil {

    queue = append(queue, curNode.Left)

    }

    if curNode.Right != nil {

    queue = append(queue, curNode.Right)

    }

    }

    for _, v := range output_list {

    fmt.Print(v, " ")

    }

    }

    func main() {

    input_list := []int{3, 7, 9, -1, -1, 20, 4}

    root := CreateByBreadthFirstSearch(input_list)

    root.BreadthFirstSearch()

    }

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

    2020-06-06 16:28:41
    Java 二叉树层次遍历

    Java 二叉树层次遍历

    简介: 遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。

    设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有几种情况:DLR(称为先序遍历),LDR(称为中序遍历),LRD (称为后序遍历),层次遍历。

    **层次遍历:**按照层次访问,通常用队列来做。访问根,访问子女,再访问子女的子女(越往后的层次越低)(两个子女的级别相同)。

    如图二叉树的层次遍历结果为: 3,9,20,15,7
    在这里插入图片描述
    代码实现:

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode n1 = new TreeNode(9);
        TreeNode n2 = new TreeNode(20);
        TreeNode n3 = new TreeNode(15);
        TreeNode n4 = new TreeNode(7);
        root.left = n1;
        root.right = n2;
        n2.left = n3;
        n2.right = n4;
    
        List<List<Integer>> rs = levelOrder(root);
        System.out.println(rs);
    }
    
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        if (root == null)
            return list;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
    
        while (!deque.isEmpty()) {
            int num = deque.size();
            List<Integer> subList = new LinkedList<Integer>();
            for (int i = 0; i < num; i++) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) deque.addLast(node.left);
                if (node.right != null) deque.addLast(node.right);
                subList.add(node.val);
            }
            list.add(subList);
        }
        return list;
    }
    

    在这里插入图片描述

    展开全文
  • 1.二叉树层次遍历 2.二叉树结构图的打印 结语 1.二叉树层次遍历 主要用到队列操作,先入队根结点,再不断出队,判断出队结点是否有左右孩子,有则入队,直到队列空为止。 层次遍历挺简单,但是如果要输出结点...

    目录

     

    1.二叉树层次遍历

    2.二叉树结构图的打印

    结语


    1.二叉树层次遍历

    主要用到队列操作,先入队根结点,再不断出队,判断出队结点是否有左右孩子,有则入队,直到队列空为止。

    层次遍历挺简单,但是如果要输出结点序列时分清该结点所在的深度则需要稍微变化一点,思路如下:

    1. 用一个变量实时记录某层的最后一个结点,当出队元素为该节点时,则之前的所有出队元素位于同一层;
    2.  记录方式为每次出队后判断是否为该层最后一个结点,如是,则入队子树时按非空子树右>左的优先级记录,比如:当出队A,且A为该层最后一个结点,如果A有右树则右树被记录,若没有右树则记录左树;
    3. 当出队子树没有子树时呢?这时再添加一个变量,用于记录在遇到该层最后一个结点之前的结点,记录方式同2,只是出队的结点都需要记录而不是只记录最后一个,当遇到最后一个结点不存在子树时,则将该结点作为该层最后节点。

    参考代码如下:

    int TraversByLevel(BTNode<char> *T) {
    	if (!T) return -1;
    	BTNode<char>* p = T;
    	BTNode<char>* last_one = T;
    	BTNode<char>* pre_last;
    	std::queue <BTNode<char>*> qu;
    	qu.push(p);
    	while (!qu.empty()) {
    		p = qu.front();
    		qu.pop();
    		printf("%c  ", p->value);
    		if (p->rchild) {
    			pre_last = (BTNode<char> *)p->rchild;
    		} else if (p->lchild) {
    			pre_last = (BTNode<char> *)p->lchild;
    		}
    		if (p == last_one) {
    			printf("\n");
    			if (p->rchild) {
    				last_one = (BTNode<char> *)p->rchild;
    			} else if (p->lchild) {
    				last_one = (BTNode<char> *)p->lchild;
    			} else {
    				last_one = pre_last;
    			}
    		}
    		if (p->lchild) {
    			qu.push((BTNode<char> *)p->lchild);
    		}
    		if (p->rchild) {
    			qu.push((BTNode<char> *)p->rchild);
    		}
    	}
    	printf("\n");
    	return 0;
    }

     运行效果(下面是的是二叉树的打印,具体参看后文):


    2.二叉树结构图的打印

    这个东西搞了我两天,不过最后写出来还是挺开心的,先来展示下打印一棵满二叉树的成果吧。

    先讲讲思路吧:

    1. 先讲讲打印结点吧,这东西无非就是找关系:找到打印结点和打印之前需要打印多少空格的关系。
    2. 为了找到到关系我把1-5层的满二叉树给画了出来,如下图,可以看到在打印从左到右第一个结点时隔了一个距离设为s0,从该结点到另外一个结点又隔了一个距离设为s1,每两个结点间又有一个距离设为s2,我找到的关系如下:
    • 第一行的s0 = └总列数/2)┘,而 总列数 = └2^(h-2)*6 - 1┘,h为二叉树深度(空树为0),之后几行的s0都为上一行的s0/2,这样就找到了s0的规律了;
    • 第一行的s1 = 0,而从第二行开始s1开始增加之后不断减少,但是可以看出s1的长度受上一行两个关系字符'/'和'\'的距离(设为g0)的影响,所以先需要找到这个的规律后,s1 = g0 + 2;
    • 得知了s0和s1后,s2只需要算就能算出来了 s2 = (总列数- (s0-1)*2 - 上层结点数*2 - s*上层结点数)/(上层结点数 - 1);
    • 再说关系行('/'和'\')的绘制,这里的第一行空格数与上一行的s0有关,而'/'和'\'之间的距离g0知道后,每一对'/'和'\'之间的距离就很容易计算出来了,所以关键是找出g0;
    • 这里g0找的方式就有点投机取巧了,一开始我以为是等比数列,前三项是1,3,9,但是到第四项,第五项就变成了21和45???没办法,我只好用曲线拟合一下了。拟合结果如下右图。这样就解决了问题了。

    然后就是程序编写了,一开始我是在层次遍历上改的,但是发现,只能满足打印满二叉树,因为我设置了一个变量,当结点行处理完就处理关系行,可是发现,关系行处理时出队结点固定了,无法读取之前结点的左右关系,并且当不是二叉树时,遇到空树就完全无法处理了,让后我就想了:无论什么二叉树都是一棵满二叉删删减减变的,那我就按照满二叉处理任何二叉树。然后就设计如下思路:

    1. 空树也要入队,遇到空树时打印空格;
    2. 出队元素为NULL时,向队列里入队两个NULL,代表空树的两个空子树;
    3. 建立两个队列,一个用于打印结点,一个打印关系。

    参考代码如下(upToInt为向上取整,fillWith为向字符串中填写指定个数的字符,返回值为buffer行数):

    int BTreePrintToStrArr(BTNode<char> *T, char buffer[][STR_MAX], int size) {
    	if (!T || !buffer) return -1;
    	BTNode<char>* p = T;
    	int height;
    	int tatolCol;
    	int spaces[3];
    	int gap[2];
    	int count;
    	int i, j, k;
    	std::queue <BTNode<char>*> qu_travers;
    	std::queue <BTNode<char>*> qu_print;
    	// init
    	memset(buffer, 0, size*sizeof(char));
    	height = getBTreeDepth(T);
    	tatolCol = upToInt(pow(2, height - 2)*6 - 1);
    	gap[0] = (int)
    			 (0.0417*pow(height,5) 
    			 - 0.6667*pow(height,4) 
    			 + 4.4583*pow(height,3) 
    			 - 13.333*pow(height,2) 
    			 + 18.5*height - 9);
    	spaces[0] = upToInt(tatolCol/2.0);
    	count = i = j = k = 0;
    	qu_travers.push(p);
    	while (!qu_travers.empty() && i < height*2) {
    		switch (i%2) {
    		case 0: // process node
    			p = qu_travers.front();
    			qu_travers.pop();
    			qu_print.push(p);
    			if (count == 0) {
    				fillWith(&buffer[i][j], ' ', spaces[0] - 1);
    				j += spaces[0] - 1;
    			} else if ((count+1)%2 == 0) {
    				fillWith(&buffer[i][j], ' ', spaces[1]);
    				j += spaces[1];
    			} else {
    				fillWith(&buffer[i][j], ' ', spaces[2]);
    				j += spaces[2];
    			}
    			count++;
    			buffer[i][j++] = p?(p->value):' ';
    			qu_travers.push(p?(BTNode<char> *)p->lchild:NULL);
    			qu_travers.push(p?(BTNode<char> *)p->rchild:NULL);
    			if (count == (int)pow(2,(i+1)/2)) {// new line
    				buffer[i][j] = '\0';
    				i++;
    				j = 0;
    				k = 0;
    				spaces[0] /= 2;	
    				gap[0] = (int)
    						(0.0417*pow(height - i/2,5) 
    						- 0.6667*pow(height - i/2,4) 
    						+ 4.4583*pow(height - i/2,3) 
    						- 13.333*pow(height - i/2,2) 
    						+ 18.5*(height - i/2) - 9);
    				if (count > 1) {
    					gap[1] = (tatolCol - spaces[0]*2 - gap[0]*count - count*2)/(count - 1);
    				} else {
    					gap[1] = 0;
    				}
    			}
    			break;
    		case 1: // process link
    			p = qu_print.front();
    			qu_print.pop();
    			// left
    			if (k == 0) {
    				fillWith(buffer[i] + j, ' ', spaces[0]);
    				j += spaces[0];
    			} else {
    				fillWith(buffer[i] + j, ' ', gap[1]);
    				j += gap[1];
    			}
    			if (p && p->lchild) {
    				buffer[i][j++] = '/';
    			} else {
    				buffer[i][j++] = ' ';
    			}
    			k++;
    			// right
    			fillWith(buffer[i] + j, ' ', gap[0]);
    			j += gap[0];
    			if (p && p->rchild) {
    				buffer[i][j++] = '\\';
    			} else {
    				buffer[i][j++] = ' ';
    			}
    			k++;
    			if (k >= count*2 || qu_print.empty()) {
    				buffer[i][j] = '\0'; j = 0;
    				i++;
    				spaces[1] = gap[0] + 2;
    				if (count > 1) {
    					spaces[2] = (tatolCol - (spaces[0]-1)*2 - count*2 - spaces[1]*count)/(count - 1);
    				} else {
    					spaces[2] = 0;
    				}
    				count = 0;
    			}
    			break;
    		}
    	}
    	return i - 1;
    }

    满二叉图效果图如下:

    其他二叉图效果图如下:


    结语

    最后还是觉得自己的方法有些冗杂,而且画出来效果不是特别好,至于深度大于6的还未试过,不知道会不会有问题。

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

    2019-06-05 17:48:43
    层次遍历二叉树:即从左到右,从上到下,从左到右依次遍历。 废话不多说,直接上图 ABCEHDFG 上面二叉树层次遍历结果为:A,B,C,D,E,F,G,H 层次遍历的算法思想: 1.初始化一个空队列Q 2.若二叉树bt为空树,则...
  • github:代码实现本文算法均使用python3实现1. 二叉树1.1 二叉树的定义二叉树是一种特殊的树,它具有以下特点:(1)树中每个节点最多只能有两棵树,即每个节点的度最多为2。(2)二叉树的子树有左右之分,即左子树...
  • 1040. 二叉树层次遍历  Description 给出一棵二叉树,求它的层次遍历结果。 [二叉树的遍历问题是一种精神,务必领会] Input Format 第一行,N 默认序号为0的节点为树根。接下来共N-1行,依次表示序号为...
  • 二叉树该二叉树层次遍历顺序为: 1 2 3 4 5 6 7 如果按行输出就是: 1 2 3 4 5 6 7 二叉树的层次遍历可以借助队列来实现,代码如下(结果按行输出): class Node(object): # 节点类 ...
  • 二叉树层次遍历代码

    千次阅读 2017-01-18 18:29:11
    vector> levelOrder(TreeNode* root) {  vector>res;  vectorlevel;  if(root == NULL)  return res ;    TreeNode* cur ;  
  • 二叉树层次遍历C++层次遍历思想C++层次遍历代码 C++层次遍历思想 第一步:将根节点放入队列 第二步:每次从队列中弹出一个节点,记为node 第三步:看这个node有没有左孩子,如果有左孩子就把左孩子放到队列中,如果...
  • 二叉树层次遍历打印

    2016-07-20 18:30:07
    二叉树层次遍历打印,并且每层对应输出换行(遍历一层输出后,下一层遍历换行输出)。 final static int MAX_NUM = 500 class TreeNode { //二叉树结构 int val = 0; TreeNode left = null; TreeNode ...
  • 二叉树层次遍历 与二叉树先序、中序遍历使用栈类似,二叉树的层次遍历的实现是基于队列这个数据结构来实现的。 主要算法思想是首先建一个队列并将树的根节点入队,然后当树不为空的时候持续访问队首节点并将其左右...
  • 二叉树层次遍历--C语言

    千次阅读 多人点赞 2018-12-21 17:54:22
    今天写一下二叉树层次遍历层次遍历用到的数据结构是队列。   层次遍历算法中增加了三个int型数据,其中levelcount用于记录现在处理的是树的第几层;curlevel用于记录当前层还有几个节点没有被访问过;next...
  • 数据结构-二叉树层次遍历

    千次阅读 多人点赞 2018-10-23 14:57:49
    首先介绍下二叉树层次遍历即按照顺序对树节点依次访问,如下图: 顺序遍历的结果为:ABCDEFGHIJK 我们可以借助一个队列来实现二叉树层次遍历;思路如下: 先将二叉树根节点入队,然后出队,访问该节点,...
  • 二叉树层次遍历算法

    千次阅读 2020-08-27 01:23:39
    层次遍历 其实记住以上的输出顺序还是非常简单的。首先要明白,左节点一定先比右节点输出! 那么就很好理解了,那么那些所谓的前序、中序、后序而言是针对根节点的相对位置命名的。 例如前序遍历,则就是根节点是最...
  • 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层次遍历...
  • 7-1 二叉树层次遍历 (25 分) 编写程序,要求实现(1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 ...
  • 在教科书上学到的关于二叉树层次遍历,只是简单的按照每一层打印元素。如果想要区分每一层,应该怎么做?
  • 二叉树层次遍历写法

    2018-10-11 20:24:00
    层次遍历利用队列,很容易实现,先根节点入队,出队,每次出队检查左右子节点是否为空,非空则入队,如此往复直至队空,代码如下 //层次遍历输出二叉树 void levelOrder(BiTree biT){ printf("层次遍历结果:...
  • 实现二叉树层次遍历实现二叉树层次遍历实现二叉树层次遍历实现二叉树层次遍历
  • 小弟研究二叉树层次遍历三天了,始终不能结合队列写出可执行的代码。。。。真心求教。。。。万分感谢。。。。。!!!! void Printbylevel(BTree T) { BNode *tmp = T; CircleQueue *q = malloc(sizeof...
  • 这一节几道题目都是应用层次遍历的基本思路解决问题,当然也有不用层次遍历...(三)二叉树层次遍历 103.Binary Tree Zigzag Level Order Traversal Given a binary tree, return thezigzag level ordertraversal ...
  • 有一篇旧文写的是在终端或文件中图形化打印二叉树,当时使用了 队列 ,但后来在学到二叉树层次遍历 的时候才意识到当时的实现是真的……蹩脚。 二叉树层次遍历 如图所示二叉树: .--------- 1 ---------. .--...
  • **题目:**输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。...这题考查的是二叉树的层次遍历,二叉树层次遍历一般采用队列来存储下一层的结点,然后用循环处理队列,逐个打印出来。 代码: ...
  • 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树[3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层次...
  • 二叉树遍历代码

    2019-05-30 21:54:32
    4.编写函数,借助队列实现二叉树层次遍历算法 5.编写函数,求二叉树的高度 6.编写函数,求二叉树的结点个数 7.编写函数,求二叉树的叶子个数 8.编写函数,交换二叉树每个结点的左子树和右子树 9.编写一个主函数,在...

空空如也

空空如也

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

二叉树层次遍历代码