二叉树用二叉链存储问题

Question

二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。请设计一个算法完成①对一棵二叉树加线索（中序）；②把二叉树的叶子结点按从左到右的顺序连成一个单链表。③统计二叉树中0到2度结点个数。

Answer 1

回答：相对来说，我感觉这个线索化是比较难的一个，其余两个则没那么困难，代码如下：

# 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);
}

有点晚了，线索化还没写完，可以先凑合看看，我感觉有许多问题，首先就是这个二叉树的建立，好麻烦，明天必须改进一下