Scribd
Upload
5 views8 pages

Code Cây

The document contains a C program that implements a binary tree with various functionalities such as insertion, traversal (pre-order, in-order, post-order), counting nodes (leaf, internal, even, odd, positive, negative), summing values of nodes, searching for a node, and deleting a node. It also includes functions to print node information and calculate the height of the tree. The main function allows user interaction to create a binary tree and perform operations on it.

Uploaded by

nguyenquan.420267
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views8 pages

Code Cây

The document contains a C program that implements a binary tree with various functionalities such as insertion, traversal (pre-order, in-order, post-order), counting nodes (leaf, internal, even, odd, positive, negative), summing values of nodes, searching for a node, and deleting a node. It also includes functions to print node information and calculate the height of the tree. The main function allows user interaction to create a binary tree and perform operations on it.

Uploaded by

nguyenquan.420267
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

#include<stdio.

h>
#include<stdlib.h>
typedef int kieudl;
typedef struct TNode* TNodeType;
struct TNode{
kieudl dl;
TNodeType left, right;
};
typedef TNodeType TTree; //con tro tro den node root
void makeNullTree(TTree *T){
(*T)=NULL;
}
int emptyTree(TTree T){
return (T==NULL);
}
TTree leftChild(TTree n){ //TTree là ki?u d? li?u mà hàm tr? v?
if(n!=NULL) return (n->left);
else return NULL;
}
TTree rightChild(TTree n){
if(n!=NULL) return (n->right);
else return NULL;
}
int isLeaf(TTree n){
if(n!=NULL) return (leftChild(n)==NULL) && (rightChild(n)==NULL);
else return 0;
}
TTree nhap(TTree T, kieudl x){
if(T==NULL){
TTree P=(TTree)malloc(sizeof(struct TNode));
P->dl=x;
P->left = P->right = NULL;
return P;
}
else if(x<T->dl){
T->left=nhap(T->left,x);
}
else if(x>T->dl){
T->right=nhap(T->right,x);
}
return T;
}
//Duyet Tien T?
void duyettientu(TTree T){
printf("[%d]",T->dl);
if(leftChild(T)!=NULL)
duyettientu(leftChild(T));
if(rightChild(T)!=NULL)
duyettientu(rightChild(T));
}
// Duy?t Trung T?
void duyettrungtu(TTree T){
if(leftChild(T)!=NULL)
duyettrungtu(leftChild(T));
printf("[%d]",T->dl);
if(rightChild(T)!=NULL)
duyettrungtu(rightChild(T));
}
// Duy?t H?u T?
void duyethautu(TTree T){
if(leftChild(T)!=NULL)
duyethautu(leftChild(T));
if(rightChild(T)!=NULL)
duyethautu(rightChild(T));
printf("[%d]",T->dl);
}
// ??m nút lá
int demisLeaf(TTree T){
if(T == NULL)
return 0;
if(T->left==NULL && T->right==NULL)
return 1; // root là lá
return demisLeaf(T->left) + demisLeaf(T->right);
}
// ??m nút trong (Nút có 2 con)
int demNodetrong(TTree T){ // ??m nút 2 con
if(T==NULL)
return 0;
if(T->left==NULL && T->right==NULL)
return 0;
return 1 + demNodetrong(T->left) + demNodetrong(T->right);
}
// ??m nút có 1 con
int demNode1Leaf(TTree T){ //??m nút có 1 con
if(T==NULL)
return 0;
int left = demNode1Leaf(T->left);
int right = demNode1Leaf(T->right);
int dem=0;
if((T->left==NULL && T->right!=NULL) || (T->left!=NULL && T-
>right==NULL))
dem=1;
return left + right + dem;
}
// ??m các nút ch?n
int demnutchan(TTree T){
if(T==NULL)
return 0;
int dem=0;
if(T->dl%2==0)
dem=1;
return dem + demnutchan(T->left) + demnutchan(T->right);
}
// ??m nút l?
int demnutle(TTree T){
if(T==NULL)
return 0;
int demle=0;
if(T->dl%2!=0)
demle=1;
return demle + demnutle(T->left) + demnutle(T->right);
}
// ??m nút d??ng
int demnutduong(TTree T){
if(T==NULL)
return 0;
int demduong=0;
if(T->dl>0)
demduong=1;
return demduong + demnutduong(T->left) + demnutduong(T-
>right);
}
// nút có 2 con
void timNode2Con(TTree T){
if(T == NULL)
return;

if(T->left != NULL && T->right != NULL){


printf("Node co 2 con: %d\n", T->dl);
}

timNode2Con(T->left);
timNode2Con(T->right);
}

