Triển khai cấu trúc cây bằng cách sử dụng danh sách liên kết (char)

[Hung_Dang1 (Hưng Đặng)]

#Thảo luận để giải quyết vấn đề.

đề bài: sử dụng danh sách liên kết với dữ liệu thuộc kiểu dữ liệu là char
yêu cầu :
Trong dòng đầu tiên, số nút trong cây nhị phân N (1≤N≤26) được đưa ra. Mỗi nút, nút con bên trái và nút con bên phải được cho trên N dòng kể từ dòng thứ hai. Tên nút được viết hoa chữ cái theo thứ tự từ A và A luôn là nút gốc. Nếu không có nút con nào thì Được thể hiện là .
vd:
input:

7
A B C
B D . 
C E F
E . .
F . G 
D . . 
G . .

output: DBAECFG

struct node{
    char value;
    struct node*  left;
    struct node*  left;
}

nhập dữ liệu trong main là:

scanf("%d", &n); 
getchar();

for(inti=0;i<n;i++) {

    char parent, leftChild, rightChild;
    scanf("%c %c %c", &parent, &leftChild, &rightChild);
    getchar();
}

như trên em đã nêu rõ. đây là bài thảo luận nếu có vi phạm em xin phép xoá bài nhưng trước đó e có 1 thắc mắc về việc là làm thế nào mà ta biết được parent ở dòng 3 là B thì là nút bên trái để thêm vào vậy.

---

em có 2 phương án

phương án 1 là : em kiểm tra xem char x thuộc bên trái hay bên phải gốc.
rồi dịch chuyển gốc sang trái hay phải.

int isRight(node* root, char x){
    if (root!= NULL) {
        isRight(root->right, x);
        if ((int)root->right == 'x') {
            return 1;
        }
    }
    return 0;
}
node* Insert(node* root, char x){
    if (root == NULL) {
        node* p = (node*)malloc(sizeof(node));
        p->value = x;
        p->left = NULL;
        p->right = NULL;
        return p;
    }
    if (isRight(root, x)) {
        Insert(root->right, x);
    }else if (isLeft(root, x)){
        Insert(root->left, x);
    }
    return root;
}

---

phương án 2 là : ngay trên main em phân loại r thêm vào luôn

 for (int i = 0; i < n; i++) {
        char parent, leftchild, rightchild;
        scanf("%c %c %c", &parent, &leftchild, &rightchild);
        getchar();
        
        serach(root, parent);
        serach(root, leftchild);
        serach(root, rightchild);
    }

hàm thêm vào:

treeNode* serach(treeNode* root, char x){
    if (root == NULL) {
        treeNode* p = (treeNode*)malloc(sizeof(treeNode));
        p->value = x;
        p->Left = NULL;
        p->Right = NULL;
        return p;
    }
    if ('x' < (int)root->value) {
        serach(root->Left, x);
    }else if ('x' > (int)root->Right){
        serach(root->Right, x);
    }
    return root;
}

cảm ơn mọi người ạ

[SITUVN.gcd]

• Đây là cây nhị phân chứ!
• Bạn chưa đưa ra yêu cầu xuất giá trị của bài toán. Nếu không sai thì xuất theo thứ tự LNR (in-order).

Tree traversal