ltbaogt
Tổng số bài gửi : 18 Join date : 01/01/2010
| Tiêu đề: Cay Nhi Phan Tk Mon Apr 19, 2010 4:38 pm | |
| - Code:
-
#include "stdio.h" struct NODE{ int Key; NODE *pLeft; NODE *pRight; }; typedef NODE node; void Init(node *&tree) { tree = NULL; } node *taonode(int x) { node *pnode=new node; if(pnode==NULL) { printf("Khong du bo nho "); } else { pnode->Key=x; pnode->pLeft=NULL; pnode->pRight=NULL; } return pnode; }
void Insert ( node *&proot, int x) { if (proot == NULL) { node *q; q = new node; q->Key = x; q->pLeft = q->pRight = NULL; proot = q; } else { if (x < proot->Key) Insert (proot->pLeft, x); else if (x > proot->Key) Insert (proot->pRight, x); } } void CreateTree(NODE *&pRoot) { int Data; do{ printf("Nhap vao du lieu, -1 de ket thuc: "); scanf("%d", &Data); if (Data == -1) break; Insert(pRoot, Data); } while(1); } int NLR(NODE* pTree,int &s) {
if(pTree != NULL) { s=s+pTree->Key; NLR(pTree->pLeft,s); NLR(pTree->pRight,s); } return s;
} int sn(NODE* pTree,int &s) {
if(pTree != NULL) { s++; sn(pTree->pLeft,s); sn(pTree->pRight,s); } return s;
} NODE* Search(NODE* pRoot, int x) { if(pRoot == NULL) return NULL; if(x < pRoot->Key) Search(pRoot->pLeft, x); else if(x > pRoot->Key) Search(pRoot->pRight, x); else { //Ghi chú: Trong tr..ng h.p nào dòng bên d..i d..c th.c hien? return pRoot; } } int Height(NODE* pNode) { if(pNode == NULL) return 0; int HL, HR; HL = Height(pNode->pLeft); HR = Height(pNode->pRight); if(HL > HR) return (1 + HL); return (1 + HR); } void SearchStandFor(NODE* &Tree, NODE* &q) { if (Tree->pRight) SearchStandFor(Tree->pRight,q); else { q->Key = Tree->Key; q = Tree; Tree = Tree->pLeft; } } void RemoveNode(NODE* &Tree, int x) { NODE* p; if(Tree == NULL) printf("%d khong co trong cay", x); else { if (x < Tree->Key) RemoveNode(Tree->pLeft,x); else if (x > Tree->Key) RemoveNode(Tree->pRight,x); else { //Ghi chú: M c dích phép gán này là gì? p = Tree; if(p->pRight == NULL) Tree = p->pLeft; else if (p->pLeft == NULL) Tree = p->pRight; else { //Ghi chú: Hàm bên d..i dùng de làm gì? SearchStandFor(Tree->pLeft,p); } delete p; } } } void main() { NODE* pTree, *p; int x; Init(pTree); CreateTree(pTree); int s=0; int t= NLR(pTree,s); printf("%d\n",s); int dem=0; int count=sn(pTree,dem); printf("so luong nu la: %d\n",count); printf("Nhap vao 1 gia tri de tim: "); scanf("%d", &x); p = Search(pTree, x); if(p != NULL) { printf ("%d co xuat hien trong cay.\n", x); printf("Chieu cao cua nut %d la %d\n", x, Height(p)); RemoveNode(pTree, x); } else { printf("%d khong co trong cay.\n", x); } } | |
|