Cây liên tục trong C ++

Cây liên tục được định nghĩa là cây với bất kỳ đường dẫn nào từ nút gốc đến nút lá đều có giá trị hoặc trọng số của các nút sao cho sự khác biệt tuyệt đối giữa nút cha và tất cả các nút con trực tiếp của nó luôn là 1.

Nếu chúng ta chọn bất kỳ nút nào trên đường dẫn từ gốc đến lá, thì

| trọng số của nút-trọng số của nút con trái | =| trọng số của nút con trái-trọng số của nút | =1, điều này cũng đúng đối với đúng trẻ em

| weight of node-weight của nút con bên phải | =| weight lof trọng số của nút con bên phải của nút | =1

Sơ đồ

Hãy cho chúng tôi hiểu với các ví dụ.

Cây bên dưới là liên tục vì sự khác biệt tuyệt đối giữa các nút cha và các nút con của chúng là luôn luôn 1.

Cây dưới đây không đủ tiêu chuẩn để trở thành Cây liên tục.

Thuật toán tìm cây có liên tục không

• Nếu gốc là NULL, trả về 1

• Nếu đó là một nút lá, hãy trả về 1 vì cây đã Liên tục, đó là lý do tại sao nút đó lại được đính kèm.

• Nếu cây con bên trái trống, hãy kiểm tra tính liên tục của nút hiện tại với nút con bên phải (tính toán chênh lệch trọng số tuyệt đối) và tiếp tục cho cây con bên phải một cách đệ quy.

• Nếu cây con bên phải trống, hãy kiểm tra tính liên tục của nút hiện tại với nút con bên trái (tính toán chênh lệch trọng số tuyệt đối) và tiếp tục cho cây con bên trái một cách đệ quy.

• Khác tính toán chênh lệch tuyệt đối với trọng số của con trái và con phải và tiếp tục cho các cây con bên trái và bên phải, một cách đệ quy.

Mã giả

// Function to check tree is continuous or not
struct btreeNode{
   int data;
   btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
   // if node is NULL return 1, exit condition
   if (root == NULL)
      return 1;
   //if leaf node is reached then tree must be continous during this path
   if (root->left == NULL && root->right == NULL)
      return 1;
   // if no left child
   if (root->left == NULL)
      return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
   // if no right child
   if (root->right == NULL)
      return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
      // calculate absoute difference
      return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
   isContinuous(root->left) && isContinuous(root->right);
}