Duyệt cây nhị phân không đệ quy

#1

Chả là thầy e có giao bài tập thực hành về duyệt cây nhị phân không đệ quy ( ) và còn 1 vấn đề nữa về con trỏ 2 chiều vấn đề là ntn ạ ( em khai báo 1 con trỏ Tree ntn Tree *tree, tree là con trỏ 2 chiều cho em hỏi 1 tí về công dụng của nó ạ, liệu nó có thể trỏ tới 1 thằng bất kỳ trong (1 cái tree khác cùng kiểu dữ liệu và
tree->left và tree->right liệu nó có hiểu được không ạ) || hay là có từ khóa nào có thể giúp chỉ tới 1 vị trí và có khả năng như vị trí nó vừa chỉ vào không ạ!! Em cảm ơn trước ạ :smiley:.

#2

Không hiểu câu hỏi của bạn lắm Bạn hỏi bản chất của Node hay của 1 Tree?

1 Like
#3

bản chất của node em hiểu rồi ạ 1 tree em cũng hiểu rùi ạ em chỉ không biết làm thế nào để duyệt cây nhị phân không đệ quy thôi ạ @@!

#4


bạn có thể tham khảo thêm video này!

#5

vâng ạ bạn có thể cho mình hỏi đoạn code này tại sao nó không chạy vào Empty(stack) k.

#include<stdio.h>
#include<conio.h>
#include<iostream>

typedef struct Node {
	int data;
	struct Node *pleft;
	struct Node *pright;
} NODE;

typedef struct Stack {
	NODE *top;
} STACK;

typedef NODE* Tree;

void khoitao(STACK &stack, Tree &tree) {
	stack.top = NULL;
	tree = NULL;
}

NODE* getNode(int &x) {
	NODE* p = new NODE;
	if (p == NULL) {
		return NULL;
	}
	else {
		p->data = x;
		p->pleft = NULL;
		p->pright = NULL;
		return p;
	}
}

int isEmpty(STACK &stack) {
	return stack.top == NULL;
}

int isEmptyTree(Tree &tree) {
	return tree == NULL;
}

void Push(STACK &stack, NODE *p) {
	if (stack.top == NULL) {
		stack.top = p;
	}
	else {
		p->pright = stack.top;
		stack.top->pleft = p->pleft;
		stack.top = p;
	}
}

void Pop(STACK &stack) {
	int x;
	if (isEmpty(stack)) {
		return;
	}
	else {
		NODE* p = stack.top;
		x = p->data;
		printf("%d ", x);
		stack.top = p->pright;
		delete p;
	}
}

void addTree(Tree &tree, int &x) {
	NODE* p = getNode(x);
	if (isEmptyTree(tree)) {
		NODE* p = getNode(x);
		tree = p;
	}
	else {
		if (tree->data > x) {
			addTree(tree->pleft, x);
		}
		else if (tree->data < x) {
			addTree(tree->pright, x);
		}
	}
}

void DuyetCayDeQuy(Tree &tree) {
	if (isEmptyTree(tree)) {
		return;
	}
	else {
		printf("%d ", tree->data);
		DuyetCayDeQuy(tree->pleft);
		DuyetCayDeQuy(tree->pright);
	}
}

void DuyetCayKhongDeQuy(Tree &tree) {
	STACK stack;
	NODE *p;

	Push(stack, tree);
	while (!isEmpty(stack)) {
		p = stack.top;
		Pop(stack);
		if (p->pright != NULL) {
			Push(stack, p->pright);
		}
		if (p->pleft != NULL) {
			Push(stack, p->pleft);
		}
	}
}


/*
void Nhap(STACK &stack){
NODE* p;
int x;
for(int i = 0 ; i < 5; i++){
scanf("%d",&x);
p = getNode(x);
Push(stack,p);
}
while(!isEmpty(stack)){
Pop(stack);
}
}
*/

int main() {
	Tree tree;
	Stack stack;
	khoitao(stack, tree);

	int luachon, x;
	do {
		printf("\nNhap 2 de duyet cay NLR\nNhap 1 de them.\nNhap 0 de thoat.\n");
		printf("\nMoi nhap lua chon cua ban.\n");
		scanf_s("%d", &luachon);
		switch (luachon) {
		case 1: {
			printf("\nMoi ban nhap so can chen: ");
			scanf_s("%d", &x);
			printf("\n");
			addTree(tree, x);
			break;
		}
		case 2: {
			DuyetCayKhongDeQuy(tree);
			break;
		}
		}
	} while (luachon != 0);


	system("pause");
	return 0;
}
#6

Bạn có thể markdown lại code giúp mình được ko :smiley:
Khá đơn giản thôi:

1/ Tách đoạn code thành 1 đoạn riêng với văn bản
2/ Bôi đen
3/ Nhấn Ctrl + Shiflt + C

2 Likes
#7

Mình không biết tại sao :slight_smile:

#8 
#include<stdio.h>
#include<conio.h>
#include<iostream>

typedef struct Node {
	int data;
	struct Node *pleft;
	struct Node *pright;
} NODE;

typedef struct Stack {
	NODE *top;
} STACK;

typedef NODE* Tree;

void khoitao(STACK &stack, Tree &tree) {
	stack.top = NULL;
	tree = NULL;
}

NODE* getNode(int &x) {
	NODE* p = new NODE;
	if (p == NULL) {
		return NULL;
	}
	else {
		p->data = x;
		p->pleft = NULL;
		p->pright = NULL;
		return p;
	}
}

int isEmpty(STACK &stack) {
	return stack.top == NULL;
}

int isEmptyTree(Tree &tree) {
	return tree == NULL;
}

void Push(STACK &stack, NODE *p) {
	if (isEmpty(stack)) {
		stack.top = p;
	}
	else {
		p->pright = stack.top;
		stack.top->pleft = p->pleft;
		stack.top = p;
	}
}

void Pop(STACK &stack) {
	int x;
	if (isEmpty(stack)) {
		return;
	}
	else {
		NODE* p = stack.top;
		x = p->data;
		printf("%d ", x);
		stack.top = p->pright;
		delete p;
	}
}

void addTree(Tree &tree, int &x) {
	NODE* p = getNode(x);
	if (isEmptyTree(tree)) {
		NODE* p = getNode(x);
		tree = p;
	}
	else {
		if (tree->data > x) {
			addTree(tree->pleft, x);
		}
		else if (tree->data < x) {
			addTree(tree->pright, x);
		}
	}
}

void DuyetCayDeQuy(Tree &tree) {
	if (isEmptyTree(tree)) {
		return;
	}
	else {
		printf("%d ", tree->data);
		DuyetCayDeQuy(tree->pleft);
		DuyetCayDeQuy(tree->pright);
	}
}

void DuyetCayKhongDeQuy(Tree &tree) {
	STACK stack;
	NODE *p;

	Push(stack, tree);
	while (!isEmpty(stack)) {
		p = stack.top;
		Pop(stack);
		if (p->pright != NULL) {
			Push(stack, p->pright);
		}
		if (p->pleft != NULL) {
			Push(stack, p->pleft);
		}
	}
}


/*
void Nhap(STACK &stack){
NODE* p;
int x;
for(int i = 0 ; i < 5; i++){
scanf("%d",&x);
p = getNode(x);
Push(stack,p);
}
while(!isEmpty(stack)){
Pop(stack);
}
}
*/

int main() {
	Tree tree;
	Stack stack;
	khoitao(stack, tree);

	int luachon, x;
	do {
		printf("\nNhap 2 de duyet cay NLR\nNhap 1 de them.\nNhap 0 de thoat.\n");
		printf("\nMoi nhap lua chon cua ban.\n");
		scanf_s("%d", &luachon);
		switch (luachon) {
		case 1: {
			printf("\nMoi ban nhap so can chen: ");
			scanf_s("%d", &x);
			printf("\n");
			addTree(tree, x);
			break;
		}
		case 2: {
			DuyetCayKhongDeQuy(tree);
			break;
		}
		}
	} while (luachon != 0);


	system("pause");
	return 0;
}
#9

đây ạ @@! giúp e với :smiley:

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