no

#include <iostream>
#include <malloc.h>
#include <stdio.h>
#include <queue>
#include <stack>
#include <Windows.h> //GetAsyncKeyState
#include <string>
#include <utility>
#include <vector>
#include <functional>
#include <conio.h> //kbhit
#include <set>
#include <math.h>
#include <map>
#include <ctime>
#include <algorithm>
#include <fstream>
#include <unordered_map> // hashmap
#include "console.h"
using namespace std;

//struct SkewHeap
//{
//	int key;
//	SkewHeap *left;
//	SkewHeap *right;
//};
//
//void Init(SkewHeap *sh)
//{
//	sh->key = 0;
//	sh->left = NULL;
//	sh->right = NULL;
//}
//
//SkewHeap* Merge(SkewHeap *h1, SkewHeap *h2)
//{
//	SkewHeap *temp = new SkewHeap;
//	if (h1 == NULL)
//		return h2;
//	else if (h2 == NULL)
//		return h1;
//	else {//Bước 1
//		if (h1->key < h2->key)
//		{
//			temp = h1;
//			h1 = h2;
//			h2 = temp;
//		}
//		//Bước 2
//		temp = h1->left;
//		h1->left = h1->right;
//		h1->right = temp;
//		//Bước 3
//		h1->left = Merge(h2, h1->left);
//	}
//	return h1;
//}
//
//SkewHeap* Insert(SkewHeap *root)
//{
//	int value;
//	cout << "Nhap gia tri can chen:";
//	cin >> value;
//	SkewHeap *temp = new SkewHeap;
//	Init(temp);
//	temp->key = value;
//	root = Merge(root, temp);
//	return root;
//}
//SkewHeap* constructs(SkewHeap* root, int heap[], int n)
//{
//	SkewHeap* temp;
//
//	for (int i = 0; i < n; i++) {
//		temp = new SkewHeap;
//		Init(temp);
//		temp->key = heap[i];
//		root = Merge(root, temp);
//	}
//	return root;
//}
//
//SkewHeap* DeleteMax(SkewHeap *root)
//{
//	if (root == NULL)
//	{
//		cout << "Skew Heap rong!";
//		return NULL;
//	}
//	SkewHeap *temp1;
//	SkewHeap *temp2;
//	temp1 = root->left;
//	temp2 = root->right;
//	temp1 = Merge(temp1, temp2);
//
//	return temp1;
//}
//
//void PreOrder(SkewHeap *root) {
//	if (root == NULL)
//		return;
//	else {		
//		cout << root->key << "  ";
//		PreOrder(root->left);
//		PreOrder(root->right);
//	}
//	return;
//}
//
//void InOrder(SkewHeap *root) {
//	if (root == NULL)
//		return;
//	else {
//		InOrder(root->left);
//		cout << root->key << "  ";
//		InOrder(root->right);
//	}
//	return;
//}
//
//void PostOrder(SkewHeap *root) {
//	if (root == NULL)
//		return;
//	else {
//		PostOrder(root->left);
//		PostOrder(root->right);
//		cout << root->key << "  ";
//	}
//	return;
//}
//
//void print_heap(SkewHeap *root)
//{
//
//	cout << "Preorder traversal of the heap is " << endl;
//	PreOrder(root);
//	cout << endl;
//
//	cout << "Inorder traversal of the heap is " << endl;
//	InOrder(root);
//	cout << endl;
//
//	cout << "Postorder traversal of the heap is " << endl;
//	PostOrder(root);
//	cout << endl;
//}
//
//
//int main()
//{
//	// Construct two heaps
//	SkewHeap *temp1 = NULL, *temp2 = NULL;
//
//	int heap1[] = { 12, 5, 10 };
//	int heap2[] = { 3, 7, 8, 14 };
//
//	int n1 = sizeof(heap1) / sizeof(heap1[0]);
//	int n2 = sizeof(heap2) / sizeof(heap2[0]);
//
//	temp1 = constructs(temp1, heap1, n1);
//	temp2 = constructs(temp2, heap2, n2);
//
//	// Merge two heaps
//	temp1 = Merge(temp1, temp2);
//	/*
//			3
//		   / \
//		  /   \
//		 5     7
//		/ \   /
//	   8  10 14
//	  /
//	 12    */
//	cout << "Merged Heap is: " << endl;
//
//	print_heap(temp1);
//
//	return 0;
//}



struct Node
{
	int Data; 
	struct Node *Left, *Right; // Trỏ tới các Node cây con trái và cây con phải
	bool TinhTrangDuyet;
	int ThuTuDuyet;
	struct Node *Cha;
};
typedef struct Node NODE;

NODE* TimKiemNode_DeQuy(NODE *Root, int x, NODE *NodeTruocNull);

/* 2/ Khởi tạo cây */

void INit(NODE *&Root)
{
	Root = NULL;
}


/* 3/ Tạo node */

