Thực hiện hàm new_xmas_tree (int height), tạo một cây mới được tạo với độ sâu nhất định

#1

chào mọi người, e có 1 bài tập cụ thể là viết thêm vào 1 function cho trước sao cho đạt được yêu cầu như title e đã ghi . mong mọi người giúp đỡ hoặc đưa ra pseudo code cũng đc ạ .
Trong bài có thể viết thêm help func tuỳ ý.
code viết với c-programming.
Hàm cần implement nằm ở dòng 115

e copy code lên đây mời anh chị bấm vào ạ . (http://tpcg.io/KsiVzW)

b) Thực hiện hàm new_branch (Branch *left, Branch * right), sẽ trả về 1 nhánh mới . Biến dry nên được khởi tạo thành false. Phần tử treo trên cành cây(Branch) được cho là chứa một ngôi sao, một ngọn nến hoặc một quả bóng. (phần này e đã viết a chị có thể xem qua. e nghĩ nó có hữu ích với các phần dưới )
c) Thực hiện hàm new_xmas_tree (int height), tạo một cây mới được tạo với độ sâu nhất định

Giải thích thêm là i_rnd(int number) hay d_rnd(double number) là tạo ra số ngẫu nhiên từ 0 -> number input ạ

Cảm ơn anh chị

#2

Dùng thuật toán duyệt cây nhé bạn :smiley:

{ pseudo :D }
def Tree::populate(doBranch: proc(Branch), height: integer) begin
   if(height <= 0) return;
   assert root.nil? raise exception { cây đang còn đó mà }
   root = Branch.new;
   doBranch(root);
   root.grow(doBranch, height);
end
def Branch::grow(doBranch: proc(Branch), height: integer) begin
   if(height <= 1) return;
   proc.left = Branch.new; { mặc định là NULL cả hai cây con }
   proc.right = Branch.new;
   doBranch(self);
   self.left.grow(doNode, height-1);
   self.right.grow(doNode, height-1);
end
2 Likes
#3

chào bạn cảm ơn ban trước. mình muốn hỏi là doNode: proc ở đây nghĩa là gì .
nếu và doNode (self) thì là gi vậy.

#4

doNote là 1 process.

Đây chỉ là mã giả thôi, không phải code của ngôn ngữ nào cả.

1 Like
#5

ra là process. e cảm ơn.

#6

procedure chứ :smiley:

Mình tách ra là để cho code linh hoạt hơn :slight_smile: Cách duyệt cây thường là ko đổi, nhưng hành động với mỗi node sẽ thay đổi, gọi là “separation of concerns” :slight_smile:

2 Likes
#7

ở đoạn này là tạo ra 1 branch mới có vị trí trỏ là left hoặc right.
vậy e sẽ tạo 1 branch mới thế nào khi e muốn sử dụng hàm e đã viết bên trên

Branch *new_branch(Branch *left, Branch *right):: return Branch.

vì ở đây cần input vào 2 params đều là type Branch.

Còn 1 vấn đề nếu dùng calloc hay malloc để cấp phát bộ nhớ tạo ra 1 branch mà không dùng hàm đã viết "new_branch " thì lúc này trong struct của Branch có

struct Branch* left;
struct Branch* right;

thì sẽ nhận input đầu vào thế nào ạ .

e chưa hiểu nhất đoạn tao Branch mới này

#8

Viết tắt đó mà :smiley: sorry.

Ừ nhỉ :smiley: mà hàm đó sao lại có hai câu return branch; liên tiếp vậy?

2 Likes
#9

à dòng đó bị thừa đó bạn.

#10

Mình cũng thấy hàm này nó kì kì, kiểu như là từ nhánh về gốc vậy. Hàm có thể sẽ dùng trong một cây cân bằng nào đó chứ new thì khá là chuối. Thôi thì cứ pass NULL NULL vậy.

1 Like
#11

36
Bildschirmfoto 2018-12-27 um 23.00.36.png1584×518 7.58 KB

