GeneralTree 一般树形结构类

这个类用于一般树形，每个节点可以有多个分支，且数目不定。

可以看做是二叉树的变形形式。一个节点除了父指针外还有左右两个指针。

左指针为孩子节点的起始指针，右指针为同父节点的兄弟节点的指针

例如：

A的左指针为B，右指针为C，C的左指针为E，右指针为D

则，A，C,D为同兄弟节点。B为A的子节点，E为C的子节点。

这里使用到了 GeneralTreeNode类

这个树没有delete操作。因为我暂时不知道这个树类在什么地方会用到delete操作。而且这个树的查找是O(n)，相比与排序二叉树那是慢的太多了。不过这个树
在未知每个节点的分叉个数时，可以使用。其他的地方，个人认为还是尽量使用其他树形。

这个GeneralTree类还要进行大量的改进。

另外因为继承的缘故，这里大量使用dynamic_cast<>()方法。为了将GeneralTreeNode类转变为TreeNode类。这里我暂时还是不知道有
什么好的方法。

另外注意这里的Print函数，必须传入一个函数指针。因为树不知道你的打印数据方法和格式，其实我这里想了很多，最后感觉还是这种方法好点。感觉应该在TreeNo
de类中添加一个virtual Print（）函数来负责data的打印工作。

开始的时候，想过使用模板的方法，在TreeNode中添加一个模板参数。后来发现这样做对数据控制不利，而且我要改动非常多的代码，不如直接在GeneralTre
eNode类中添加一个virtual Print（）函数，然后传入指针参数去控制打印。

当然这样做的缺点在于如果还有类继承了TreeNode，而且也需要有print data
的方法。那么代码还要改动。但是现在的需求并没有看出这样做的趋势…所以暂时还是在GeneralTreeNode类中添加一个virtual
Print（）函数.

具体代码如下：

/* created by chico chen * date 2009/02/02 * 如需转载注明出处 / #ifndef
GENERAL_TREE #define GENERAL_TREE #include #include
#include “GeneralTreeNode.h” #include “BinaryTree.h” #include “List.h” using
namespace std; // this tree can not accept the same value. No element is the
same! // The class is not finished, and I am thinking where the class should
be used. // And there is no delete operator. template class
GeneralTree: public BinaryTree { private : GeneralTreeNode
GetTail(GeneralTreeNode* head) { // only the right piont can be used!
if(head != NULL) { while(head->right != NULL) { head =
(GeneralTreeNode)head->right; } } else { throw “head is null!”; } return
head; } // pre: parent != NULL and index is bigger than or equal with 0
GeneralTreeNode GetAChild(GeneralTreeNode* parent,int index) {
assert(index>=0); assert(parent!=NULL); GeneralTreeNode* head =
dynamic_cast<GeneralTreeNode>(parent->left); assert(head != NULL);
while(head->right != NULL && index–) { head =
dynamic_cast<GeneralTreeNode>(head->right); } if(NULL == head->right &&
index > 0) { throw “index is over float!”; } return head; } // this is deep
print(深度遍历) void DeepPrint(GeneralTreeNode* subRoot) { if(NULL != subRoot)
{ cout << subRoot->getData()<<" "<<endl;
DeepPrint(dynamic_cast<GeneralTreeNode>(subRoot->getLeft()));
DeepPrint(dynamic_cast<GeneralTreeNode>(subRoot->getRight())); } } // this
is level print(层次遍历) void LevelPrint(GeneralTreeNode* subRoot,void
(print)(T& data)) { List<GeneralTreeNode> queue; queue.Insert(new
ListNode<GeneralTreeNode>(subRoot),-1); while(!queue.IsEmpty()) {
ListNode<GeneralTreeNode>* temp = queue.GetHead(); GeneralTreeNode*
tempNode = temp->data; tempNode->Print(print); for(int i = 0; i <
tempNode->childLength; i++) { GeneralTreeNode* tempChildNode =
GetAChild(tempNode,i); queue.Insert(new ListNode<GeneralTreeNode*

(tempChildNode),-1); } queue.DeleteHead(); } } // pre: node != NULL // post:
true iff node is in the Tree, false iff node isn’t in the tree bool
Search(GeneralTreeNode* subRoot,GeneralTreeNode* node) { if(subRoot ==
NULL) { return false; } else if(node == subRoot) { return true; } else { bool
a = Search((GeneralTreeNode)subRoot->getLeft(),node); bool b =
Search((GeneralTreeNode)subRoot->getRight(),node); return a||b; } }
public: GeneralTree():BinaryTree() { this->root = NULL; } GeneralTree(T&
data):BinaryTree(data) { this->root->parent = NULL; } virtual ~GeneralTree() {
} // this function will call Insert (GeneralTreeNode* node,
GeneralTreeNode * parent) // and it will find the point of parentData. //
So it means if there are the same T in two node, it will return the first
node. //void Insert(T & dataCurrent, T & parentData) //{ //} // pre: node is
not in the tree. void Insert(GeneralTreeNode* node, GeneralTreeNode *
parent) { if(parent == NULL&& root == NULL) { // this is root root = node;
return; } if(root == NULL) { throw “no parent!”; } bool isFind =
Search(dynamic_cast<GeneralTreeNode>(root),parent); if(!isFind) { throw
“no such parent node!”; } isFind =
Search(dynamic_cast<GeneralTreeNode>(root),node); if(isFind) { throw
“there is the same node in the tree!”; } if(parent->left == NULL) {
parent->left = node; } else { GeneralTreeNode* tail =
GetTail((GeneralTreeNode)parent->left); tail->right = node; } node->parent
= parent; parent->childLength ++; } // this is deep print(深度遍历) void
DeepPrint() { DeepPrint(dynamic_cast<GeneralTreeNode>(this->root)); } //
this is level print(层次遍历) void LevelPrint(void (print)(T& data)) {
LevelPrint(dynamic_cast<GeneralTreeNode>(this->root),print); } }; #endif

这里可能还需要一个 List.h

文件，大家可以使用stl中的代替，也可以自己写，也可以使用我的…