二叉树的基础定义可自行百度。
二叉树的遍历方法,根据数据节点的先后顺序,可分成3种方式,假设一个节点的,左孩子为L,根节点为D,右孩子为R,那么访问顺序有3中。DLR先序,LDR中序,LRD后序(左和右是并列的。所以不需要有DRL之类的顺序)。
此处以DRL为例。
算法描述如下:
首先访问根结点。
然后如果有左孩子,则对于左孩子也采用DRL的遍历规则。没有就忽略。
然后如果有右孩子,则对右孩子也采用DRL的遍历规则。没有就忽略。
因此可以看到,是可以通过递归算法实现遍历的。
LDR和LRD的遍历也类似。
二叉树的构成可以采用数组或者链表方式。各有优缺点,此处采用链表方式,更为灵活。
下例代码中,采用链表的方式,分别构建了2个不同的树,并且对其进行遍历。程序代码和结果如下。
字母树
数字树
- using System;
-
using System.Collections.Generic;
-
using System.Linq;
-
using System.Text;
-
-
namespace binarytree
-
{
- #region 节点的定义
-
class node
- {
-
public string nodevalue;
-
public node leftchild, rightchild;
-
-
public node()
- { }
-
public node(string value)
- {
- nodevalue = value;
- }
-
-
public void assignchild(node left, node right)
- {
-
this.leftchild = left;
-
this.rightchild = right;
- }
-
-
public bool hasleftchild
- {
-
get
- {
-
return (leftchild != null);
- }
- }
-
-
public bool hasrightchild
- {
-
get
- {
-
return (rightchild != null);
- }
- }
-
}
- #endregion
-
- #region 主程序
-
class Program
- {
-
static void Main(string[] args)
- {
-
node node_a = new node("a");
-
node node_b = new node("b");
-
node node_c = new node("c");
-
node node_d = new node("d");
-
node node_e = new node("e");
-
node node_f = new node("f");
-
node node_g = new node("g");
-
node node_h = new node("h");
-
node node_i = new node("i");
-
- node_a.assignchild(node_b, node_c);
- node_b.assignchild(node_d, node_e);
- node_c.assignchild(node_f, node_g);
- node_e.assignchild(node_h, node_i);
-
-
preorder_visit(node_a);
- Console.WriteLine();
-
inorder_visit(node_a);
- Console.WriteLine();
-
postorder_visit(node_a);
- Console.WriteLine();
-
-
-
-
node node_1 = new node("1");
-
node node_2 = new node("2");
-
node node_3 = new node("3");
-
node node_4 = new node("4");
-
node node_5 = new node("5");
-
node node_6 = new node("6");
-
node node_7 = new node("7");
-
node node_8 = new node("8");
-
-
- node_1.assignchild(node_2, node_3);
- node_2.assignchild(node_4, node_5);
-
node_3.assignchild(null, node_7);
-
node_5.assignchild(node_6, null);
-
node_7.assignchild(node_8, null);
-
-
preorder_visit(node_1);
- Console.WriteLine();
-
inorder_visit(node_1);
- Console.WriteLine();
-
postorder_visit(node_1);
- Console.WriteLine();
- }
-
-
-
static void preorder_visit(node Anode)
- {
- Console.Write(Anode.nodevalue);
-
-
if (Anode.hasleftchild)
- {
- preorder_visit(Anode.leftchild);
- }
-
-
if (Anode.hasrightchild)
- {
- preorder_visit(Anode.rightchild);
- }
- }
-
-
static void inorder_visit(node Anode)
- {
-
if (Anode.hasleftchild)
- {
- inorder_visit(Anode.leftchild);
- }
-
- Console.Write(Anode.nodevalue);
-
-
if (Anode.hasrightchild)
- {
- inorder_visit(Anode.rightchild);
- }
- }
-
-
static void postorder_visit(node Anode)
- {
-
if (Anode.hasleftchild)
- {
- postorder_visit(Anode.leftchild);
- }
-
-
if (Anode.hasrightchild)
- {
- postorder_visit(Anode.rightchild);
- }
-
- Console.Write(Anode.nodevalue);
-
- }
-
-
}
- #endregion
- }
运行结果如下:
本文转自cnn23711151CTO博客,原文链接:http://blog.51cto.com/cnn237111/841507 ,如需转载请自行联系原作者