看数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先 - fuming0210sc的专栏 - 博客频道 - CSDN.NET

看数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先 - fuming0210sc的专栏 - 博客频道 - CSDN.NET
二叉树的宽度是：每一层 节点数的最大值。
思路：根据层序遍历，求出 每一层的节点数，

//纠正 求 二叉树的 宽度问题， //二叉树的宽度 为 各层次 节点数的 最大值 //算法思路，层序 遍历, 

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);
 }
}

Read full article from 看数据结构写代码（25） 二叉链表 求 宽度，交换左右子树,判断完全二叉树,求节点祖先 - fuming0210sc的专栏 - 博客频道 - CSDN.NET