数据结构—基础知识(12):二叉树算法补充
-
复制二叉树
【算法步骤】
如果是空树,递归结束,否则进行以下操作:
- 申请一个新结点空间,复制根结点;
- 递归复制左子树;
- 递归复制右子树。
void Copy(BiTree T,BiTree &NewT) {//复制一棵和T完全相同的二叉树 if(T==NULL)//如果是空树,递归结束 { NewT=NULL; return; } else { NewT=new BiTNode; NewT->data=T->data;//复制根结点 Copy(T->lchild,NewT->lchild);//递归复制左子树 Copy(T->rchild,NewT->rchild);//递归复制右子树 }//else }
-
计算二叉树的深度
【算法步骤】文章来源:https://www.toymoban.com/news/detail-824343.html
如果是空树,递归结束,深度为0,否则进行以下操作:文章来源地址https://www.toymoban.com/news/detail-824343.html
- 递归计算左子树的深度记为m;
- 递归计算右子树的深度记为n;
- 如果m大于n,二叉树的深度为m+1,否则为n+1
int Depth(BiTree T) {//计算二叉树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) } }
-
统计二叉树中结点的个数
int NodeCount(BiTree T) {//统计二叉树T中结点的个数 if(T==NULL) return 0;//如果是空树,则结点个数为0,递归结束 else return NodeCount(T->lchild)+NodeCount(T->rchild)+1 //否则结点个数为左子树的结点个数+右子树的结点个数+1 }
-
统计二叉树叶子结点个数
int LeafNode(BiTree T) {//统计二叉树T中叶子结点的个数 if(T==NULL) return 0;//空树,返回0 else if(T->lchild==NULL&&T->rchild==NULL) return 1;//叶子结点,返回1 else//递归 return LeafNode(T->lchild)+LeafNode(T->rchild) }
到了这里,关于数据结构—基础知识(12):二叉树算法补充的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!