采用二叉链表结构存储一颗二叉树，编写算法统计该二叉树的高度、二叉树的节点个树、叶子结点的个数和度为1的节点个数

Question

采用二叉链表结构存储一颗二叉树，编写算法统计该二叉树的高度、二叉树的节点个树、叶子结点的个数和度为1的节点个数

Answer 1

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7559801
• 这篇博客你也可以参考下：习题：设二叉树按照二叉链表存储，编写算法判别一棵二叉树是否是一棵正则二叉树，正则二叉树是指在二叉树中不存在子树个数为1的结点。
• 这篇博客也不错, 你可以看下习题：设二叉树按照二叉链表存储，编写算法判别一棵二叉树是否是一棵正则二叉树，正则二叉树是指在二叉树中不存在子树个数为1的结点。
• 除此之外, 这篇博客: 例题：设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法中的 例题：设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 如有谬误或者不足还请批评指正！

  （1）统计二叉树中度为0、1、2的结点个数

  int num_0 = 0, num_1 = 0, num_2 = 0;
  
  void CountNode(BiTree T)
  {
  	if (T == NULL)
  		return;
  	if ((T->lchild && !T->rchild) || (!T->lchild && T->rchild))
  		num_1++;
  	else if (!T->lchild && !T->rchild)
  		num_0++;
  	else
  		num_2++;
  	CountNode(T->lchild);
  	CountNode(T->rchild);
  }
  

  （2）统计二叉树的高度

  int CountHeight(BiTree T)
  {
  	if (T == NULL)
  		return 0;
  	if (T->lchild == NULL && T->rchild == NULL)
  		return 1;
  	return Max(CountHeight(T->lchild), CountHeight(T->rchild)) + 1;
  }
  

  （3）统计二叉树的宽度

  int MaxWidth = -1;
  int Level[MaxSize];
  
  void CountWidth(BiTree T, int l)
  {
  	if(T == NULL)
  		return;
  	Level[l]++;
  	if(MaxWidth < Level[l])
  		MaxWidth = Level[l];
  	CountWidth(T->lchild, l+1);
  	CountWidth(T->rchild, l+1);
  }
  

  （4）从二叉树中删去所有叶结点

  void DeleteLeafNode(BiTree T)
  {
  	if(T == NULL)
  		return;
  	if(T->lchild != NULL)
  	{
  		BiTNode *p = T->lchild;
  		if(p->lchild == NULL && p->rchild == NULL)
  		{
  			free(p);
  			T->lchild = NULL;
  		}
  	}
  	if(T->rchild != NULL)
  	{
  		BiTNode *q = T->rchild;
  		if(q->lchild == NULL && q->rchild == NULL)
  		{
  			free(q);
  			T->rchild = NULL;
  		}
  	}
  	DeleteLeafNode(T->lchild);
  	DeleteLeafNode(T->rchild);
  }
  

  （5）计算指定结点*p所在的层次

  int FindNodeLevel(BiTree T, BiTNode *p, int level)
  {
  	if (T == NULL)
  		return 0;
  	if (T->data == p->data)
  		return level;
  	FindNodeLevel(T->lchild, p, level + 1);
  	FindNodeLevel(T->rchild, p, level + 1);
  	return -1;
  }
  

  （6）计算二叉树各结点中的最大元素的值

  int Max = -32767;
  
  void FindMaxNode(BSTree T)
  {
  	if (T != NULL)
  	{
  		if (Max < T->data)
  			Max = T->data;
  		FindMaxNode(T->lchild);
  		FindMaxNode(T->rchild);
  	}
  }
  

  （7）交换二叉树中每个结点的两个子女

  void ExchangeNode(BiTree T)
  {
  	if (T == NULL)
  		return;
  	BiTNode *p = T->lchild;
  	T->lchild = T->rchild;
  	T->rchild = p;
  	ExchangeNode(T->lchild);
  	ExchangeNode(T->rchild);
  }
  

  （8）以先序次序输出一颗二叉树中所有结点的数据值及结点所在的层次

  void PreOrder(BiTree T, int level)
  {
  	if (T == NULL)
  		return;
  	printf("T->data : %d ", T->data);
  	printf("level : %d ", level);
  	PreOrder(T->lchild, level + 1);
  	PreOrder(T->rchild, level + 1);
  }