C#二叉树的从右向左的层次遍历详解
2.4 用C#构造一棵二叉树，并从根开始，按层的顺序，从右到左，从上到下，依次进行访问。
引言
这是一道C#初学时遇到的问题,也正好趁此机会回顾一下有关于二叉树的内容
通过本篇文章,你将收获到:
1.关于二叉树和层次遍历的基础知识;
2.复习有关于队列的基本知识
3.学习如何解决这道习题
环境设置
编译环境为Microsoft Visual Studio 2019,控制台程序
具体过程实现
首先,我们先回顾一下有关于二叉树和其遍历的基础知识:
简单来说,二叉树是一种每个结点最多有两个子树的树结构,如下图所示:
对于二叉树的遍历来说,常见的先序遍历,中序遍历,后序遍历,层次遍历等多种方法,而这道题要用到二叉树的层次遍历
所谓的层次遍历,也就是从上到下一层一层地对二叉树进行遍历.这道题要求的是每一层从右往左遍历,不过为了使题目更加好理解,我们优先考虑常见情况,也就是每一层从左到右进行遍历,此时上图的遍历顺序应该是A-B-C-D-E-F-G-H..
一种比较经典的做法是运用队列,我们以上图为例叙述过程(为了方便,仅作示意图):
如果读者想要回顾关于队列的基本知识,可以参考这一篇文章:
https://www.cnblogs.com/TimVerion/p/11194552.html
通过队列可以很好的实现二叉树的层次遍历,在思路清晰之后,我们需要对本题情况进行分析:
我们每次将元素出队之后,访问它并将它的左右子树依次加入队列,从而实现从左至右的层次遍历.那如果我们出队某节点并访问之后,将其右子树先入队,再入队左子树,是不是就可以实现每层从右到左的遍历了?接下来我们试一下:
1.入队A;
2.出队A,入队C,B;
3.出队C,入队G,F;
4.出队B,入队E,D;
5.出队G,无左右子树,因此不入队元素;
6.出队F,无左右子树,因此不入队元素;
7.出队E,无左右子树,因此不入队元素;
8.出队D,入队H;
9.出队H,队空,结束;
至此,出队顺序为:A-C-B-G-F-E-D-H,说明思路是正确的,接下来我们用C#的代码实现该过程:
首先是定义树的结点类
public class TreeNode
{
//树结点类的成员变量
private object _data;//存放结点数据
private TreeNode _left;//树的左孩子
private TreeNode _right;//树的右孩子
//属性
public object Data
{
get { return _data; }
}
public TreeNode Left
{
get { return _left; }
set { _left = value; }
}
public TreeNode Right
{
get { return _right; }
set { _right = value; }
}
//构造方法
public TreeNode(object data)
{
_data = data;//接收数据
}
public override string ToString()//重写了object类的ToString()方法
{
return _data.ToString();
}
}
这里面我们应用了属性来进行对字段的访问
关于属性的问题,详见https://www.cnblogs.com/zhangbaochong/p/4793360.html
接下来是二叉树操作的类的构造
public class BinaryTree//二叉树的类
{
private TreeNode _head;//二叉树的头节点
private string str;//用来存放结点信息的字符串
//属性
public TreeNode Head
{
get { return _head; }
}
private void Add(TreeNode parent,int index)//根据字符串添加左右结点,建立二叉树
{
int leftindex = 2 * index + 1;//左孩子结点应该对应的数组中的位置
if(leftindex<str.Length)
{
if(str[leftindex]!='#')
{
parent.Left = new TreeNode(str[leftindex]);
Add(parent.Left, leftindex);//用递归实现左孩子结点添加
}
}
int rightindex = index * 2 + 2;
if(rightindex<str.Length)
{
if(str[rightindex]!='#')
{
parent.Right = new TreeNode(str[rightindex]);
Add(parent.Right, rightindex);//用递归实现右孩子结点添加
}
}
}
public BinaryTree(string Cstr)
{
str = Cstr;
_head = new TreeNode(str[0]);//添加头结点
Add(_head, 0);//给头结点添加孩子结点
}
//接下来,用队列实现二叉树的层次遍历
public void leveltraverse()
{
Queue queue = new Queue();//建立一个队列
queue.Enqueue(_head);//让头结点进入队列
while(queue.Count>0)//当队列不为空
{
TreeNode node = (TreeNode)queue.Dequeue();//出队
Console.Write(node.ToString());//访问该结点
if(node.Right!=null)
{
queue.Enqueue(node.Right);//右子树不为空则右子树进入队列
}
if(node.Left!=null)
{
queue.Enqueue(node.Left);//左子树不为空则左子树进入队列
}
}
}
}
在这一部分里,我们一共解决了这样几件事情:
1.将一个顺序输入的字符串转换为二叉树(其中字符串的#字符对应二叉树的空结点)
这一部分的原理是,在空结点用#表示的情况下,跟结点在字符串中对应的位置为0,则其左子树的序号为2x+1=1,右子树的序号为2x+2=2,以此类推(二叉树的性质)
2.用递归不断地实现左子树的加入和右子树的加入
3.用队列的方式实现二叉树的每层从右到左的层次遍历
接下来是主函数部分
class Program
{
static void Main(string[] args)
{
string str;
Console.WriteLine("请按照层次遍历从左到右的顺序输入树的结点(结点为空则用#表示)");
str = Console.ReadLine();
Console.WriteLine("层次遍历从右到左的结果是:");
BinaryTree bitree = new BinaryTree(str);
bitree.leveltraverse();
}
}
至此,我们通过用户输入的字符串实现了二叉树每层从右到左的层次遍历
最后,附上本题的全部代码:
using System;
using System.Collections;
using System.ComponentModel;
using System.Reflection.Metadata.Ecma335;
namespace leveltraverse
{
public class TreeNode
{
//树结点类的成员变量
private object _data;//存放结点数据
private TreeNode _left;//树的左孩子
private TreeNode _right;//树的右孩子
//属性
public object Data
{
get { return _data; }
}
public TreeNode Left
{
get { return _left; }
set { _left = value; }
}
public TreeNode Right
{
get { return _right; }
set { _right = value; }
}
//构造方法
public TreeNode(object data)
{
_data = data;//接收数据
}
public override string ToString()//重写了object类的ToString()方法
{
return _data.ToString();
}
}
public class BinaryTree//二叉树的类
{
private TreeNode _head;//二叉树的头节点
private string str;//用来存放结点信息的字符串
//属性
public TreeNode Head
{
get { return _head; }
}
private void Add(TreeNode parent,int index)//根据字符串添加左右结点,建立二叉树
{
int leftindex = 2 * index + 1;//左孩子结点应该对应的数组中的位置
if(leftindex<str.Length)
{
if(str[leftindex]!='#')
{
parent.Left = new TreeNode(str[leftindex]);
Add(parent.Left, leftindex);//用递归实现左孩子结点添加
}
}
int rightindex = index * 2 + 2;
if(rightindex<str.Length)
{
if(str[rightindex]!='#')
{
parent.Right = new TreeNode(str[rightindex]);
Add(parent.Right, rightindex);//用递归实现右孩子结点添加
}
}
}
public BinaryTree(string Cstr)
{
str = Cstr;
_head = new TreeNode(str[0]);//添加头结点
Add(_head, 0);//给头结点添加孩子结点
}
//接下来,用队列实现二叉树的层次遍历
public void leveltraverse()
{
Queue queue = new Queue();//建立一个队列
queue.Enqueue(_head);//让头结点进入队列
while(queue.Count>0)//当队列不为空
{
TreeNode node = (TreeNode)queue.Dequeue();//出队
Console.Write(node.ToString());//访问该结点
if(node.Right!=null)
{
queue.Enqueue(node.Right);//右子树不为空则右子树进入队列
}
if(node.Left!=null)
{
queue.Enqueue(node.Left);//左子树不为空则左子树进入队列
}
}
}
}
class Program
{
static void Main(string[] args)
{
string str;
Console.WriteLine("请按照层次遍历从左到右的顺序输入树的结点(结点为空则用#表示)");
str = Console.ReadLine();
Console.WriteLine("层次遍历从右到左的结果是:");
BinaryTree bitree = new BinaryTree(str);
bitree.leveltraverse();
}
}
}
运行结果可以看到如下图所示:
总结
1.本文介绍了有关于二叉树层次遍历的基础知识及其具体实现的方式(通过队列)
2.本文通过对于这道题目的探索巩固了C#的一些基础的语法知识
3.读者如果对于二叉树的其他遍历方式(如先序遍历,中序遍历,后序遍历等)感兴趣,可以参考文末的文章[3]https://www.cnblogs.com/zhaodayou/p/6883147.html
最后想说的话
因为本人刚接触C#这门优秀的语言,所以这篇文章难免会有错误和不足的地方,也欢迎大家讨论和交流.同时我也会在接下来的学习中不断提升自己,掌握更多的知识和技能.
参考文章:
[1]https://blog.csdn.net/weixin_43251547/article/details/104062082
[2]https://blog.csdn.net/qq_24642743/article/details/78597219?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2-all-first_rank_v2~rank_v25-1-78597219.nonecase&utm_term=c#%20%E4%BA%8C%E5%8F%89%E6%A0%91&spm=1000.2123.3001.4430
[3]https://www.cnblogs.com/zhaodayou/p/6883147.html
