13. Binar daraxtning barcha barglari yozuvini chop etuvchi dastur ishlab chiqing
Download 186.12 Kb. Pdf ko'rish
|
4-lab
|
13. Binar daraxtning barcha barglari yozuvini chop etuvchi dastur ishlab chiqing.
#include using namespace std; void print_vector(vector cout << "[ \n ";
for ( int i = 0 ; i cout << "[";
(
int ; j cout << v[i][j] << ", ";
}
";
cout << "]"< }
{
public: int
TreeNode *left, *right; TreeNode(
int
val = data; left = right = NULL;
}
void insert(TreeNode **root, val){
queue q.push(*root);
(q.size()){ TreeNode *temp = q.front(); q.pop();
( ! temp->left){
if (val != NULL) temp->left = new TreeNode(val);
else
temp->left = new TreeNode( 0 );
return ; } else {
q.push(temp->left); }
if ( ! temp->right){
if (val != NULL) temp->right = new TreeNode(val);
else
temp->right = new TreeNode( 0 );
return ; } else {
q.push(temp->right); }
} } TreeNode *make_tree(vector< int > v){
TreeNode *root = new TreeNode(v[ 0 ]);
for ( int i = 1 ; i insert(&root, v[i]);
}
root;
getHeight(TreeNode* node){ if ( ! node) return
;
return
+ max
(getHeight(node->left), getHeight(node->right)); }
void fill(TreeNode* node, vector int
lvl, int
l, int
r){
if ( ! node || node->val == 0 )
; ret[lvl][(l + r) / 2 ] = to_string(node->val); fill(node->left, ret, lvl +
, l, (l + r) / 2 );
fill(node->right, ret, lvl + 1 , (l + r + 1 ) /
2 , r);
} vector
int
h = getHeight(root);
int leaves = ( 1 << h) - 1 ; vector < vector fill(root, ret, 0 ,
, leaves);
return ret;
}
int main(){ int
> v = { 1 ,
,
,
,
,
,
};
TreeNode *root = make_tree(v); print_vector(printTree(root));
return
; }
using namespace std; void print_vector(vector cout << "[ \n ";
for ( int i = 0 ; i cout << "[";
(
int ; j cout << v[i][j] << ", ";
}
";
cout << "]"< }
{
public: int
TreeNode *left, *right; TreeNode(
int
val = data; left = right = NULL;
}
void insert(TreeNode **root, val){
queue q.push(*root);
(q.size()){ TreeNode *temp = q.front(); q.pop();
( ! temp->left){
if (val != NULL) temp->left = new TreeNode(val);
else
temp->left = new TreeNode( 0 );
return ; } else {
q.push(temp->left); }
if ( ! temp->right){
if (val != NULL) temp->right = new TreeNode(val);
else
temp->right = new TreeNode( 0 );
return ; } else {
q.push(temp->right); }
} } TreeNode *make_tree(vector< int > v){
TreeNode *root = new TreeNode(v[ 0 ]);
for ( int i = 1 ; i insert(&root, v[i]);
}
root;
getHeight(TreeNode* node){
(
!
;
return
+ max
(getHeight(node->left), getHeight(node->right)); }
void fill(TreeNode* node, vector int
lvl, int
l, int
r){
if ( ! node || node->val == 0 )
; ret[lvl][(l + r) / 2 ] = to_string(node->val); fill(node->left, ret, lvl +
, l, (l + r) / 2 );
fill(node->right, ret, lvl + 1 , (l + r + 1 ) /
2 , r);
} vector
int
h = getHeight(root);
int leaves = ( 1 << h) - 1 ; vector < vector fill(root, ret, 0 ,
, leaves);
return ret;
}
int main(){ vector< int
> v = { 1 ,
,
,
,
,
,
};
TreeNode *root = make_tree(v); print_vector(printTree(root));
return
; }
2. Berilgan binar daraxt muvozanatlanganmi yoki yo’qligini tekshiring. #include
std;
class
{
public:
int val;
TreeNode *left, *right; TreeNode( int data){
val = data; left = right = NULL ;
}; int
(TreeNode* node);
bool
(TreeNode* root) {
int lh;
int rh;
if (root == NULL )
return
;
lh = height(root->left); rh = height(root->right);
if (abs(lh - rh) <= 1 && isBalanced(root->left) && isBalanced(root- >right))
return
;
return
; }
int
(
a,
int b)
{
return (a >= b) ? a : b; }
int
(TreeNode* node) {
if (node == NULL )
return
;
return
+ max(height(node->left), height(node->right)); }
TreeNode* newNode (
data) {
TreeNode* Node = new TreeNode(data); Node->left = NULL
; Node->right = NULL ;
return (Node); }
(vector cout << "[ \n ";
for (
i =
; i cout << "[";
(
j =
; j cout << v[i][j] << ", ";
}
";
cout << "]"< }
(TreeNode **root,
val){
q.push(*root);
(q.size()){ TreeNode *temp = q.front();
q.pop();
(!temp->left){ temp->left =
TreeNode(val);
;
} {
}
(!temp->right){ temp->right =
TreeNode(val);
;
} {
q.push(temp->right); }
} } TreeNode * make_tree (vector<
int > v){
TreeNode *root = new TreeNode(v[ 0 ]);
for (
i =
; i insert(&root, v[i]);
}
root;
(TreeNode* node){
if (!node)
return
;
return
+ max(getHeight(node->left), getHeight(node->right)); }
void
(TreeNode* node, vector lvl,
int l,
int
r){ if (!node || node->val == 0 )
; ret[lvl][(l + r) / 2 ] = to_string(node->val); fill(node->left, ret, lvl +
, l, (l + r) / 2 );
fill(node->right, ret, lvl + 1 , (l + r + 1 ) /
2 , r);
} vector
h = getHeight(root);
leaves = ( 1 << h) - 1 ; vector < vector fill(root, ret, 0 ,
, leaves);
return ret;
}
int main() { TreeNode* root = newNode( 1 );
root->left = newNode( 2 );
root->right = newNode( 3 );
root->left->left = newNode( 4 );
root->left->right = newNode( 5 );
root->left->left->left = newNode( 8 );
print_vector(printTree(root));
(isBalanced(root)) cout << "Binar daraxt muvozanatlangan";
else
cout << "Binar daraxt muvozanatlangan"; return
; }
Download 186.12 Kb. Do'stlaringiz bilan baham: 
|