// Tạo 1 Node mới chứa dữ liệu x và trả về địa chỉ của Node đó sau khi tạo xong
NODE* GetNode(int x) // x là dữ liệu mà sẽ đưa nó vào trong Node
{
	//NODE *p = new NODE; // cấp phát con trỏ Node kiểu của bên C++
	NODE *p = (NODE *)malloc(sizeof(NODE)); // cấp phát con trỏ Node kiểu của bên C
	if (p == NULL)
		return NULL; // Không tạo thành công do thiếu vùng nhớ để cấp phát tạo ra Node

	// Nếu vẫn còn chạy được xuống đây tức là không thỏa cái if => Node được tạo thành công
	p->Data = x; // đưa dữ liệu x vào trong Node p
	p->Left = p->Right = NULL; // cập nhật con trỏ Left, Right là NULL
	p->Cha = NULL;

	return p; // trả về Node p đã được tạo
}

/* End 3 */

// 40, 5, 35, 45, 15, 56, 48, 13, 16, 49, 47
// return 1: Thành công
// return 0: Không thành công (bị trùng)
// return -1: Không thành công (không đủ bộ nhớ để cấp phát cho Node)
int ThemNodeVaoCay_DeQuy(NODE *&Root, int x, NODE *k) // thêm giá trị x vào cây
{
	if (Root != NULL)
	{
		// điều kiện đệ quy

		if (x > Root->Data)
			return ThemNodeVaoCay_DeQuy(Root->Right, x, Root);
		else if (x < Root->Data)
			return ThemNodeVaoCay_DeQuy(Root->Left, x, Root);
		else
		{
			//printf("\nGia tri Node nay da co ton tai trong cay roi cho nen khong tao moi nua");
			return 0; // không thành công (bị trùng)
		}
	}
	else // Root == NULL
	{
		//Root = GetNode(x); // Dừng đệ quy => Tạo Node chứa giá trị cần thêm vào
		NODE *ConMoi = GetNode(x);

		if (ConMoi == NULL)
			return -1; // Không thành công (không đủ bộ nhớ để cấp phát cho Node)

		Root = ConMoi;

		ConMoi->Cha = k;
	}
	return 1; // thành công
}


void TaoCayTuDaySo(NODE *&Root, int a[], int n) 
{
	INit(Root); 

	for (int i = 0; i < n; ++i) 
	{
		ThemNodeVaoCay_DeQuy(Root, a[i], NULL);

	}
}

void NLR(NODE *Root)
{
	if (Root != NULL)
	{
		printf("%d ", Root->Data);
		NLR(Root->Left);
		NLR(Root->Right);
	}
}

void LNR(NODE *Root)
{
	if (Root != NULL)
	{
		LNR(Root->Left);
		printf("%d ", Root->Data);
		LNR(Root->Right);
	}
}

void RNL(NODE *Root)
{
	if (Root != NULL)
	{
		RNL(Root->Right);
		printf("%d ", Root->Data);
		RNL(Root->Left);
	}
}

void LRN(NODE *Root)
{
	if (Root != NULL)
	{
		LRN(Root->Left);
		LRN(Root->Right);
		printf("%d ", Root->Data);
	}
}

// 1: left -> right, khác 1: right->left
void DuyetTheoChieuRong(NODE *Root, int thutu = 1)
{
	queue<NODE *> q;

	// Phải có tồn tại Node gốc thì mới đưa Node gốc đó vào hàng đợi
	if (Root != NULL)
		q.push(Root);

	while (!q.empty()) // lặ[ liên tục khi hàng đợi còn phần tử
	{
		NODE *p = q.front(); // Lấy ra Node đầu hàng đợi
		printf("%d ", p->Data);
		q.pop(); // bỏ Node ra khỏi hàng đợi

		if (thutu == 1)
		{
			if (p->Left != NULL) // có tồn tại Node con trái của p
				q.push(p->Left); // Đưa con trái vào hàng đợi

			if (p->Right != NULL) // có tồn tại Node con phải của p
				q.push(p->Right); // Đưa con phải vào hàng đợi
		}
		else
		{
			if (p->Right != NULL) // có tồn tại Node con phải của p
				q.push(p->Right); // Đưa con phải vào hàng đợi

			if (p->Left != NULL) // có tồn tại Node con trái của p
				q.push(p->Left); // Đưa con trái vào hàng đợi
		}
	}
}

// tìm giá trị x xem có tồn tại ở node nào đó trong cây không? Nếu có thì trả về node đó, nếu không có thì trả về node đứng trước node đó để phục vụ cho mục đích thêm node vào cây
NODE* TimKiemNode_DeQuy(NODE *Root, int x, NODE *NodeTruocNull)
{
	// Điều kiện dừng: Khi không tìm thấy
	if (Root == NULL)
		return NodeTruocNull;

	// Điều kiện đệ quy
	//if(Root != NULL) // Cũng không cần viết điều kiện này bởi vì chúng ta đã xét nếu Root == NULL ở đầu tiên của hàm nên nếu nó còn chạy được xuống dưới này tức là Root != NULL
	//{
	if (x > Root->Data)
		return TimKiemNode_DeQuy(Root->Right, x, Root);
	else if (x < Root->Data)
		return TimKiemNode_DeQuy(Root->Left, x, Root);
	else // x == Root->Data
		return Root; // Điều kiện dừng: Khi đã tìm thấy
//}
}

