首页 > 代码库 > 查找二叉树中符合特定条件的值
查找二叉树中符合特定条件的值
总结了一下基本用到的公式。
下面用数组存了下,循环求解了
/* 满二叉树:一棵深度为h,且有2的(h)次方-1个节点的二叉树 特点:每一层上的结点数都是最大结点数 它的叶子数是: 2^(h-1) 第k层的结点数是: 2^(h-1) 总结点数是: 2^h-1 (2的k次方减一) 总节点数一定是奇数。所以 2^h-1=127,得出h=7.叶子数为:2^(h-1)=2^(7-1)=64 -------------------------------------------------------------------------- 用数组存,第i层的范围为2^(i-1)-1~~~~2^i-2 2^i=2<<(i-1) 2^i=1<<i; 查找特定节点: 1.节点的深入最小->递归深度,循环数组最小 2.节点为孩子节点->左右子树而空 3.节点位于最右侧 ->每层最右侧 1 2 3 4 N 6 7 89 NN 1213 NN */ #include<iostream> const int NIL=1<<10; int main(){ int A[]={1,2,3,4,NIL,6,7,8,9,NIL,NIL,12,13,NIL,NIL}; int n=(sizeof(A)/sizeof(int)+1); int cnt=0; while(n!=1 && (n=n>>1)){//求解层数 cnt++; } n=cnt; int l,r; for(int i=1;i<n;i++){ //0~n-1 l=(2<<(i-1))-3,r=(2<<(i-1))-2; //每层边界 //printf("%d %d\n",l,r); while(l>=0&&l<r){ //从右向左查找 int lc=r*2+1,rc=r*2+2; if(A[lc]==NIL && A[rc]==NIL){ printf("%d\n",A[r]); return 0; } r--; } } return 0; }
查找二叉树中符合特定条件的值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。