C++二叉树及其算法和应用...

C++树形结构是一类重要的非线性数据，树和二叉树是常用的树形结构。
　　二叉树的概念
　　◆ 1、树的概念
　　树（Tree）是由n（n≥0）个结点组成的有限集合。如n=0，称为空树。
　　非空树有一个特定的结点，它只有直接后继，没有直接前驱，称之为根（root）。除根以外的其它结点划分为m（m≥0）个互不相交的有限集合T0，T1，……，Tm-1，每个集合又是一棵树，称为根的子树（subtree）。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。这是一个递归方法定义的数据结构，如下图所示。
　　图
　　结点，包括数据项和多个指针项，指针项数目并不固定，且无次序。
　　结点的度，结点所拥有的子树数量。
　　叶结点，度为0的结点，如G，I，J，K，L，M，N，O结点。
　　分支结点，度≥1的结点。
　　孩子结点，若结点x有子树，则子树根结点即为x的孩子结点。
　　双亲结点，若结点x有孩子，它即为孩子的双亲。
　　兄弟结点，同一双亲的结点互称为兄弟。
　　结点的层次，从根到该结点所经路径上的分支条数。
　　树的深度,树中结点的层次数。
　　树的度，树中结点度的最大值。
　　◆ 2、二叉树的概念
　　二叉树（Binary Tree）是另一种独立的树形结构。二叉树是结点的一个有限集合，该集合或为空，或是由一个根结点及两棵树分别称为左子树和右子树的（注意有左右之分）互不相交的二叉树组成，其中左右子树分别可以为空子树或均为空树。这也是一个递归的定义。二叉树的特点是：每个结点最多两个孩子，并且子树有左右之分。
　　二叉树的基本性质：
　　二叉树的第i层上最多有2i-1(i>=1)个结点；
　　深度为h的二叉树中最多有2h-1个结点；
　　在任一棵二叉树中，有n0叶子结点，有n2个度为2的结点，则有n0=n2+1。
　　◆ 3、链式二叉树的结点类模板
　　先在此定义结点类模板，下一节在其基础上定义二叉树类模板。（查看源码）
　　二叉树的遍历
　　◆ 1、所谓二叉树的遍历（binary tree traversal），就是遵从某种次序，查巡二叉树的所有结点，每个结点都被访问一次，而且仅访问一次。所谓“访问”指对结点施行某些操作，但不破坏它原来的数据结构。
　　遍历二叉树有不同次序，规定先左后右，令L，R，V分别代表遍历一个结点的左右子树和访问该结点的操作，有三种方式： 前序遍历（VLR）、 中序遍历（LVR）、 后序遍历（LRV）
　　◆ 2、链式二叉树类模板
　　template<typename T>class BinaryTree{
　　Node<T> *root; //二叉树的根指针
　　void InOrder(Node<T> *Current); //中序遍历
　　void PreOrder(Node<T> *Current); //前序遍历
　　void PostOrder(Node<T> *Current); //后序遍历
　　void Insert(const T &data,Node<T> * &b);
　　//插入结点，参数为引用！
　　void Destory(Node<T> * Current); //删除树
　　public:
　　BinaryTree(){root=NULL;} //空树构造函数
　　~BinaryTree(){Destory(root);} //析构函数
　　void Creat(T* data,int n); //建立（排序）二叉树
　　void InOrder(){InOrder(root);}
　　//中序遍历，公有函数为接口
　　void PreOrder(){PreOrder(root);}
　　//前序遍历，公有函数为接口
　　void PostOrder(){PostOrder(root);}
　　//后序遍历，公有函数为接口
　　};
　　二叉排序树
　　二叉排序树（Binary Sorting Tree）又称二叉搜索树（Binary Search Tree），是一种特殊结构的二叉数，作为一种排序和查找的手段，对应有序表的对半查找，通常亦被称为数表。其定义也是递归的。
　　二叉排序树的定义：二叉排序树或者是空树或者是具有下述性质的二叉数，其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于等于根结点的数据值，左子树和右子树又各是一棵二叉排序树。
　　二叉排序树用中序遍历就可以得到由小到大的有序序列，如下图可得有序序列｛8，10，11，12，15，16，18，22，24，26，29｝。
　　图 二叉排序树例
　　二叉排序树的结点插入（可生成排序二叉树）生成算法：对任意一组数据元素序列{a0，a1，a2，…，an-1}。要生成二叉排序树的过程为：
　　令a0为二叉树的根结点。
　　若a1<a0，令a1为a0左子树的根结点，否则a1为a0右子树的根结点。
　　如ai小于根结点，则去左子树，否则去右子树，按此法查找，直到成为空树，则安放此位置。这步就是插入算法。