看数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完

二叉树的宽度是：每一层 节点数的最大值。

思路：根据层序遍历，求出 每一层的节点数，

//纠正 求 二叉树的 宽度问题，//二叉树的宽度 为 各层次 节点数的 最大值//算法思路，层序 遍历,int treeWidth(Tree tree){if (tree != NULL){int curWidth = 1;//当前层的 节点数int nextWidth = 0;//下一层的节点数int maxWidth = 1;//最大节点数LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){while (curWidth != 0){curWidth –;dequeue(&queue,&tree);if (tree->leftChild != NULL){enqueue(&queue,tree->leftChild);nextWidth++;}if (tree->rightChild != NULL){enqueue(&queue,tree->rightChild);nextWidth++;}}if(nextWidth > maxWidth){maxWidth = nextWidth;}curWidth = nextWidth;nextWidth = 0;}return maxWidth;}return 0;//空表宽度为0}

查找任意节点的祖先：

祖先指的是：从根 到 节点 所经过的 所有节点。

//查找祖先bool treeGetAllParent(Tree tree,ElementType data){if (tree != NULL){if (tree->data == data){return true;}if (treeGetAllParent(tree->leftChild,data) || treeGetAllParent(tree->rightChild,data)){printf("%d\t",tree->data);return true;}}return false;}

判断是否是完全二叉树：

思路：层序遍历，在遍历中，遇到空节点 以后，如果 再遇到 一个 非空节点，就不是完全二叉树。

//判断是不是完全二叉树//利用层序 遍历//在层序遍历时，出现了 空子树以后，又出现了非空子树，不是完全二叉树bool treeIsFull(Tree tree){bool isFindNull = false;//是不是发现空子树了LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){dequeue(&queue,&tree);if (tree == NULL){isFindNull = true;}else {if(isFindNull)//在 出现了空子树后，出现了 非空节点{return false;}else{//在还没发现空时，所有节点 都得 入队//在发现了空了，非空节点不需要入队//(算法优化）以前 无判断//enqueue(&queue,tree->leftChild);if (tree->leftChild != NULL || isFindNull == false){enqueue(&queue,tree->leftChild);}if (tree->rightChild != NULL || isFindNull == false){enqueue(&queue,tree->rightChild);}}}}//销毁队列queueDestory(&queue);return true;//空树 是完全二叉树}交互左右子树：

//交换左右子树void treeExchangeChild(Tree t){if (t != NULL){if (t->leftChild != NULL || t->rightChild != NULL){Tree temp = t->leftChild;t->leftChild = t->rightChild;t->rightChild = temp;}treeExchangeChild(t->leftChild);treeExchangeChild(t->rightChild);}}完整代码：

// binaryTree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <cstdlib>#include "stack.h"#include "queue.h"#include <math.h>typedef int ElementType;typedef struct TreeNode{ElementType data;TreeNode * leftChild;TreeNode * rightChild;} * Tree;void treeInit(Tree * tree){*tree = NULL;}//其实 自己 不懂 这个 函数 初始化…E_State treeCreate(Tree *tree){ElementType data;scanf("%d",&data);if (data == 0){*tree = NULL;}else{*tree = (Tree)malloc(sizeof(TreeNode));(*tree)->data = data;treeCreate(&(*tree)->leftChild);treeCreate(&(*tree)->rightChild);}return E_State_Ok;}//后序遍历void treeClear(Tree * tree){if (tree != NULL){if ((*tree)->leftChild != NULL){treeClear(&(*tree)->leftChild);}else if((*tree)->rightChild != NULL){treeClear(&(*tree)->rightChild);}free(*tree);*tree = NULL;}}void treeDestory(Tree * tree){treeClear(tree);}//纠正 求 二叉树的 宽度问题，//二叉树的宽度 为 各层次 节点数的 最大值//算法思路，层序 遍历,int treeWidth(Tree tree){if (tree != NULL){int curWidth = 1;//当前层的 节点数int nextWidth = 0;//下一层的节点数int maxWidth = 1;//最大节点数LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){while (curWidth != 0){curWidth –;dequeue(&queue,&tree);if (tree->leftChild != NULL){enqueue(&queue,tree->leftChild);nextWidth++;}if (tree->rightChild != NULL){enqueue(&queue,tree->rightChild);nextWidth++;}}if(nextWidth > maxWidth){maxWidth = nextWidth;}curWidth = nextWidth;nextWidth = 0;}return maxWidth;}return 0;//空表宽度为0}//查找祖先bool treeGetAllParent(Tree tree,ElementType data){if (tree != NULL){if (tree->data == data){return true;}if (treeGetAllParent(tree->leftChild,data) || treeGetAllParent(tree->rightChild,data)){printf("%d\t",tree->data);return true;}}return false;}//判断是不是完全二叉树//利用层序 遍历//在层序遍历时，出现了 空子树以后，又出现了非空子树，不是完全二叉树bool treeIsFull(Tree tree){bool isFindNull = false;//是不是发现空子树了LinkQueue queue;queueInit(&queue);enqueue(&queue,tree);while (!queueEmpty(queue)){dequeue(&queue,&tree);if (tree == NULL){isFindNull = true;}else {if(isFindNull)//在 出现了空子树后，，出现了 非空节点{return false;}else{//在还没发现空时，所有节点 都得 入队//在发现了空了，非空节点不需要入队//(算法优化）以前 无判断//enqueue(&queue,tree->leftChild);if (tree->leftChild != NULL || isFindNull == false){enqueue(&queue,tree->leftChild);}if (tree->rightChild != NULL || isFindNull == false){enqueue(&queue,tree->rightChild);}}}}//销毁队列queueDestory(&queue);return true;//空树 是完全二叉树}//交换左右子树void treeExchangeChild(Tree t){if (t != NULL){if (t->leftChild != NULL || t->rightChild != NULL){Tree temp = t->leftChild;t->leftChild = t->rightChild;t->rightChild = temp;}treeExchangeChild(t->leftChild);treeExchangeChild(t->rightChild);}}/*//求二叉树节点的最大路径数.//一棵二叉树中相距最远的两个节点之间的距离。//"距离"为两节点之间边的个数int treeMaxPath(Tree t){}//寻找节点child1 和 child2 的最近 共同祖先//后序遍历 子树Tree treeFindCommonAncestor(Tree tree,Tree child1,Tree child2){}*///递归算法 先序void preOrderTraverse(Tree tree){if (tree != NULL){printf("%d\t",tree->data);preOrderTraverse(tree->leftChild);preOrderTraverse(tree->rightChild);}}int _tmain(int argc, _TCHAR* argv[]){Tree tree;printf("—————创建树（先序,0代表子树为空）—————–\n");treeCreate(&tree);printf("————先序递归遍历—————-\n");preOrderTraverse(tree);int width = treeWidth(tree);char * isFull = treeIsFull(tree) ? "是" : "不是";printf("\n树的宽度是：%d,树是否是完全二叉树:%s\n",width,isFull);printf("———–打印5的所有祖先————-\n");treeGetAllParent(tree,5);//打印5的所有祖先。printf("\n");printf("———–交互左右子树后————-\n");treeExchangeChild(tree);preOrderTraverse(tree);printf("\n———–创建完全二叉树————-\n");Tree fullTree;treeCreate(&fullTree);isFull = treeIsFull(fullTree) ? "是" : "不是";printf("树是否是完全二叉树:%s\n",isFull);//及时释放内存是个好习惯..treeDestory(&fullTree);treeDestory(&tree);return 0;}运行截图：

任何业绩的质变都来自于量变的积累。