首先,什么是树呢?
数的定义是递归的:
定义树是满足以下条件的,包含至少一个结点的有限集合:
(1)树中有一个特别指定的结点,称为根,或树根。
(2)其它结点划分成n>=0个不相交的集合T1…Tn ,每个集合又还是一棵树,但称为根的子树。
树的主要操作包括:求树的深度、求给定节点的子节点、兄弟节点、遍历树、插入子树、删除子树等等。因为树的定义本身就是递归的,所以在实际的程序中,很多操作也是通过递归来完成的。
树是如何表示的呢?有一种常用的表示方法,成为孩子、兄弟表示法,对于每个节点,通过孩子指针指向自己的子节点,通过兄弟指针指向自己右边的兄弟。
typedef char ElemType; //通过第一个孩子和下一个兄弟来确定整个树 typedef struct TNode { ElemType data; TNode *firstChild,*nextSibling; }TNode,*Tree; //初始化一个节点 Tree initTree(ElemType e) { Tree pT; pT = (TNode*)malloc(sizeof(TNode)); pT->firstChild = NULL; pT->nextSibling = NULL; pT->data = e; return pT; } //删除树 void deleteTree(Tree *T) { if(NULL == *T) return ; deleteTree(&(*T)->nextSibling); deleteTree(&(*T)->firstChild); free(*T); *T = NULL; } //遍历树并打印 void printTree(Tree T) { if(NULL == T) return; else { printf("%c ",T->data); /* //如果不习惯递归,可以这样写 Tree p = T->firstChild; while(p != NULL) { printTree(p); p = p->nextSibling; } */ //注释掉的部分等价于如下两行: printTree(T->firstChild); printTree(T->nextSibling); } } //求树的高度 int treeDepth(Tree T) { int hmax = 0; int subTreeDepth = 0; if(NULL == T) return 0; Tree p = T->firstChild; while(p != NULL) { subTreeDepth = treeDepth(p); p = p->nextSibling; if(subTreeDepth > hmax) hmax=subTreeDepth; } return hmax+1; } //全局变量记录找到的元素的地址 Tree result; void locateElem(Tree T,ElemType e) { if(NULL == T) return; if(T->data == e) result = T; /* Tree p = T->firstChild; while(p != NULL) { locateElem(p,e); p = p->nextSibling; } */ locateElem(T->firstChild,e); locateElem(T->nextSibling,e); } //返回子节点的指针 Tree findChild(Tree T,ElemType e) { result = NULL; locateElem(T,e); //如果没有找到或者该节点是叶子节点,返回空 if(NULL == result && NULL == result->firstChild) return NULL; else return result->firstChild; } //返回兄弟节点的指针 Tree findSibling(Tree T,ElemType e) { result = NULL; locateElem(T,e); //如果没有找到或者该节点没有右兄弟,返回空 if(NULL == result && NULL == result->nextSibling) return NULL; else return result->nextSibling; } //插入子树 bool insertTree(Tree T,Tree Tadd,ElemType e) { result = NULL; locateElem(T,e); if(result != NULL) { Tadd->nextSibling = result->firstChild; result->firstChild = Tadd; return true; } else return false; } //删除子树 bool deleteSubTree(Tree T,ElemType e) { result = NULL; locateElem(T,e); //先判断result有什么节点 if(result->firstChild != NULL) { deleteTree(&(result->firstChild)); return true; } else return false; }
初始化节点时要注意,这里通过函数的返回值将动态分配的节点带出去了,但是并没有说明节点之间的关系,所以需要在主函数中手动的为每个节点连接它的孩子和兄弟指针。对于树的核心操作,毫无疑问是如何递归的遍历一棵树。我们的作法是这样的:对于一个节点,先访问它的数据域,然后通过孩子指针来访问它的孩子,一直到沿着这条分支的叶子节点,此时,访问这个节点的兄弟,直到所有的兄弟都访问过了,然后回退到上一节点,访问它的兄弟,依次类推。
在程序中,有两种写法,以printTree为例,注释掉的部分更贴近于我们描述,而实际使用的代码则更加抽象、简洁。按理来说,二者是可以相互转化的,但是对于在求树的高度这一块,我并没有好的办法解决。
对于通过递归操作操作的产找,有一个很烦人的问题,就是找到以后如何把指向这个节点的指针带出来。我试了很多方法,都不管用,无奈之下使用了全局变量。所以每次进行跟查找有关的操作时(查找、指定位置插入、指定位置删除),都必须先初始化result指针为NULL。如果读者有更好的办法,欢迎指教。
这里并没有给出通过一个节点来查找到它的父节点的操作,虽然这个工作“可能”可以完成,但最简单明了的办法就是在结构体内部增加一个指向parent的指针。