数据结构回顾：树与二叉树详解（上）

本文探讨了树与二叉树的基本结构和遍历算法。树是一种非线性结构，广泛应用于计算机中，如Windows资源管理器和应用程序菜单。文章详细介绍了树的基本概念和术语，包括根节点、内部节点、叶子节点以及节点的层次和深度。接着，文中通过猜数字游戏引出了二叉树的概念，并讨论了二叉树的顺序和链式存储结构。最后，文章提供了C#代码，展示了二叉树节点的定义、创建以及递归遍历方法的前、中、后序遍历实现。

前面所讨论的线性表元素之间都是一对一的关系，今天我们所看到的结构各元素之间却是一对多的关系。树在计算机中有着广泛的应用，甚至在计算机的日常使用中，也可以看到树形结构的身影，如下图所示的Windows资源管理器和应用程序的菜单都属于树形结构。树形结构是一种典型的非线性结构，除了用于表示相邻关系外，还可以表示层次关系。本文重点讨论树与二叉树的基本结构和遍历算法等内容。

（1）不同的节点：根节点、内部节点、叶子节点以及节点的度

（2）节点的关系：双亲与孩子，爸爸回来了，爸爸去哪儿？

（3）节点的层次：结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度（Depth）或高度。

回忆一下，当年某电视节目中会让游戏参与者猜一个产品的价格，如果参与者在限定时间内猜对了，那么他就可以获得这个产品。很多人都是一点点的提高数值来猜，但是这样猜会很没有效率。因此，很多聪明人都知道需要利用折半查找的思想去猜测。假定某个产品在100元的范围内，那么可以在7次之内猜出结果来，如下图所示：（由于是100以内的正整数，所以我们先猜50（100的一半），被告之“大了”，于是再猜25（50的一半），被告之“小了”，再猜37（25与50的中间数），小了，于是猜43，大了，40，大了，38，小了，39，完全正确。）

如上图所示，对于这种在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错，正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点。结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

But，考虑一种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配2的k次方-1个存储单元空间，这显然是对存储空间的浪费，所以，顺序存储结构一般只适用于完全二叉树。

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

（1）二叉树节点的定义：

        static void MyBinaryTreeBasicTest()        {            // 构造一颗二叉树，根节点为"A"            MyBinaryTree<string> bTree = new MyBinaryTree<string>("A");            Node<string> rootNode = bTree.Root;            // 向根节点"A"插入左孩子节点"B"和右孩子节点"C"            bTree.InsertLeft(rootNode, "B");            bTree.InsertRight(rootNode, "C");            // 向节点"B"插入左孩子节点"D"和右孩子节点"E"            Node<string> nodeB = rootNode.lchild;            bTree.InsertLeft(nodeB, "D");            bTree.InsertRight(nodeB, "E");            // 向节点"C"插入右孩子节点"F"            Node<string> nodeC = rootNode.rchild;            bTree.InsertRight(nodeC, "F");            // 前序遍历            Console.WriteLine("---------PreOrder---------");            bTree.PreOrder(bTree.Root);            // 中序遍历            Console.WriteLine();            Console.WriteLine("---------MidOrder---------");            bTree.MidOrder(bTree.Root);            // 后序遍历            Console.WriteLine();            Console.WriteLine("---------PostOrder---------");            bTree.PostOrder(bTree.Root);        }</string></string></string></string></string>

（2）运行结果：

本文实现的C#版二叉树参考代码下载：http://pan.baidu.com/s/1eQ1xmXs

（1）程杰，《大话数据结构》

（2）陈广，《数据结构（C#语言描述）》

（3）段恩泽，《数据结构（C#语言版）》

（4）杨俊明，《数据结构C#版笔记—树与二叉树》

（5）Frank Fan，《万丈高楼平地起之C#实现二叉树操作》

作者：周旭龙

出处：http://edisonchou.cnblogs.com

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接。

以上就是《数据结构回顾：树与二叉树详解（上）》的详细内容，更多关于树,二叉树,遍历算法,顺序存储,链式存储的资料请关注golang学习网公众号！