看数据结构写代码（31）树的二叉链表的实现

首先向大家推荐一个很棒的介绍树，二叉树，森林之间转换的博客：点击打开链接

源码网盘地址：点击打开链接

树的二叉链表和二叉树的二叉链表在存储结构上是一致的，但是具体含义不同；树节点的两个指针指向第一个孩子节点和右兄弟节点，而二叉链表指向左，右子树。这就表示了他们的操作既有相同的地方，又有不同的地方。

例如树的先序遍历，销毁子树，求树的长度和二叉树的操作是一样的。

void treeClear(Tree * tree){if (*tree != NULL){treeClear(&((*tree)->firstChild));treeClear(&((*tree)->firstChild));free(*tree);*tree = NULL;}}void treeDestory(Tree * tree){treeClear(tree);}//先跟节点遍历…在孩子void preOrderTraverse(Tree tree){if (tree != NULL){printf("%c\t",tree->data);preOrderTraverse(tree->firstChild);preOrderTraverse(tree->nextSibling);}}//树求长度和二叉树求长度一样.int treeLen(Tree tree){if (tree != NULL){return treeLen(tree->firstChild) + treeLen(tree->nextSibling) + 1;}return 0;}树的后序遍历（没有右子树，所以没有中序遍历）和二叉树的中序遍历时一样的。void postOrderTraverse(Tree tree){if (tree != NULL){/*postOrderTraverse(tree->firstChild);postOrderTraverse(tree->nextSibling);printf("%c\t",tree->data);*/postOrderTraverse(tree->firstChild);printf("%c\t",tree->data);postOrderTraverse(tree->nextSibling);}}树的层序遍历，和二叉树在形式上是类似的，树是将所有孩子节点入队列，而二叉树是将左右子树入队列//层序遍历（根二叉树的遍历略有不同）void levelOrderTraverse(Tree tree){if (tree != NULL){LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){Tree father;dequeue(&queue,&father);printf("%c\t",father->data);Tree child = father->firstChild;//等于第一个孩子////将所有孩子节点入队(相当于二叉树的将左右子树入队）while (child != NULL){enqueue(&queue,child);child = child->nextSibling;}}queueDestory(&queue);}}在求树的深度得注意：二叉树是求左右子树取最大值 + 1，而树的左子树代表孩子节点，右子树代表的是兄弟，所以右子树不 + 1.//求树的深度 int treeDepth(Tree tree){if (tree != NULL){int leftDepth = treeDepth(tree->firstChild) + 1;int rightDepth = treeDepth(tree->nextSibling);//注意从右子树返回的没有加1,因为右子树返回的是兄弟节点的深度return leftDepth > rightDepth ? leftDepth : rightDepth;}return 0;}求树的叶子节点得注意，二叉树是遇到左右子树为空就返回1，若是树在遇到 firstChild为NULL 就返回，那样就没有判断兄弟节点上的叶子节点。int treeLeafCount(Tree tree){if (tree != NULL){if (tree->firstChild == NULL)//第一个孩子都不存在,肯定是叶子节点..{printf("%c\t",tree->data);//return 1;//还没有访问树的兄弟节点呢。。。return 1 + treeLeafCount(tree->nextSibling);}return treeLeafCount(tree->firstChild) + treeLeafCount(tree->nextSibling);}return 0;}求树的宽度，求节点的层数，，求双亲，求所有孩子节点，求所有兄弟节点其实都是层序遍历，根二叉树的不同点，上面已经说过。//求树的宽度（每一层节点数比较之后的最大值)//层序法int treeWidth(Tree tree){int maxWidth = 0;//层的最大节点数if (tree != NULL){maxWidth = 0;//第一层只有根节点..int curWidth = 1;//当前层的节点数int nextWidth = 0;//下一层的节点数..LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){for (; curWidth > 0; curWidth–){Tree father;dequeue(&queue,&father);Tree child = father->firstChild;//等于第一个孩子////将所有孩子节点入队(相当于二叉树的将左右子树入队）while (child != NULL){enqueue(&queue,child);child = child->nextSibling;nextWidth++;//计算出每一层的宽度}}curWidth = nextWidth;maxWidth = maxWidth < nextWidth ? nextWidth : maxWidth;nextWidth = 0;}queueDestory(&queue);}return maxWidth;}//求节点的层数//跟求树的宽度基本上一致int treeLevel(Tree tree,TDataType data){int level = 0;if (tree != NULL){int curWidth =1;int nextWidth = 0;LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){//每循环一次加一层level++;for (; curWidth > 0; curWidth–){Tree father;dequeue(&queue,&father);if (father->data == data){queueDestory(&queue);return level;}Tree child = father->firstChild;//等于第一个孩子////将所有孩子节点入队(相当于二叉树的将左右子树入队）while (child != NULL){enqueue(&queue,child);child = child->nextSibling;nextWidth++;//计算出每一层的宽度}}curWidth = nextWidth;nextWidth = 0;}queueDestory(&queue);}return level;}//打印父节点的值//跟二叉树不一致，有误区（不能用 tree->firstChild->data == childData 作为判断条件）//思路：层序遍历.Tree treeGetParent(Tree tree,TDataType childData){if (tree != NULL){LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){Tree father;dequeue(&queue,&father);Tree child = father->firstChild;//等于第一个孩子////将所有孩子节点入队(相当于二叉树的将左右子树入队）while (child != NULL){if (child->data == childData){queueDestory(&queue);return father;}enqueue(&queue,child);child = child->nextSibling;}}queueDestory(&queue);}return NULL;}//打印所有的孩子节点.void treeGetAllChild(Tree fatherTree){if (fatherTree != NULL){printf("%c节点的孩子有：",fatherTree->data);Tree child = fatherTree->firstChild;for (; child != NULL; child = child->nextSibling){printf("%c\t",child->data);}printf("\n");}}//打印出所有的兄弟节点.void treeGetAllBrother(Tree tree,TDataType data){Tree fatherTree = treeGetParent(tree,data);//找到父节点printf("%c节点的兄弟有：",data);if (fatherTree != NULL){Tree child = fatherTree->firstChild;for (; child != NULL; child = child->nextSibling){if (child->data != data){printf("%c\t",child->data);}}printf("\n");}}在求节点的祖先和最近祖先问题上，原本准备操作一把，可是上网百度的时候看到一篇《淘宝面试题，在一亿个节点的树中，查找两个节点的最近祖先》的面试题，网上有人给出了答案，在树的二叉链表和三叉链表数据结构中的算法完全不同。可知三叉链表多了一个父亲节点带来很大的方便和效率。

看来相同问题，不同数据结构，算法步骤不同，算法的效率和存储空间也不同。选择合适的数据结构很重要。

所以就不准备写这两个函数的具体实现了。

人，都有不能称心如意的时候，都有愿望落空的窘迫，

相关文章：

你感兴趣的文章：

标签云：