Một số thắc mắc với cây nhị phân C++

#1

Mình đang làm bài tập trên cây tìm kiếm nhị phân nhưng đang bí chức năng sau:

̶c̶̶.̶ ̶L̶̶ư̶̶u̶ ̶t̶̶o̶̶à̶̶n̶ ̶b̶̶ộ̶ ̶d̶̶ữ̶ ̶l̶̶i̶̶ệ̶̶u̶ ̶t̶̶r̶̶ê̶̶n̶ ̶c̶̶â̶̶y̶ ̶x̶̶u̶̶ố̶̶n̶̶g̶ ̶f̶̶i̶̶l̶̶e̶̶.̶
̶m̶̶.̶ ̶Đ̶̶ả̶̶o̶ ̶n̶̶h̶̶á̶̶n̶̶h̶ ̶t̶̶r̶̶á̶̶i̶ ̶v̶̶à̶ ̶n̶̶h̶̶á̶̶n̶̶h̶ ̶p̶̶h̶̶ả̶̶i̶ ̶c̶̶ủ̶̶a̶ ̶c̶̶â̶̶y̶̶.̶
̶n̶̶.̶ ̶D̶̶u̶̶y̶̶ệ̶̶t̶ ̶c̶̶â̶̶y̶ ̶t̶̶h̶̶e̶̶o̶ ̶c̶̶h̶̶i̶̶ề̶̶u̶ ̶r̶̶ộ̶̶n̶̶g̶ ̶(̶̶B̶̶F̶̶S̶)
̶o̶̶.̶ ̶D̶̶u̶̶y̶̶ệ̶̶t̶ ̶c̶̶â̶̶y̶ ̶t̶̶h̶̶e̶̶o̶ ̶c̶̶h̶̶i̶̶ề̶̶u̶ ̶s̶̶â̶̶u̶ ̶(̶̶D̶̶F̶̶S̶
̶p̶̶.̶ ̶K̶̶i̶̶ể̶̶m̶ ̶t̶̶r̶̶a̶ ̶x̶̶e̶̶m̶ ̶c̶̶â̶̶y̶ ̶T̶ ̶c̶̶ó̶ ̶p̶̶h̶̶ả̶̶i̶ ̶l̶̶à̶ ̶c̶̶â̶̶y̶ ̶c̶̶â̶̶n̶ ̶b̶̶ằ̶̶n̶̶g̶ ̶h̶̶o̶̶à̶̶n̶ ̶t̶̶o̶̶à̶̶n̶ ̶h̶̶a̶̶y̶ ̶k̶̶h̶̶ô̶̶n̶̶g̶̶?̶
̶r̶̶.̶ ̶T̶̶ì̶̶̶m̶ ̶m̶̶ứ̶̶c̶ ̶c̶̶ủ̶̶a̶ ̶m̶̶ộ̶̶t̶ ̶n̶̶ú̶̶t̶ ̶t̶̶h̶̶e̶̶o̶ ̶g̶̶i̶̶á̶ ̶t̶̶r̶̶ị̶ ̶n̶̶h̶̶ậ̶̶p̶̶.̶
̶s̶̶.̶ ̶K̶̶i̶̶ể̶̶m̶ ̶t̶̶r̶̶a̶ ̶m̶̶ộ̶̶t̶ ̶c̶̶â̶̶y̶ ̶T̶ ̶c̶̶h̶̶o̶ ̶t̶̶r̶̶ư̶̶ớ̶̶c̶ ̶c̶̶ó̶ ̶p̶̶h̶̶ả̶̶i̶ ̶l̶̶à̶ ̶c̶̶â̶̶y̶ ̶B̶̶S̶̶T̶ ̶h̶̶a̶̶y̶ ̶k̶̶h̶̶ô̶̶n̶̶g̶̶?̶

Sau 1 buổi tối chinh chiến tới 3h38 phút sáng ,đã nghiên cứu và làm xong bài tập,cảm ơn tất cả mọi người,giờ phải đi ngủ đã :stuck_out_tongue:

Link bài tập full

Cảm ơn mọi người rất nhiều

#2

Bài này bị flag là đúng rồi. Với câu hỏi này thì mong muốn của bạn là gì?

2 Likes
#3

Câu O với E hình như là như nhau @_@
DFS bản chất là có 3 hướng duyệt như vậy.

Còn khi duyệt được rồi thì ở câu C có thể vừa duyệt và vừa append vào file và tương tự cho câu R là vừa duyệt vừa đếm và dùng BFS sẽ tiện.

3 Likes
#4

em cũng đã tìm hiểu nhưng hình như có >3 kiểu duyệt ở case e thì phải ạ

#5

chết cha edit lại xóa luôn cái dòng muốn hỏi

Mình đã edit lại lần 3,cảm ơn bạn đã nhắc nhở

#6

Mấy cái này hiểu đc recursion thì dễ lắm, thuật toán nhé
m/

function reverse_tree(tree) : 
    TREE newtree
    newtree.left = reverse_tree(tree.right)
    newtree.right = reverse_tree(tree.left)
    return newtree
1 Like
#7

Câu m) thì làm kiểu gì :slight_smile: tại vì bên trái < bên phải mà. Hay là cân bằng AVL?
Câu r) giống q)
Câu s) thì với thứ tự <= cho trước, nếu bên phải <= bên trái thì knock out. Có liên quan đến min max.

