C#代码创建二叉树以及遍历二叉树
标签：字符串 数据 三目运算 初始 lse bin bsp 脚本 创建
转自 https://blog.csdn.net/qq_45071375/article/details/103715587
这是我们用代码创建出来的二叉树图例
A
/ \
B C
/ \ \
D E F
友情提示：
在下面代码中出现的#字符代表子树为空，例如D结点下面左右子树都没有，就是两个#号；C结点没有左子树就是一个#号，具体看Main函数运行代码！
一，字段脚本
using System;
using System.Collections.Generic;
using System.Text;
namespace BinaryDemo
{
public class TreeNode
{
/*
* 树的知识点
* 树结点 根结点 结点子树
* 结点的度 结点关系 结点层次
* 树的深度/高度
*/
//结点下标 结点下标字符串数据 左子树 右子树
private int index;
private string data;
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
///
/// 有参构造结点下标 结点下标的字符串数据
///
///
///
public TreeNode(int index, string data)
{
this.index = index;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
public int getIndex()
{
return index;
}
public void setIndex(int index)
{
this.index = index;
}
//拿到左右子串的数据
public String getData()
{
return data;
}
public void setData(String data)
{
this.data = data;
}
//拿到左子树
public TreeNode getLeftChild()
{
return leftChild;
}
public void setLeftChild(TreeNode leftChild)
{
this.leftChild = leftChild;
}
//拿到右子树
public TreeNode getRightChild()
{
return rightChild;
}
public void setRightChild(TreeNode rightChild)
{
this.rightChild = rightChild;
}
public TreeNode getParent()
{
return parent;
}
public void setParent(TreeNode parent)
{
this.parent = parent;
}
//快捷键生成的字段get和set
public int Index { get => index; set => index = value; }
public string Data { get => data; set => data = value; }
public TreeNode LeftChild { get => leftChild; set => leftChild = value; }
public TreeNode RightChild { get => rightChild; set => rightChild = value; }
public TreeNode Parent { get => parent; set => parent = value; }
}
}
二，二叉树具体实现构建遍历的脚本
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
namespace BinaryDemo
{
public class BinaryTree
{
//根结点
public TreeNode root = null;
public static string[] str;
public static int count;
///
/// 无参构造设置根结点并赋值数据
///
public BinaryTree()
{
root = new TreeNode(1,"A");
}
///
/// 构建二叉树的方法 B C D E F
/// 手动的构建一棵二叉树 很快就可以得出这个二叉树的结构
///
public void CreateBinaryTree()
{
TreeNode nodeb = new TreeNode(2,"B");
TreeNode nodec = new TreeNode(3, "C");
TreeNode noded = new TreeNode(4, "D");
TreeNode nodee = new TreeNode(5, "E");
TreeNode nodef = new TreeNode(6, "F");
root.LeftChild = nodeb;
root.RightChild = nodec;
nodeb.LeftChild = noded;
nodeb.RightChild = nodee;
nodec.RightChild = nodef;
}
///
/// 先序遍历 --迭代
/// 若二叉树为空树直接返回，先序遍历的特点根左右
///
public void PreOrder(TreeNode node)
{
if (node == null)
{
return;
}
else
{
//node.getData()我们可以获取到二叉树的根结点的数据
Console.WriteLine("先序遍历" + "\t迭代" + node.getData());
//得到左子树的数据
PreOrder(node.LeftChild);
//得到右子树的数据
PreOrder(node.RightChild);
}
}
///
/// 中序遍历--迭代
/// 若二叉树为空树直接返回，中序遍历的特点左根右
///
///
public void MidOrder(TreeNode node)
{
if (node == null)
{
return;
}
else
{
MidOrder(node.LeftChild);
Console.WriteLine("中序遍历" + "\t迭代" + node.getData());
MidOrder(node.RightChild);
}
}
///
/// 后序遍历--迭代
/// 若二叉树为空树直接返回，中序遍历的特点左右根
///
///
public void LastOrder(TreeNode node)
{
if (node == null)
{
return;
}
else
{
LastOrder(node.LeftChild);
LastOrder(node.RightChild);
Console.WriteLine("后序遍历" + "\t迭代" + node.getData());
}
}
//-----------------------------------分界线------------------------------------------
/*
迭代与普通循环的区别是：迭代时，循环代码中参与运算的变量同时是保存结果的变量，
当前保存的结果作为下一次循环计算的初始值。
递归与普通循环的区别是：循环是有去无回，而递归则是有去有回(因为存在终止条件)。
*/
///
/// 根据先序序列构建二叉树
///
///
///
public TreeNode CreateBinaryTree(List data)
{
return CreateBinaryTree(data.Count, data);
}
///
/// 根据先序递归创建二叉树
/// "A","B","D","#","#","E","#","#","C","#","F","#","#"
/// 1、首先判断集合的长度是否为0，为空树或者结点都已经赋值成功
/// 2、把存储每个结点的集合以及长度传参进来 index为结点下标
/// 3、先序遍历根左右首先确定根结点也就是集合的第0项，结点下标为0结点数据为A，从集合中删除结点数据
/// A，现在集合中有12数量
///
/// 4、然后进到获取左子树结点里面，结点B、D一样的执行原理，
/// 5、注意#的使用 #号代表结点没有左子树或者右子树 一个#代表没有左子树，但是有右子树 两个#左右子
/// 树都没有
///
/// 6、注意里面的顺序 根结点 左子树 如果出现#号 根据个数判断 一层一层的遍历
///
///
///
///
private TreeNode CreateBinaryTree(int count, Liststring> data)
{
if (data.Count == 0)
{
return null;
}
string d = data[0];
TreeNode node = null;
int index = count - data.Count;
if (d.Equals("#"))
{
node = null;
data.RemoveAt(0);//删除#
return node;//退出
}
node = new TreeNode(index,d);//创建新的结点
if (index == 0)
{
root = node;
}
data.RemoveAt(0);
node.LeftChild = CreateBinaryTree(count, data);
node.RightChild = CreateBinaryTree(count, data);
return node;
}
///
/// 求二叉树的高度
///
///
public int GetHeight()
{
return GetHeight(root);
}
private int GetHeight(TreeNode node)
{
//根结点为空 高度为0
if (node == null)
{
return 0;
}
else
{
Console.WriteLine(node.getData());
//求出左子树和右子树的高度
int i = GetHeight(node.LeftChild);
int j = GetHeight(node.RightChild);
//左右子树的高度就是树的深度 三目运算符判断哪棵子树的高度高 树的高度就是返回值
return (i 1 : i + 1;
}
}
///
/// 获取二叉树的结点数
///
///
public int GetSize()
{
return GetSize(root);
}
private int GetSize(TreeNode node)
{
//没有根结点即为空树 所以也就不存在结点
if (node == null)
{
return 0;
}
else
{
//不是空树的情况下 拿到所有的左子树的结点和右子树的结点 最后加上根结点
return 1 + GetSize(node.LeftChild) + GetSize(node.RightChild);
}
}
///
/// 前序遍历-------非迭代
/// 栈里面的操作A进栈-->B进栈-->D进栈-->D出栈-->B出栈-->E进栈-->E出栈-->A出栈-->C进栈-->C出栈
///-->F进栈-->F出栈
///
///
public void TheFirstOrder(TreeNode root)
{
Stack stack = new Stack();
TreeNode node = root;
//结点数不为空或者栈的数量大于0
while (node != null||stack.Count>0)
{
if (node != null)
{
Console.WriteLine("前序遍历"+"非迭代进栈"+node.getData());
stack.Push(node);//压栈访问
node = node.LeftChild;
}
else
{
//弹栈
node = stack.Pop();
node=node.RightChild;
}
}
}
///
/// 中序遍历-------非迭代
///
///
public void TheMidleOrder(TreeNode root)
{
Stack stack = new Stack();
TreeNode node = root;
while (node != null || stack.Count > 0)
{
if (node != null)
{
stack.Push(node);//压栈
node = node.LeftChild;
}
else
{
node = stack.Pop();//弹栈访问
Console.WriteLine("中序遍历" + "非迭代出栈" + node.getData());
node = node.RightChild;
}
}
}
///
/// 后序遍历-------非迭代
///
///
public void TheLastOrder(TreeNode root)
{
Stack stack = new Stack();
Stack output = new Stack();//新建一个中间栈来存储后序遍历的结果
TreeNode node = root;
//先序遍历根左右 后序遍历左右根 首先确定根结点 右子树 左子树 反过来就行
while (node != null || stack.Count > 0)
{
if (node != null)
{
output.Push(node);
stack.Push(node);
node = node.RightChild;
}
else
{
//弹栈
node = stack.Pop();
node = node.LeftChild;
}
}
while (output.Count > 0)
{
Console.WriteLine("后序遍历"+"非迭代"+output.Pop().getData());
}
}
}
}
三，Main方法调试
using System;
using System.Collections.Generic;
namespace BinaryDemo
{
class Program
{
static void Main(string[] args)
{
//方法一
/*
BinaryTree binarytree = new BinaryTree();
//在代码中手动的创建了二叉树
binarytree.CreateBinaryTree();
//先序遍历
binarytree.PreOrder(binarytree.root);
Console.WriteLine();
//中序遍历
binarytree.MidOrder(binarytree.root);
Console.WriteLine();
//后序遍历
binarytree.LastOrder(binarytree.root);
*/
//方法二
//用集合存储所有的结点
List data = new Liststring>();
//存储先序遍历每一个结点的数组
String[] dataArray = new string[] {"A","B","D","#","#","E","#","#","C","#","F","#","#"};
//遍历存储结点的数组存储到集合里面
foreach (string item in dataArray)
{
data.Add(item);
}
BinaryTree binary = new BinaryTree();
binary.CreateBinaryTree(data);//创建二叉树
int height = binary.GetHeight();//求二叉树的高度
Console.WriteLine("二叉树的高度是"+height);
int size = binary.GetSize();//过去所以的结点数
Console.WriteLine("二叉树的结点数是"+size);
binary.TheFirstOrder(binary.root);
Console.WriteLine();
binary.TheMidleOrder(binary.root);
Console.WriteLine();
binary.TheLastOrder(binary.root);
Console.ReadKey();
}
}
}
C#代码创建二叉树以及遍历二叉树
标签：字符串 数据 三目运算 初始 lse bin bsp 脚本 创建
原文地址：https://www.cnblogs.com/joemono/p/13178159.html
评论