// p là Node thế mạng sẽ xóa
void TimPhanTuTheMang_DeQuy(NODE *&Root, NODE *&p, NODE *cha)
{
	if (Root->Right != NULL)
		TimPhanTuTheMang_DeQuy(Root->Right, p, Root);
	else // Lúc này Root->Right == NULL => Root là NODE phải nhất => đó là Node thế mạng
	{
		p->Data = Root->Data; // Gán giá trị của Node thế mạng (Root) sang giá trị của Node cần xóa (p)
		p = Root; // Cho con trỏ p trỏ tới Node thế mạng (Root) để kết thúc hàm thì sẽ free(p) chính là free(Root)
		Root = Root->Left; // Mục đích: Giữ liên kết với các Node con của Node bị xóa - Vì Root đang là Node phải nhất => sẽ không có con phải chỉ có thể có con trái hoặc không có con => cứ cho trỏ tới con trái

		if (Root != NULL && Root->Left != NULL)
			Root->Left->Cha = cha;
	}
}

void XoaNodeTrongCay_DeQuy(NODE *&Root, int x, NODE *cha = NULL) // x là giá trị cần xóa ra khỏi cây
{
	// Điều kiện dừng
	if (Root == NULL)
		return; // kết thúc vì cây không có gì để xóa hoặc không tìm thấy Node cần xóa (giá trị cần xóa x không tồn tại trong cây)

	// Bước đệ quy
	if (x > Root->Data)
		XoaNodeTrongCay_DeQuy(Root->Right, x, Root);
	else if (x < Root->Data)
		XoaNodeTrongCay_DeQuy(Root->Left, x, Root);
	else // tìm thấy x trong cây tại Node Root => xóa
	{
		NODE *p = Root; // p là Node sẽ bị xóa

		// TH1: Node cần xóa là Node lá
		// TH2: Node cần xóa là Node có 1 con

		// Giữ liên kết với phần còn lại của Node bị xóa
		if (p->Left == NULL)
		{
			Root = p->Right;

			if (p->Right != NULL)
				p->Right->Cha = cha;
		}
		else if (p->Right == NULL)
		{
			Root = p->Left;

			if (p->Left != NULL)
				p->Left->Cha = cha;
		}
		else // p->Left != NULL && p->Right != NULL => TH3: Node cần xóa là Node có đủ 2 con
		{
			TimPhanTuTheMang_DeQuy(Root->Left, p, Root);
		}

		free(p); // giải phóng p
	}
}

void XoaTatCaCacNodeGiaiPhongCay_DeQuy(NODE *&Root)
{

	if (Root == NULL)
		return;

	XoaNodeTrongCay_DeQuy(Root, Root->Data);

	XoaTatCaCacNodeGiaiPhongCay_DeQuy(Root);
}

void GiaiPhongCay_DeQuy(NODE *&Root)
{
	if (Root != NULL)
	{
		GiaiPhongCay_DeQuy(Root->Left);
		GiaiPhongCay_DeQuy(Root->Right);

		free(Root);
		Root = NULL; // Để sau hàm giải phóng nếu người dùng có thao tác gì đó với cây thì Root = NULL nên ko làm gì được nữa, tránh xảy ra lỗi ngang
	}
}

int main()
{
	int a[] = {40, 5, 35, 45, 15, 56, 35, 35, 35, 48, 13, 16, 49, 47};
	int n = sizeof(a) / sizeof(a[0]);

	NODE *Root;
	INit(Root);
	TaoCayTuDaySo(Root, a, n);

	printf("\nNLR: ");
	NLR(Root);

	printf("\nLNR: ");
	LNR(Root);

	printf("\nLRN: ");
	LRN(Root);

	/*XoaNodeTrongCay_DeQuy(Root, 40);
	XoaTatCaCacNodeGiaiPhongCay_DeQuy(Root);*/

	printf("\nDuyet rong: ");

	DuyetTheoChieuRong(Root, 2);

	/*printf("\nNLR: ");
	NLR(Root);

	printf("\nLNR: ");
	LNR(Root);

	printf("\nLRN: ");
	LRN(Root);
	
	printf("\nXoa tat ca cac Node => giai phong cay");
	XoaTatCaCacNodeGiaiPhongCay_DeQuy(Root);*/

	int x = 17;

	NODE *p = TimKiemNode_DeQuy(Root, x, Root);

	if(p->Data != x)
		printf("\nKhong tim thay node trong cay co gia tri la: %d", x);
	else
		printf("\nDa tim thay node trong cay co gia tri la: %d", p->Data);

	printf("\nLNR: ");
	LNR(Root);
	XoaTatCaCacNodeGiaiPhongCay_DeQuy(Root);

	_getch();
	return 0;
}