二叉树叶子节点的个数 二叉树深度的求解"/>
C/C++: 二叉树叶子节点的个数 二叉树深度的求解
其实这个比较简单,对于求深度的时候:用一个开关flag来标记是否要深度+1;
对于求叶子结点的个数的时候:用num1和num2来标记,如果有左子结点,那么在每个循环中num1置1;同理,若有右子结点,在每个循环中num2置1;综上,每个循环中只要num1和num2 都是0的时候,说明没有子结点,则可以判断是叶子结点,最终答案ans++即可
/**
*
* Althor: Hacker Hao
* Create: 2023.11.1
*
*/
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define MAXSIZE 200
typedef struct BiTNode
{ElemType data;struct BiTNode* lchild, * rchild;
}BTNode;BTNode* Create(int val)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));node->data = val;node->rchild = NULL;node->lchild = NULL;return node;
}void PreOrder(BTNode* root)
{int cnt = 0, ans = 0;int flag = 0;BTNode* stack[MAXSIZE], * p;int top = 0;if (!root){cout << "ERROR" << endl;exit(0);}stack[top] = root;while (top != -1){int num1 = 0, num2 = 0;p = stack[top];top--;cout << p->data << " ";if (p->rchild){stack[++top] = p->rchild;cnt++;flag = 1;num1 = 1;}if (p->lchild){stack[++top] = p->lchild;num2 = 1;if (flag == 0){cnt++;}}if (num1 == 0 && num2 == 0)ans++;}cout << endl;cout << "深度为:" << cnt << endl;cout << "叶子节点为:" << ans << endl;
}int main()
{cin.tie(0), cout.tie(0);BTNode* A = Create(1);BTNode* B = Create(2);BTNode* C = Create(3);BTNode* D = Create(4);BTNode* E = Create(5);BTNode* F = Create(6);BTNode* G = Create(7);BTNode* H = Create(8);A->lchild = B;A->rchild = C;B->lchild = D;B->rchild = E;E->lchild = G;E->rchild = H;C->rchild = F;cout << "前序遍历结果是:";PreOrder(A);cout << endl;return 0;
}
更多推荐
C/C++: 二叉树叶子节点的个数 二叉树深度的求解
发布评论