二叉树用二叉链存储,链接时用叶子结点的rchild 域存放指针。请设计一个算法完成①对一棵二叉树加线索(中序);②把二叉树的叶子结点按从左到右的顺序连成一个单链表。③统计二叉树中0到2度结点个数。
回答:相对来说,我感觉这个线索化是比较难的一个,其余两个则没那么困难,代码如下:
# include <stdio.h>
# include <stdlib.h>
typedef int Type;
int countOfZero = 0;
int countOfOne = 0;
int countOfTwo = 0;
struct Node
{
Type value;
Node* left;
Node* right;
};
void init(Node* root)
{
root->value = 10;
root->left = NULL;
root->right = NULL;
Node* node1 = (Node*)malloc(sizeof(Node));
Node* node2 = (Node*)malloc(sizeof(Node));
Node* node3 = (Node*)malloc(sizeof(Node));
Node* node4 = (Node*)malloc(sizeof(Node));
node1->left = NULL;
node1->right = NULL;
node2->left = NULL;
node2->right = NULL;
node3->left = NULL;
node3->right = NULL;
node4->left = NULL;
node4->right = NULL;
node1->value = 2;
node2->value = 4;
node3->value = 6;
node4->value = 8;
root->left = node1;
root->right = node2;
node1->right = node3;
node2->left = node4;
}
void inorder(Node* root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->value);
inorder(root->right);
}
void addNode(Node* head, Node* node)
{
Node* temp = head;
while (temp->right)
{
temp = temp->right;
}
temp->right = node;
}
void getLeafToList(Node* root, Node* head)
{
if (root == NULL)
{
return;
}
getLeafToList(root->left, head);
if (root->left == NULL && root->right == NULL)
{
addNode(head, root);
}
getLeafToList(root->right, head);
}
void getCountOfNodeZero(Node* root)
{
if (root == NULL)
{
return;
}
getCountOfNodeZero(root->left);
if (root->left == NULL && root->right == NULL)
{
countOfZero++;
}
getCountOfNodeZero(root->right);
}
void getCountOfNodeOne(Node* root)
{
if (root == NULL)
{
return;
}
getCountOfNodeOne(root->left);
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
{
countOfOne++;
}
getCountOfNodeOne(root->right);
}
void getCountOfNodeTwo(Node* root)
{
if (root == NULL)
{
return;
}
getCountOfNodeTwo(root->left);
if (root->left != NULL && root->right != NULL)
{
countOfTwo++;
}
getCountOfNodeTwo(root->right);
}
int main()
{
Node* root = (Node*)malloc(sizeof(Node));
init(root);
inorder(root);
printf("\n");
// Node* head = (Node*)malloc(sizeof(Node));
// head->value = -100;
// head->left = NULL;
// head->right = NULL;
//
// getLeafToList(root, head);
// inorder(head);
// printf("\n");
getCountOfNodeZero(root);
getCountOfNodeOne(root);
getCountOfNodeTwo(root);
printf("度为0的节点个数:%d\n", countOfZero);
printf("度为1的节点个数:%d\n", countOfOne);
printf("度为2的节点个数:%d\n", countOfTwo);
}
有点晚了,线索化还没写完,可以先凑合看看,我感觉有许多问题,首先就是这个二叉树的建立,好麻烦,明天必须改进一下