// nút có 1 con
void timNode1Con(TTree T){
if(T == NULL)
return;

if((T->left == NULL && T->right != NULL) ||


(T->left != NULL && T->right == NULL)){
printf("Node chi co 1 con: %d\n", T->dl);
}

timNode1Con(T->left);
timNode1Con(T->right);
}

// ??m nút âm
int demnutam(TTree T){
if(T==NULL)
return 0;
int demam=0;
if(T->dl<0)
demam = 1;
return demam + demnutam(T->left) + demnutam(T->right);
}
// ??m t?ng s? nút
int tongsonut(TTree T){
if(T==NULL)
return 0;
return 1 + tongsonut(T->left) + tongsonut(T->right);
}
// T?ng giá tr? các nút ch?n
int sumnutchan(TTree T){
if(T==NULL)
return 0;
int sum=0;
if(T->dl%2==0)
sum=T->dl;
return sum + sumnutchan(T->left) + sumnutchan(T->right);
}
// T?ng giá tr? các nút l?
int sumnutle(TTree T){
if(T==NULL)
return 0;
int sum=0;
if(T->dl%2!=0)
sum=T->dl;
return sum + sumnutle(T->left) + sumnutle(T->right);
}
// tong câc nút trong
int sumnuttrong(TTree T){
if(T == NULL)
return 0;

int sum = 0;

if(T->left != NULL || T->right != NULL)


sum = T->dl;

return sum + sumnuttrong(T->left) + sumnuttrong(T->right);


}
// tong cac nut la
int sumnutla(TTree T){
if(T == NULL)
return 0;

if(T->left == NULL && T->right == NULL)


return T->dl;

return sumnutla(T->left) + sumnutla(T->right);


}

// T?ng giá tr? t?t c? nút


int tonggiatri(TTree T){
if(T==NULL)
return 0;
int sum =0;
sum = T->dl;
return sum + tonggiatri(T->left) + tonggiatri(T->right);
}
void printNodeInfo(TTree T) {
if (T != NULL) {
printf("Node: %d", T->dl);
printf(" | Left: ");
if (T->left != NULL)
printf("%d", T->left->dl);
else
printf("NULL");

printf(" | Right: ");


if (T->right != NULL)
printf("%d", T->right->dl);
else
printf("NULL");
printf("\n");

printNodeInfo(T->left);
printNodeInfo(T->right);
}
}
// tong nut co 2 con
int demNode2Con(TTree T){
if(T == NULL)
return 0;

int dem = 0;

if(T->left != NULL && T->right != NULL)


dem = 1;

return dem + demNode2Con(T->left) + demNode2Con(T->right);


}
// tong nut co 1 con
int sumnut1Con(TTree T){
if(T == NULL)
return 0;

int sum = 0;
// nút có dúng 1 con
if((T->left == NULL && T->right != NULL) ||
(T->left != NULL && T->right == NULL))
sum = T->dl;

return sum + sumnut1Con(T->left) + sumnut1Con(T->right);


}

// Hàm tình t?ng giá tr? nút d??ng


