树(Tree)是 n(n≥0)个相同类型的数据元素的有限集合。树中的数据元素叫结点(Node)。n=0 的树称为空树(Empty Tree)；对于 n＞0 的任意非空树 T 有： （1）有且仅有一个特殊的结点称为树的根(Root)结点，根没有前驱结点； （2）若n＞1，则除根结点外，其余结点被分成了m(m＞0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这棵树的子树(Subtree)
二叉树(Binary Tree)是 n(n≥0)个相同类型的结点的有限集合。n=0 的二叉树称为空二叉树(Empty Binary Tree)；对于 n＞0 的任意非空二叉树有：
（1）有且仅有一个特殊的结点称为二叉树的根(Root)结点，根没有前驱结点；
（2）若n＞1，则除根结点外，其余结点被分成了 2 个互不相交的集合TL，TR，而TL、TR本身又是一棵二叉树，分别称为这棵二叉树的左子树(Left Subtree)和右子树(Right Subtree)。
1）满二叉树(Full Binary Tree)：如果一棵二叉树只有度为 0 的结点和度为 2的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树
（2）完全二叉树(Complete Binary Tree)：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k，有 n 个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树
二叉树的存储结构主要有三种：顺序存储结构、二叉链表存储结构和三叉链表存储结构
二叉链表存储结构的类实现
二叉树的二叉链表的结点类有3个成员字段：数据域字段data、左孩子引用域字段lChild和右孩子引用域字段rChild。
public class Node<T> { private T data;//数据域 public T Data { get { return data; } set { data = value; } } private Node<T> lchild;//左孩子 public Node<T> Lchild { get { return lchild; } set { lchild = value; } } private Node<T> rchild;//右孩子 public Node<T> Rchild { get { return rchild; } set { rchild = value; } } public Node() { data = default(T); lchild = null; rchild = null; } public Node(T data ) { this.data = data; lchild = null; rchild = null; } public Node(T data, Node<T> lchild, Node<T> rchlid) { this.data = data; this.lchild = lchild; this.rchild = rchild; } }
不带头结点的二叉树的二叉链表比带头结点的二叉树的二叉链表的区别与不带头结点的单链表与带头结点的单链表的区别一样。
下面只介绍不带头结点的二叉树的二叉链表的类
public class BinaryTree<T> { private Node<T> head; //头引用 internal Node<T> Head { get { return head; } set { head = value; } } public BinaryTree() { head = null; } public BinaryTree(T data) { Node<T> p = new Node<T>(data); head = p; } public BinaryTree(T data, Node<T> lchild, Node<T> rchild) { Node<T> p = new Node<T>(data, lchild, rchild); head = p; } // 二叉树是否为空 public bool IsEmptyTree() { if (null != head) { return false; } else { return true; } } // 获取根节点 public Node<T> GetRoot() { if (IsEmptyTree()) { return null; } return head; } //获取结点的左孩子结点 public Node<T> GetLChild(Node<T> p) { return p.Lchild; } // right child public Node<T> GetRChild(Node<T> p) { return p.Rchild; } //将结点p的左子树插入值为val的新结点， //原来的左子树成为新结点的左子树 public void InsertL(T val, Node<T> p) { Node<T> temp = new Node<T>(val); temp.Lchild = p.Lchild; p.Lchild = temp; } //将结点p的右子树插入值为val的新结点， //原来的右子树成为新结点的右子树 public void InsertR(T val, Node<T> p) { Node<T> tmp = new Node<T>(val); tmp.Rchild = p.Rchild; p.Rchild = tmp; } //若p非空，删除p的左子树 public Node<T> DeleteL(Node<T> p) { if (p == null || p.Lchild == null) { return null; } Node<T> temp = p.Lchild; p.Lchild = null; return temp; } //若p非空，删除p的右子树 public Node<T> DeleteR(Node<T> p) { if (p == null || p.Rchild == null) { return null; } Node<T> temp = p.Rchild; p.Rchild = null; return temp; } //判断是否是叶子结点 public bool IsLeaf(Node<T> p) { if ( p != null && p.Lchild == null && p.Rchild == null) { return true; } return false; } // 销毁二叉树 public void DestroyTree( Node<T> node ) { if ( node != null ) { if (node.Lchild != null) { node.Lchild = null; } if (node.Rchild != null) { node.Rchild = null; } node = null; } } // 1、先序遍历（DLR） public void PreOredr(Node<T> root) { if ( root == null ) { //Console.WriteLine("树为空，无法遍历"); return; } //处理根结点 Console.WriteLine("{0}", root.Data); //先序遍历左子树 PreOredr(root.Lchild); //再遍历右子树 PreOredr(root.Rchild); } /* 2、中序遍历（LDR） 中序遍历的基本思想是：首先中序遍历根结点的左子树，然后访问根结点， 最后中序遍历其右子树 */ public void InOrder(Node<T> root) { if (root.Lchild != null) { InOrder(root.Lchild); } Console.WriteLine( root.Data ); if (root.Rchild != null) { InOrder(root.Rchild); } } /* 3、后序遍历（LRD） 后序遍历的基本思想是：首先后序遍历根结点的左子树，然后后序遍历根结 点的右子树，最后访问根结点 */ public void PostOrder(Node<T> root) { if (root.Lchild != null) { PostOrder(root.Lchild); } if (root.Rchild != null) { PostOrder(root.Rchild); } Console.WriteLine(root.Data); } /* 层序遍历的基本思想是：由于层序遍历结点的顺序是先遇到的结点先访问， 与队列操作的顺序相同。所以，在进行层序遍历时，设置一个队列,将根结点引 用入队，当队列非空时，循环执行以下三步： （1） 从队列中取出一个结点引用，并访问该结点； （2） 若该结点的左子树非空，将该结点的左子树引用入队； （3） 若该结点的右子树非空，将该结点的右子树引用入队 */ public void LevelOrder(Node<T> root) { if ( root == null ) { return; } Queue<Node<T>> queue = new Queue<Node<T>>(); queue.Enqueue(root); while ( queue.Count > 0 ) { //结点出队 Node<T> temp = queue.Dequeue(); //处理当前结点 Console.WriteLine("结点出队{0}", temp.Data); //将当前结点的左孩子结点入队 if (temp.Lchild != null) { queue.Enqueue(temp.Lchild); } if (temp.Rchild != null) { queue.Enqueue(temp.Rchild); } } } }
// 测试
BinaryTree<char> tree = new BinaryTree<char>(); Node<char> p = new Node<char>(‘A‘); Node<char> p1 = new Node<char>(‘B‘); tree.InsertL(‘B‘, p); tree.InsertL(‘D‘, p); tree.InsertR(‘E‘, p1); tree.InsertR(‘C‘, p); tree.InsertR(‘F‘, p); tree.InsertR(‘G‘, p); Console.WriteLine("先序遍历*******************************"); tree.PreOredr(p); //tree.PreOredr(p1); Console.WriteLine("中序遍历*******************************"); tree.InOrder(p); Console.WriteLine("后序遍历*******************************"); tree.PostOrder(p); Console.WriteLine("层序遍历*******************************"); tree.LevelOrder(p);