有了昨天的铺垫,今天就很简单了。先把昨天二叉树的代码复制一下,今天还要用。
代码:
typedef int datatype;
typedef struct BinaryTree
{
datatype _data;
struct BinaryTree* _left;
struct BinaryTree* _right;
}BT;
BT* CreatNode(datatype x)
{
BT* newnode = (BT*)malloc(sizeof(BT));
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->_left = NULL;
newnode->_right = NULL;
newnode->_data = x;
return newnode;
}
BT* CreatBinaryTree()
{
BT* node1 = CreatNode(1);
BT* node2 = CreatNode(2);
BT* node3 = CreatNode(3);
BT* node4 = CreatNode(4);
BT* node5 = CreatNode(5);
BT* node6 = CreatNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}
二叉树节点个数
代码如下:
int BinaryTreeSize(BT* root)
{
if (root == NULL)
{
return 0;
}
return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
我们看下运行结果:
这个是递归的思想,不懂的小伙伴可以画一下递归图就懂了。不过,相信各位小伙伴昨天应该就弄懂递归的思想了,今天这个游刃有余了。
二叉树叶子节点个数
代码如下:
int BinaryTreeLeafSize(BT* root)
{
if (root == NULL)
{
return 0;
}
if (root->_left == NULL && root->_right == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
我们看下运行结果:
这个也是递归思想,看不懂的小伙伴们,画画递归图就看懂了。
二叉树第k层节点个数
代码如下:
int BinaryTreeLevelKSize(BT* root, int k)
{
assert(k>0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
运行一下,当k=3、k=2和k=4时:
这道题可能会有点想不出来,这里给一下解题思路。
1 当root==null时,无论k=多少,结果都是0.
2 root != null时,且k=1时,输出1.
3 k>0时,就是输出左子树k-1和右子树k-1的结果(这句就是递归的思想)。
4 可以画画图。
这部分递归的题,没有思路很正常,多做几道题就可以了。