int sumnutduong(TTree T){
if(T==NULL)
return 0;
int sum =0;
if(T->dl>0)
sum = T->dl;
return sum + sumnutduong(T->left) + sumnutduong(T->right);
}
// Hàm tình t?ng giá tr? nút âm
int sumnutam(TTree T){
if(T==NULL)
return 0;
int sum =0;
if(T->dl<0)
sum = T->dl;
return sum + sumnutam(T->left) + sumnutam(T->right);
}
// Hàm tìm ki?m
TTree search(TTree T, kieudl x){
if(T==NULL) return NULL;
else if(T->dl==x)
return T;
else if(T->dl<x)
return search(T->right,x);
else return search(T->left,x);
}
// Hàm xóa nút
TTree deleteNode(TTree T, int x) {
if (T == NULL) return NULL;

if (x < T->dl) {
T->left = deleteNode(T->left, x);
} else if (x > T->dl) {
T->right = deleteNode(T->right, x);
} else {
// Tìm th?y node c?n xóa
if (T->left == NULL) {
TTree temp = T->right;
free(T);
return temp;
} else if (T->right == NULL) {
TTree temp = T->left;
free(T);
return temp;
} else {
// Node có 2 con: tìm node nh? nh?t ? cây con ph?i
TTree temp = T->right;
while (temp->left != NULL) {
temp = temp->left;
}
T->dl = temp->dl;
T->right = deleteNode(T->right, temp->dl);
}
}
return T;
}
// Hàm tình chi?u cao c?a cây
int height(TTree t) {
if (t == NULL)
return -1; // ho?c return 0 n?u dùng quy ??c cây r?ng cao 0
int hL = height(t->left);
int hR = height(t->right);
return (hL > hR ? hL : hR) + 1;
}
int main(){
TTree T;
makeNullTree(&T);
int n,x;
printf("Nhap so luong phan tu cua cay: ");
scanf("%d",&n);
for(int i=0;i<n;i++){
printf("Nhap gia tri phan tu thu %d: ",i+1);
scanf("%d",&x);
T=nhap(T,x);
}
printf("Da tao xong cay!\n");
printf("Cay co rong %d\n",emptyTree(T));
printf("Gia tri goc: %d\n",T->dl);
printf("\nDuyet tien tu:\n");
duyettientu(T);
printf("\nDuyet trung tu:\n");
duyettrungtu(T);
printf("\nDuyet hau tu:\n");
duyethautu(T);
printf("\nTong so nut la: %d\n",demisLeaf(T));
printf("\nTong so nut trong la: %d\n",demNodetrong(T));
printf("\nTong so nut chan la: %d\n",demnutchan(T));
printf("\nTong so nut le la: %d\n",demnutle(T));
printf("\nTong so nut duong la: %d\n",demnutduong(T));
printf("\nTong so nut am la: %d\n",demnutam(T));
printf("\nTong so nut la: %d\n",tongsonut(T));
printf("\nTong cac gia tri chan trong cay la: %d\n",sumnutchan(T));
printf("\nTong cac gia tri le trong cay la: %d\n",sumnutle(T));
printf("\nTong gia tri cac nut trong cay la: %d\n",tonggiatri(T));
printf("\nChieu cao cua cay la: %d\n",height(T));
printf("\nTong gia tri cac nut trong la: %d\n", sumnuttrong(T));
printf("\nTong gia tri cac nut la: %d\n", sumnutla(T));
printf("\nTong so nut co 2 con la: %d\n", demNode2Con(T));
printf("\nTong gia tri cac nut co 1 con la: %d\n", sumnut1Con(T));

int m;
printf("\nNhap x: ");
scanf("%d",&m);

TTree kq = search(T, m);


if (kq != NULL)
printf("Da tim thay x = %d\n", kq->dl);
else
printf("Khong tim thay x = %d\n", m);

int v;
printf("Nhap gia tri can xoa: ");
scanf("%d",&v);
printf("Xoa %d",v);
T=deleteNode(T,v);
printf("\nCay sau khi xoa:\n");
printNodeInfo(T);
printf("\nCac nut chi co 1 con:\n");
timNode1Con(T);
printf("\nCac nut co 2 con:\n");
timNode2Con(T);

return 0;
}

You might also like