|
图6.12二叉树的递归定义
|
|
D
|
|
L
|
|
R
|
点击展开示例
using ...System; 
public class Node ...{ 
//成员变量 private object _data; //数据 private Node _left; //左孩子 private Node _right; //右孩子 public object Data 
...{ get ...{ return _data; } 
} public Node Left //左孩子 ...{ get ...{ return _left; } set ...{ _left = value; } } public Node Right //右孩子 ...{ get ...{ return _right; } set ...{ _right = value; } } //构造方法 public Node(object data) ...{ _data = data; } public override string ToString() ...{ return _data.ToString(); } } 战场展开示例using ...System; public class BinaryTree ...{ //成员变量 private Node _head; //头指针 private string cStr; //用于构造二叉树的字符串 public Node Head //头指针 ...{ get ...{ return _head; } } //构造方法 public BinaryTree(string constructStr) ...{ cStr = constructStr; _head = new Node(cStr[0]); //添加头结点 Add(_head, 0); //给头结点添加孩子结点 } private void Add(Node parent, int index) ...{ int leftIndex = 2 * index + 1; //计算左孩子索引 if (leftIndex < cStr.Length) //如果索引没超过字符串长度 ...{ if (cStr[leftIndex] != '#') //'#'表示空结点 ...{ //添加左孩子 parent.Left = new Node(cStr[leftIndex]); //递归调用Add方法给左孩子添加孩子节点 Add(parent.Left, leftIndex); } } int rightIndex = 2 * index + 2; if (rightIndex < cStr.Length) ...{ if (cStr[rightIndex] != '#') ...{ //添加右孩子 parent.Right = new Node(cStr[rightIndex]); //递归调用Add方法给右孩子添加孩子节点 Add(parent.Right, rightIndex); } } } public void PreOrder(Node node) //先序遍历 ...{ if (node != null) ...{ Console.Write(node.ToString()); //打印字符 PreOrder(node.Left); //递归 PreOrder(node.Right); //递归 } } public void MidOrder(Node node) //中序遍历 ...{ if (node != null) ...{ MidOrder(node.Left); //递归 Console.Write(node.ToString()); //打印字符 MidOrder(node.Right); //递归 } } public void AfterOrder(Node node) //后继遍历 ...{ if (node != null) ...{ AfterOrder(node.Left); //递归 AfterOrder(node.Right); //递归 Console.Write(node.ToString()); //打印字符 } } } 点击展开示例using ...System; class Demo6_1 ...{ static void Main(string[] args) ...{ //使用字符串构造二叉树 BinaryTree bTree = new BinaryTree("ABCDE#F"); bTree.PreOrder(bTree.Head); //先序遍 Console.WriteLine(); bTree.MidOrder(bTree.Head); //中序遍 Console.WriteLine(); bTree.AfterOrder(bTree.Head); //后序遍 Console.WriteLine(); } } 点击展开示例public void LevelOrder() //宽度优先遍历 ...{ Queue queue = new Queue(); //声明一个队例 queue.Enqueue(_head); //把根结点压入队列 while (queue.Count > 0) //只要队列不为空 ...{ Node node = (Node)queue.Dequeue(); //出队 Console.Write(node.ToString()); //访问结点 if (node.Left != null) //如果结点左孩子不为空 ...{ //把左孩子压入队列 queue.Enqueue(node.Left); } if (node.Right != null) //如果结点右孩子不为熔 ...{ //把右孩子压入队列 queue.Enqueue(node.Right); } } } 点击展开示例using ...System; class Demo6_2 ...{ static void Main(string[] args) ...{ //使用字符串构造二叉树 BinaryTree bTree = new BinaryTree("ABCDE#F"); bTree.LevelOrder(); } }