Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Cách duyệt cây nhị phân như thế nào?

  1. #1
    Ngày gia nhập
    09 2008
    Nơi ở
    TP HCM
    Bài viết
    0

    Angry Cách duyệt cây nhị phân như thế nào?

    Mình đả làm cách duyệt cây theo kiểu đệ quy.Phần dưới đây là 3 hàm dùng để duyệt cây theo 3 kiểu khác nhau.Nhưng theo mình nghĩ thì cách này khá tốn thời gian và nếu sử dụng kiểu duyệt cây như trong stack thì sẽ nhanh hơn nhưng mình chưa nghĩ ra được phải làm như thế nào.Mong các bạn có thể giúp dùm mình.Thanks nhiều
    C++ Code:
    1. void NLR_DQ(Node * p)
    2. {
    3.     if(p!=NULL)
    4.     {
    5.         cout<<p->info<<endl;
    6.         NLR_DQ(p->left);
    7.         NLR_DQ(p->right);
    8.     }
    9. }
    10. void LNR_DQ(Node * p)
    11. {
    12.     if(p!=NULL)
    13.     {
    14.         LNR_DQ(p->left);
    15.         cout<<p->info<<endl;
    16.         LNR_DQ(p->right);
    17.     }
    18. }
    19. void LRN_DQ(Node * p)
    20. {
    21.     if(p!=NULL)
    22.     {
    23.         LRN_DQ(p->left);
    24.         LRN_DQ(p->right);
    25.         cout<<p->info<<endl;
    26.     }
    27. }

  2. #2
    Ngày gia nhập
    11 2008
    Nơi ở
    Neverland
    Bài viết
    48

    Dùng Stack là cách khử đệu quy của các phép duyệt cây . Lợi về tốc độ nhưng tốn về bộ nhớ (dùng Stack để lưu trữ địa chỉ các nút trong cây) . Mình nêu ra thuật toán duyệt cây theo thứ tự trước bằng ngôn ngữ tự nhiên . Bạn có thể dựa vào đó viết Code , các phép duyệt cây theo thứ tự giữa và sau tương tự .
    Code:
          if (root==NULL) //Cây rỗng
          {
                     -In ra cây rỗng
          }
          else
          {
                     -Khởi tạo Stack
                     -Đẩy root vào Stack
          }
          while (Stack còn chưa rỗng)
          {
                     -Lấy phần tử từ đỉnh Stack ra cho vào biến Node
                     if (Node!=NULL)
                     {
                          -Thăm Node (In ra giá trị tại nút Node v.v...)
                          -Nếu con phải của Node Node->right !=NULL ->đẩy vào Stack
                          -Đi xuống con trái Node=Node->left
                     } 
          }
    Mình chỉ nêu ra thuật toán còn tạo Stack thế nào các phép toán với Stack như đẩy phần tử vào Stack lấy phần tử ra kiểm tra Stack rỗng chắc bạn biết làm rồi phải không . Chúc bạn viết thành công .

  3. #3
    Ngày gia nhập
    09 2008
    Nơi ở
    TP HCM
    Bài viết
    0

    Bạn có thể giải thích thêm cái đoạn này được không, mình chưa hiểu lắm.Cám ơn bạn nhiều.
    "-Nếu con phải của Node Node->right !=NULL ->đẩy vào Stack
    -Đi xuống con trái Node=Node->left"

  4. #4
    Ngày gia nhập
    11 2008
    Nơi ở
    Neverland
    Bài viết
    48

    Mình viết rõ ràng lắm mà : Khi lấy nút Node ra từ Stack đầu tiên bạn thăm nút đó sau đó nếu tồn tại nút con phải của nó tức là Node->right!=NULL . Lúc đó lưu địa chỉ nút con phải của nút Node lại (đưa nó vào Stack) để thăm sau rồi tiếp tục duyệt xang nhánh bên trái .

Các đề tài tương tự

  1. Hướng dẫn nạp tiền bằng thẻ cào trên trình duyệt di động
    Gửi bởi GBkhuyenvu2012 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 04-12-2013, 04:22 PM
  2. Trình duyệt Opera, giúp bạn trải nghiệm tốt hơn khi duyệt wap
    Gửi bởi hailuacuibep trong diễn đàn Software (Phần mềm) | Ebooks
    Trả lời: 2
    Bài viết cuối: 02-01-2013, 12:12 PM
  3. Fire fox 8.01 - Trình Duyệt Web Số 1 Thế Giới
    Gửi bởi gdra trong diễn đàn Software (Phần mềm) | Ebooks
    Trả lời: 0
    Bài viết cuối: 06-12-2011, 04:08 PM
  4. Duyệt các controls bằng foreach thì control nào sẽ được duyệt trước
    Gửi bởi chitviv trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 4
    Bài viết cuối: 05-10-2011, 10:01 PM
  5. Cách thức duyệt tiền tự trên cây khi duyệt từ con trái nhất rồi sang anh em ruột phải?
    Gửi bởi tyrant trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 14-09-2011, 10:53 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn