基于二叉树的算法
2022/2/4 20:12:46
本文主要是介绍基于二叉树的算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.统计二叉树中度为1的节点个数
int NodeCount(BiTree bt){ if(bt == null) return 0; if(bt->lchild == null && bt->rchild != null || bt->lchild != null && bt->rchild == null) return 1+NodeCount(bt->lchild) + NodeCount(bt->rchild); return NodeCount(bt->lchild) + NodeCount(bt->rchild); }
2.统计二叉树中度为2的节点个数
int NodeCount(BiTree bt){ if(bt == null) return 0; if(bt->lchild != null && bt->rchild != null) return 1+NodeCount(bt->lchild) + NodeCount(bt->rchild); }
3.统计二叉树中度为0的节点个数(叶节点)
int NodeCount(BiTree bt){ if(bt == null) return 0; if(bt->lchild == null && bt->rchild == null) return 1; else return NodeCount(bt->lchild) + NodeCount(bt->rchild); }
4.计算二叉树高度
int height(BiTree bt){ if(bt == null) return 0; int LHeight = height(bt->left); int RHeight = height(bt->right); return (LHeight > RHeight ? LHeight : RHeight) + 1; }
5.计算二叉树最大高度(基于先序遍历)
int count[MaxSize]; int max = -1; void width(BiTree bt, int k){ if(bt == null) return; count[k]++; //该层节点数+1 if(max<count[k]) max = count[k]; width(bt->lchikd, k+1); width(bt->rchild, k+1); }
6.删除二叉树中所有叶节点
void Del_0(BiTree bt){ BiTree *p = bt; if((p->lchild == null && p->rchild == null) || p == null) free(p); return; if(p->lchild->lchild == null && p->lchild->rchild == null) free(p->lchild); //说明是叶节点,删掉 p->lchild = null; else(p->rchild->lchild == null && p->rchild->rchild == null) free(p->rchild); p-rchild = null; Del_0(p->lchild); Del_0(p->rchild); }
7.计算二叉树指定节点所在层次
int level(BiTree bt, BiTree *p){ int d1,d2; if(bt == null) return 0; if(bt == p) return 1; d1 = level(bt->lchild, p); d2 = level(bt->rchild, p); if(d1 || d2) return 1+(d1>d2 ? d1:d2); retrun 0; }
8.交换二叉树左右子树
void swap(BiTree bt){ if(bt){ swap(bt->lchild); swap(bt->rchild); BiTree *temp = bt->lchild; bt->lchild = bt->rchild; bt->rchild = temp; } }
9.后序遍历非递归算法
void PostOrder(BiTree T){ InitStack(S); BiTree *p = T; BiTree *r = null; while(p || !IsEmpty(S)){ if(p){ Push(S,p); p = p->lchild; }else{ GetTop(S,p); if(p->rchild && p->rchild != r){ //判断是否有右子树 p = p->rchild; }else{ Pop(S,p); visit(p->data); r = p; p = null; } } } }
这篇关于基于二叉树的算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南