1 Like
#8

bạn có thể giải nghĩa nó không,nếu mình không nhầm là:

  • tạo ra 1 cây mới,
  • Để left của cây mới bằng right của cây cũ
  • Để right của cây mới bằng left của cây cũ
  • return tạo ra 1 cây mới

Mình thắc mắc là reverse_tree là hàm có sẵn hay mình định nghĩa z

#9

Hì Hì phiền bạn nói rõ hơn được k

Hỏi về cách viết bài đúng chuẩn
#10

recursion hay còn gọi là đệ quy.
reverse_tree là tên mình đặt; 1 dạng recursion

1 Like
#11

DFS thì viết đệ quy đc chứ BFS làm sao đc ông ?

2 Likes
#12

Câu s) bạn tìm hiểu định nghĩa cây nhị phân tìm kiếm nó sẽ ntn.

Cây nhị phân tìm kiếm là cây nhị phân có gắn khóa sao cho

  • các khóa ở cây con bên trái đều nhỏ hơn gốc.
  • các khóa ở cây con bên phải đều lớn hơn gốc.

dưới một thứ tự toàn phần <. Vì vậy phải có min max, nếu chỉ xét cục bộ là sai.

^ oops… :smiley:

1 Like
#13

Nếu vậy mình sẽ tìm MAX rồi gán nó = gốc
-tiếp đó so sánh các phần tử bên trái và bên phải
-nếu các phần tử bên trái > MAX và bên phải <MAX thì return false,ngược lại thì true :slight_smile:

Chả biết đúng không mong bạn đừng chê cười :))

#14

Sau 1 buổi tối cày quốc tới 3h sáng , thanh niên vẫn tắc tịt 2 yêu cầu
n. Duyệt cây theo chiều rộng (BFS)
-Chưa hiểu giải thuật
o. Duyệt cây theo chiều sâu (DFS)
-Ngoài đầu (NLR), giữa (LNR), cuối (LRN),còn trường hợp gì nữa nhỉ ?

#15

n. Sử dụng cấu trúc queue (FIFO) đó :slight_smile: cứ đẩy mỗi node ra thì kiểm tra trước rồi đưa cả hai node con vào queue.

1 Like
#16

Đây là code nhà người ta:

public static BinaryTreeNode Postfix2ExpressionTree(string postfixExpression)
{
    Stack stack = new Stack();
 
    IEnumerable enumer = postfixExpression.Split(' ');
 
    foreach (string s in enumer)
    {
        BinaryTreeNode node = new BinaryTreeNode(s);
        if (IsOperand(s))
            stack.Push(node);
        else if (IsOperator(s))
        {
            node.RightChild = stack.Pop();
            node.LeftChild= stack.Pop();
            stack.Push(node);
        }
    }
    return stack.Pop();
}

Cho mình hỏi câu

    IEnumerable enumer = postfixExpression.Split(' ');

"Người ta " cũng đã chỉ thuật toán và cho code tham khảo nhưng mà chưa hiểu code cái dòng trên có nghĩa là sao,mọi người chỉ mình với.

#17

Tức là tách ra theo khoảng trắng. Vấn đề là phải chuẩn hóa xong thì mới được =)) thôi thà đọc trực tiếp cho rồi.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?