关键字:
二叉树,查找,(breadth-first algrithm) ---前序遍历,中序遍历,后序遍历,(depth-first algrithm)-层次遍历。
摘要:
树是一种非常重要的数据结构,Binary Tree则是树型结构中应用最为广泛。本文给出了C#版本的二叉树的建立,查找,以及各种递归和非递归的遍历算法。
代码如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace DS
{
public class Tree
{
public Tree(int data)
{
_data = data;
leftChild = null;
rightChild = null;
}
private int _data;
private Tree leftChild;
private Tree rightChild;
public void PreOrder()
{
if(this != null)
{
Console.Write("{0} ", _data);
if(leftChild!=null)
leftChild.PreOrder();
if(rightChild!=null)
rightChild.PreOrder();
}
}
public void InOrder()
{
if (this != null)
{
if (leftChild != null)
leftChild.InOrder();
Console.Write("{0} ", _data);
if (rightChild != null)
rightChild.InOrder();
}
}
public void PostOrder()
{
if (this != null)
{
if (leftChild != null)
leftChild.PostOrder();
if (rightChild != null)
rightChild.PostOrder();
Console.Write("{0} ", _data);
}
}
public void PostOrderWithoutIretation()
{
Stack<Tree> stack = new Stack<Tree>();
Tree pre=null, temp;
temp=this;
while (temp != null || stack.Count != 0)
{
while (temp != null)
{
stack.Push(temp);
temp = temp.leftChild;
}
temp = stack.First<Tree>();
if (temp.rightChild == null || temp.rightChild==pre)
{
temp=stack.Pop();
Console.Write("{0} ", temp._data);
pre = temp;
temp = null;
}
else
{
temp = temp.rightChild;
}
}
}
public void InOrderWithoutIretation()
{
Stack<Tree> stack = new Stack<Tree>();
Tree temp;
temp = this;
while (temp!=null || stack.Count != 0)
{
while (temp != null)
{
stack.Push(temp);
temp = temp.leftChild;
}
temp = stack.Pop();
Console.Write(" {0} ", temp._data);
temp = temp.rightChild;
}
}
public void LevelOrder()
{
Queue<Tree> queue = new Queue<Tree>();
queue.Enqueue(this);
Tree temp;
while (queue.Count != 0)
{
temp=queue.Dequeue();
Console.Write("{0} ", temp._data);
if(temp.leftChild!=null)
queue.Enqueue(temp.leftChild);
if(temp.rightChild!=null)
queue.Enqueue(temp.rightChild);
}
}
public void Search(int data, out Tree p, out Tree q)
{
p = this;
q = null;
while (p != null)
{
q = p;
if (p._data>data)
p = p.leftChild;
else if (p._data < data)
p = p.rightChild;
else
break;
}
}
public bool InsertNode(int data)
{
Tree newNode = new Tree(data);
Tree p,q;
Search(data, out p, out q);
if (p!= null)
return true;
else
{
if (q._data >data)
q.leftChild =newNode;
else
q.rightChild = newNode ;
}
return false;
}
public void PreOrderWithouIreration()
{
Tree temp;
temp = this;
Stack<Tree> stack=new Stack<Tree>();
stack.Push(this);
while (stack.Count != 0)
{
temp = stack.Pop();
Console.Write("{0} ", temp._data);
if (temp.rightChild!=null)
stack.Push(temp.rightChild);
if (temp.leftChild!=null)
stack.Push(temp.leftChild);
}
}
}
class Program
{
static void Main(string[] args)
{
Tree Root = new Tree(10);
Root.InsertNode(5);
Root.InsertNode(14);
Root.InsertNode(9);
Root.InsertNode(13);
Root.InsertNode(8);
Console.WriteLine("pre order");
Root.PreOrder();
Console.WriteLine("pre order without iteration\n");
Root.PreOrderWithouIreration();
Console.WriteLine("\nIn order");
Root.InOrder();
Console.WriteLine("\nInOrder without Iteration");
Root.InOrderWithoutIretation();
Console.WriteLine("\nPost Order:");
Root.PostOrder();
Console.WriteLine("\nPost Order without Iteration");
Root.PostOrderWithoutIretation();
Console.WriteLine("\nlevel order");
Root.LevelOrder();
Console.Read();
}
}
}
分享到:
相关推荐
用函数实现如下二叉排序树算法: (1) 插入新结点 (2) 前序、中序、后序遍历二叉树 (3) 中序遍历的非递归算法 (4) 层次遍历二叉树 (5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) (6) ...
vs2010环境下c++实现二叉排序树,内容:有建立二叉排序树--非递归;创建二叉排序树--递归法;查找二叉排序树的某个值域的值为k的结点--递归法--含有”前序遍历“思想;二叉树的前序遍历,中序遍历,后序遍历...
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
2)对二叉排序树进行先根、中根、 和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 例如,a 为根,左右孩子是 bc,b 的孩子是 de,c 的孩子是 fg. 也可以像...
/*选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等) 【实验内容】 必做内容 程序的菜单功能项如下: 1----...
树 * 字典树 ...* 二叉查找树-从有序数组中构造二叉查找树 * 二叉查找树-从有序链表构造平衡的二叉查找树 * 二叉树-的最大深度 数组&字符串 查找排序 排列组合 动态规划 树 链表 数学 位运算 编程之美
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).
经典的数据结构问题:二叉树非递归遍历算法实现 二叉树递归遍历算法实现
数据结构DFS深度优先遍历非递归算法实现,是自己编写的,可靠。
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
这个程序实现了二叉查找树的删除,增加,先序遍历,后序遍历,中序遍历,还有一些非递归和层次遍历!
二叉查找与递归二叉查找算法
小小学习,C语言数据结构,中序遍历二叉树非递归算法
本人写的二叉寻找树的建立,遍历 用逗号分隔。。。。
二叉树的中序、前序、后序的递归、非递归遍历算法
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
本代码是在windows平台下vs2008上编译通过,包含搜索二叉树的插入,查找和删除算法(采用递归和非递归两种方法)。包含全部在平台下的文件,解压可以直接运行。
用函数实现如下二叉排序树算法:(1) 插入新结点(2) 前序、中序、后序遍历二叉树(3) 中序遍历的非递归算法(4) 层次遍历二叉树(5) 在二叉树中查找给定关键字(函数返回值为成功1,失败0) Input 第一行:准备...