Tiefe = depth .
cái này là cái mô tả mà ở đề bài vẽ ra. không mình biết giúp gì được không

#12

yêu cầu đề bài ở phần đó là câu a:
Implement the new_branch function (Branch * left, Branch * right), which will pass two branches and create a new branch that will have these left and right children.

#13

Thì đồng ý là branch = malloc() rồi set left set right, nhưng sử dụng hàm đó thì phải build từ nhánh về gốc trừ phi bypass bằng (NULL, NULL) :smiley:

1 Like
#14

Mình vừa hỏi giáo sư thì ông đưa gợi ý thế này
The function gets the height that the tree should have. A tree with Branch = NULL has height 0, a tree with Branch! = NULL has at least height 1 … My recommendation is to create the tree in the function and the branches in a recursive Help-func
Solution của b đưa ra đúng ý oy. Nhưng mình chưa biết làm sao hoy. Cảm ơn b đã quan tâm nhé.
Mong đc trao đổi cùng bạn tiếp

#15

Mình cũng nhận ra vì sao và cách build như thế nào rồi :smiley:

2 Likes
#17

cho min hỏi đoạn này gán đẹ quy thế nào b.
hiện tại mình với viết đến đây

Branch *new_xmas_branch(Branch *branch, int height)
{
 if (height <= 1)  return 0;
  
 branch->left = new_branch(NULL, NULL);
 branch->right = new_branch(NULL, NULL);

 return branch;
}
#18

Thật ra… lúc đó mình đang hiểu sai ý đồ :smiley: giờ phải thay đổi cách duyệt cây, do hai cây con phải được tạo trước, nếu không thì dữ liệu sẽ không đúng.

1 Like
#19 
{ pseudo }
contract BinaryNode(type X) begin
   X.must: [X getLeft(), X getRight(), type::Any getValue(), type::Any setValue()]
   X.must: [setLeft(X), setRight(X)]
end;
contract ForSelfBalancingBinaryTrees << BinaryNode begin
   X.may: [X getParent(X), X getUncle(X)]
end;
contract ForPopulating(type X) begin { cây nào cũng "grow" được }
   X.must(Y): [type Y in [X, void] grow(type::Any) ]
end;

class Branch<generic T> comply BinaryNode, ForPopulating
begin
   open: value: T
   open-for-container: left, right: Branch<T> { ý là dùng friend của C++ }
   read-only: height: UInteger := 0
   def self.height(left, right: Branch<T>) begin
       return 1 + max(left.nil? 0 : left.height, right.nil? 0 : right.height);
   end
   def setLeft(Branch<T>) begin height = self.height(left, right); end
   def setRight(Branch<T>) begin height = self.height(left, right); end
   def init(left, right: Branch<T>) begin
      self.left := left; self.right := right;
      self.height := Branch.height(left, right)
   end

   def self.grow(height: uInteger, doBranch: proc(Branch<T>) = {}): Branch<T> begin
     if(height <= 1) begin t := Branch<T>.new(nil, nil); doBranch(t); end
     else begin
       t := Branch<T>.new(self.grow(height-1, doBranch),
                          self.grow(height-1, doBranch)); 
       doBranch(t);
     end
     return t;
   end
end
2 Likes
#20

cảm ơn bạn minh đang nghiên cứu. pseudo code của b

#21

Thực ra duyệt cây nhị phân có ba cách (chính):

  • Node Left Right
  • Left Node Right
  • Left Right Node

với Left Right là lời gọi đệ quy. Cây là thực thể tự đồng dạng - nên ta sẽ nhìn theo kiểu đệ quy, góc nhìn rất cần thiết khi đi sâu vào cây.

Bài này sử dụng 1 trong 3 cách duyệt (ban đầu mình lầm :smiley: ) khi nào có Branch (gốc) thì mới doBranch được. Một chủ đề khó sau này là cân bằng cây để truy cập và thao tác nhanh.

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