当前位置:首页 > 数据结构与算法 > 正文内容

以层序插入二叉树结点

admin2周前 (04-25)数据结构与算法47

这里以层序插入二叉树的结点,以先序遍历输出。

上一篇关于二叉树的内容在这里:https://lovedm.club/?id=110

using System;
using System.Collections.Generic;

namespace BTree
{
    class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree(new Node(10));//           10
            tree.InsertNode(new Node(9));      //          /  \  
            tree.InsertNode(new Node(8));      //         9    8
            tree.InsertNode(new Node(7));      //       /  \  /  \
            tree.InsertNode(new Node(6));      //      7   6 5    4              
            tree.InsertNode(new Node(5));      //     /  
            tree.InsertNode(new Node(4));      //    3
            tree.InsertNode(new Node(3));      //

            tree.PreTraversal(tree.root);
            Console.WriteLine("--------------");
            tree.LevelOrderTraversal(tree.root);

        }
    }

    /// <summary>
    /// 树的节点
    /// </summary>
    class Node
    {
        public int Value = 0;
        public Node Left;
        public Node Right;
        public Node(int value)
        {
            Value = value;
        }
    }

    /// <summary>
    /// 二叉树
    /// </summary>
    class Tree
    {
        public readonly Node root;
        public Tree(Node node)
        {
            root = node;
        }

        /// <summary>
        /// 以层序进行插入结点
        /// </summary>
        /// <param name="node"></param>
        public void InsertNode(Node node)
        {
            //使用队列
            Queue<Node> queue = new Queue<Node>();
            //首先根节点入队列
            queue.Enqueue(root);
            //队列不为空一直循环
            while (queue.Count != 0)
            {
                //出队列
                Node tempNode = queue.Dequeue();
                //左孩子不为空,那么将左孩子进队列;如果左孩子为空,则将结点挂到左孩子
                if (tempNode.Left != null)
                {
                    queue.Enqueue(tempNode.Left);
                }
                else
                {
                    tempNode.Left = node;
                    return;
                }
                //右孩子不为空,那么将右孩子进队列;如果右孩子为空,则将结点挂到右孩子
                if (tempNode.Right != null)
                {
                    queue.Enqueue(tempNode.Right);
                }
                else
                {
                    tempNode.Right = node;
                    return;
                }

            }
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        /// <param name="node"></param>
        public void PreTraversal(Node node)
        {
            if (node == null)
            {
                return;
            }

            Console.WriteLine(node.Value);
            PreTraversal(node.Left);
            PreTraversal(node.Right);
        }

        public void LevelOrderTraversal(Node node)
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(node);

            while (queue.Count != 0)
            {
                Node tempNode = queue.Dequeue();
                Console.WriteLine(tempNode.Value);
                if (tempNode.Left != null)
                {
                    queue.Enqueue(tempNode.Left);
                }
                if (tempNode.Right != null)
                {
                    queue.Enqueue(tempNode.Right);
                }
            }
        }
    }
}


版权声明:本文由cyhu's essay发布,如需转载请注明出处。

本文链接:https://lovedm.club/?id=126

相关文章

中缀表达式转后缀表达式

中缀表达式转后缀表达式

转换过程如下:1、运算数:直接输出;2、左括号:压入堆栈;3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运...

C# 二叉树

C# 二叉树

这里实现了二叉树的创建与插入结点,前中后序遍历的递归实现以及前序遍历的非递归实现,层序遍历的非递归实现。插入结点时采用二叉排序树的方式,没有处理有相同结点时的情况,按下面代码中插入结点时,构成的二叉树...

线性表

线性表

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。1.集合中必存在唯一的一个“第一元素”。...

二分查找

二分查找

使用二分法对数组进行元素的搜索,返回查找的元素索引,当然使用二分搜索的前提是数组已经完成排序。原始数组有10个元素,要搜索的元素是11。整个排序过程如下:首先原始数组如下:第一次两个指针位置如下:低指...

数据结构

数据结构

数据结构:逻辑结构:反映数据元素之间的逻辑关系。包括:集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系。线性结构:数据结构中的元素存在一对一的相互关系。树形结构:数据结构中的...

单链表

单链表

单链表存储一个直接后继的地址,用一组任意的存储单元存储线性表中的元素。数据域(数据元素)+指针域(指示后继元素存储位置) = 结点,如下图:a和b是两个结点,其中a的指针域保存了指向b的地址。以结点的...