VC++2012编程演练数据结构《23》二叉树排序
在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。
　在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
　尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
　　树和二叉树的2个主要差别：
　　1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
　　2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树
基本形态
　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
　　(1)空二叉树——(a)；
　　 (2)只有一个根结点的二叉树——(b)；
　　(3)只有左子树——(c)；
　　(4)只有右子树——(d)；
　　(5)完全二叉树——(e)
　　注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
重要概念
　　(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。　
　　(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树,。
　　(3)深度——二叉树的层数，就是高度。
性质
　　(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
　　(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
　　(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
　　(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
　　若I为结点编号则 如果I<>1，则其父结点的编号为I/2；
　　如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
　　如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
　　(6)给定N个节点，能构成h(N)种不同的二叉树。
　　h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

　　（7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

我们创建一个工程

类的实现如下

代码下载



http://download.csdn.net/detail/yincheng01/4789514