遍历二叉树的具体算法实现与剖析

72 阅读 0 评论 48 点赞

我是靠谱客的博主外向龙猫，最近开发中收集的这篇文章主要介绍遍历二叉树的具体算法实现与剖析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 二叉树的建立
- 复制二叉树
- 计算二叉树的深度
- 统计二叉树中结点的个数
- 计算二叉树叶子结点数

二叉树的建立

按先序遍历序列建立二叉树的二叉链表
1.从键盘输入二叉树的结点信息，建立二叉树的存储结构。
2.在建立二叉树的过程中按照二叉树先序方式建立；
【算法步骤】
①扫描字符序列，读入字符ch
②如果ch是一个“#”字符，则表明该二叉树为空树，即 T 为NULL；否则执行以下操作：
- 申请一个结点空间 T
- 将 ch 赋给T->data
- 递归创建T的左子树
- 递归创建T的右子树
  【算法描述】

void CreateBiTree(BiTree &T)
{
	scanf(&ch); //cin >> ch;
	if(ch=='#') T=NULL; //递归结束，建空树 
	else                //递归创建二叉树
	{
		T=new BiTNode;  //生成根结点 
		//或T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data = ch;   //根结点数据域置为ch 
		CreateBiTree(T->lchild); //递归创建左子树 
		CreateBiTree(T->rchild); //递归创建右子树 
	}
 } //CreateBiTree

复制二叉树

【算法步骤】
如果是空树，递归结束，否则执行以下操作：

申请一个新结点空间，复制根结点
递归复制左子树
递归复制右子树

【算法描述】

void Copy(BiTree T,BiTree &newT)
{
 	if(T==NULL)   //如果是空树，递归结束 
 	{
 		newT=NULL;
 		return;
	}
	else
	{
		NewT=new BiTNode;
		NewT->data=T->data;  //复制根结点 
		Copy(T->lchild,NewT->lchild); //递归复制左子树 
		Copy(T->rchild,NewT->rchild); //递归复制右子树 
	}
}

计算二叉树的深度

【算法步骤】
如果是空树，递归结束，深度为0，否则执行以下操作：

递归计算左子树的深度记为m
递归计算左子树的深度记为n
如果 m 大于 n，二叉树的深度为 m+1，否则为 n+1

【算法描述】

int Depth(BiTree T)
{
	if(T==NULL) return 0;   //空树，深度为0，递归结束 
	else
	{
		m=Depth(T->lchild); //递归计算左子树的深度记为m 
		n=Depth(T->rchild); //递归计算右子树的深度记为n 
		if(m>n) return (m+1);//二叉树的深度为m与n的较大者加1 
		else return (n+1);
	}
 }

统计二叉树中结点的个数

【算法分析】
如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数+右子树的结点个数再+1。
【算法描述】

int NodeCount(BiTree T)
{
	if(T==NULL) return 0;  //空树，则结点个数为0，递归结束 
	else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
	//结点个数为左子树的结点个数+右子树的结点个数+1 
 }

计算二叉树叶子结点数

【算法分析】
如果是空树，则结点个数为0；
否则，结点个数为左子树的结点个数+右子树的结点个数。
(左子树和右子树都会空，叫做叶子结点)
【算法描述】

int LeadCount(BiTree T)
{
	if(T==NULL) return 0; //如果是空树返回0 
	if(T->lchild==NULL && T->rchild==NULL)
	  return 1;           //如果是叶子结点返回1 
	else
	  return LeadCount(T->lchild)+LeadCount(T->rchild);  
 }