PDA

View Full Version : [Q] Mí wuynh ui...



thodinh
28-06-2003, 13:49
Mi' wuynh ơi, mấy hàm sau bị báo lỗi là "Function should return a value", có cách nào khắc phục lỗi này không,níu có thì chỉ đệ dzới (các hàm này chạy vẫn đúng), cảm ơn mí wuynh trước nhoa.

//Ham hieu chinh node cho AVL_Tree
AVLTREE_NODE *AdjustNode(AVLTREE_NODE *&pCurRoot)
{
AVLTREE_NODE *p;
if (HeightOfNode(pCurRoot->pLeft)==HeightOfNode(pCurRoot->pRight)+2)
{
p=pCurRoot->pLeft;
if (HeightOfNode(p->pLeft)==HeightOfNode(p->pRight))
{
pCurRoot->pLeft=p->pRight;
p->pRight=pCurRoot;
pCurRoot->nBal=-1;
p->nBal=1;
return p;
}
else if (HeightOfNode(p->pLeft)==HeightOfNode(p->pRight)+1)
{
pCurRoot->pLeft=p->pRight;
p->pRight=pCurRoot;
pCurRoot->nBal=0;
p->nBal=0;
return p;
}
else if (HeightOfNode(p->pLeft)==HeightOfNode(p->pRight)-1)
{
AVLTREE_NODE *p1;
p1=p->pRight;
p->pRight=p1->pLeft;
pCurRoot->pLeft=p1->pRight;
p1->pLeft=p;
p1->pRight=pCurRoot;
switch (p1->nBal)
{
case 0:
{
pCurRoot->nBal=0;
p->nBal=0;
}
break;
case 1:
{
pCurRoot->nBal=0;
p->nBal=-1;
}
break;
case -1:
{
pCurRoot->nBal=1;
p->nBal=0;
}
break;
}
p1->nBal=0;
return p1;
}
}
else
{
p=pCurRoot->pRight;
if (HeightOfNode(p->pRight)==HeightOfNode(p->pLeft))
{
pCurRoot->pRight=p->pLeft;
p->pLeft=pCurRoot;
pCurRoot->nBal=1;
p->nBal=-1;
return p;
}
else if (HeightOfNode(p->pRight)==HeightOfNode(p->pLeft)+1)
{
pCurRoot->pRight=p->pLeft;
p->pLeft=pCurRoot;
pCurRoot->nBal=0;
p->nBal=0;
return p;
}
else if (HeightOfNode(p->pRight)==HeightOfNode(p->pLeft)-1)
{
AVLTREE_NODE *p1;
p1=p->pLeft;
p->pLeft=p1->pRight;
pCurRoot->pRight=p1->pLeft;
p1->pRight=p;
p1->pLeft=pCurRoot;
switch (p1->nBal)
{
case 0:
{
pCurRoot->nBal=0;
p->nBal=0;
}
break;
case 1:
{
pCurRoot->nBal=-1;
p->nBal=0;
}
break;
case -1:
{
pCurRoot->nBal=0;
p->nBal=1;
}
break;
}
p1->nBal=0;
return p1;
}
}
}

//Ham them node cho AVL_Tree
int AVLTreeAdd(AVLTREE_NODE *&pCurRoot,int nKey)
{
if (pCurRoot==NULL)
{
pCurRoot=new(AVLTREE_NODE);
pCurRoot->pLeft=pCurRoot->pRight=NULL;
pCurRoot->nKey=nKey;
return 1;
}
else
{
if (pCurRoot->nKey==nKey) return 0;
if (pCurRoot->nKey>nKey)
AVLTreeAdd(pCurRoot->pLeft,nKey);
if (pCurRoot->nKey<nKey)
AVLTreeAdd(pCurRoot->pRight,nKey);
}
int nHL,nHR;
nHL=HeightOfNode(pCurRoot->pLeft);
nHR=HeightOfNode(pCurRoot->pRight);
if (nHL==nHR) pCurRoot->nBal=0;
else if (nHL==nHR+1) pCurRoot->nBal=-1;
else if (nHL==nHR-1) pCurRoot->nBal=1;
else pCurRoot=AdjustNode(pCurRoot);
}

//Ham tim node thay the cho node can xoa
AVLTREE_NODE *SearchStandFor(AVLTREE_NODE *pCurRoot,AVLTREE_NODE *&pStandFor)
{
if (pStandFor->pRight!=NULL)
SearchStandFor(pCurRoot,pStandFor->pRight);
else
{
pCurRoot->nKey=pStandFor->nKey;
AVLTREE_NODE *pTemp;
pTemp=pStandFor;
pStandFor=pStandFor->pLeft;
return pTemp;
}
}

//Ham xoa node co khoa la nKey trong AVL_Tree
int AVLTreeDelete(AVLTREE_NODE *&pCurRoot,int nKey)
{
if (pCurRoot==NULL) return 0;
if (pCurRoot->nKey>nKey)
AVLTreeDelete(pCurRoot->pLeft,nKey);
else if (pCurRoot->nKey<nKey)
AVLTreeDelete(pCurRoot->pRight,nKey);
else
{
AVLTREE_NODE *pTemp;
pTemp=pCurRoot;
if (pCurRoot->pLeft==NULL) pCurRoot=pCurRoot->pRight;
else if (pCurRoot->pRight==NULL) pCurRoot=pCurRoot->pLeft;
else pTemp=SearchStandFor(pCurRoot,pCurRoot->pLeft);
delete pTemp;
int nHL,nHR;
nHL=HeightOfNode(pCurRoot->pLeft);
nHR=HeightOfNode(pCurRoot->pRight);
if (nHL==nHR) pCurRoot->nBal=0;
else if (nHL==nHR+1) pCurRoot->nBal=-1;
else if (nHL==nHR-1) pCurRoot->nBal=1;
else pCurRoot=AdjustNode(pCurRoot);
return 1;
}
}

thodinh
28-06-2003, 13:51
Xin lỗi mí wuynh nha, khi copy rồi dán qua thì nó bị nhảy tùm lum dzị á :rolleyes:

mastertek
28-06-2003, 23:03
NHÌN MÙ LUÔN:):):):):)

Boy4is
29-06-2003, 01:10
Thì phải thêm làm shao cho nó trả về 1 giá trị là được rồi, ví dụ thiêm vào cuối câu lệnh 'return NULL' chắc là được

thodinh
01-07-2003, 18:26
Chòi , hàm ngừ ta trả dzìa con trỏ mà wuynh bỉu trả dzìa NULL thì còn gì là hàm của tui :rolleyes:

Boy4is
02-07-2003, 00:36
Hổng phải vậy ... :-) Vì có thể trong hàm của bác có xét thiêm các điều kiện và chỉ trả về khi thoả các điều kiện này, khi đó compiler sẽ warning là "... not all paths return value ...", nếu bác setting những warning dạng này đều là Error hết (coi lại phần option setting) thì sẽ bị báo lỗi, do đó bác thêm đại 1 cái 'return NULL' ở cuối cho C++ nó 'lầm tưởng' là luôn luôn có trả về để nó câm họng lại ... Trừ phi có gì sai khác thì cách của tui là đúng rùi !

thodinh
04-07-2003, 09:21
nhưng mà đây là hàm đệ quy mò, đâu có làm dzị được :rolleyes:

Boy4is
06-07-2003, 17:03
Ôi trời ơi .. em trả lời vậy mà bác chưa hài lòng sao ? :-) .. ý em là chỉ thêm vô vậy thôi chứ có làm gì đâu ! Nếu thật sự chương trình mà chạy đến câu lệnh đó thì rõ ràng bác đã viết sai đâu đó rồi (lỗi logic) ... bác thử đi xem nào, với lại lỗi nó báo ra sao thì post lên thì các bác khác mới giúp được chứ ! Mà bác xem lại thử chỗ gọi đệ qui có return chưa ? 'return <Recursive Function>'

haison3000
06-07-2003, 22:49
Bac de cai ham return lai gia tri la con tro la khong dung. Vi sau khi function ket thuc vung nhho chua con tro se bi xoa sach nen luc nay gia tri cua con tro la vo dinh.
BAc nen them 1 cai new(*p) ( dynamic allocated memory) trong function roi hay tra gia tri con tro nay ve.

thodinh
08-07-2003, 22:02
To Boy4is: xin lũi wuynh nhoa, đó chi 3 là warning thui, không phải là error, hàm của tui vẫn chạy đúng, tui chi 3 muốn khử cái waring đó thui.Dù seo thì cũng cảm ơn wuynh đã quan tâm giúp đỡ, thanks.
To haison: vậy sao, nhưng mà mấy hàm tìm kiếm tui đâu cần phải new(*p) đâu :rolleyes: .Okie, dù seo thì tui cũng dzìa thử coi.Thanks nha

thodinh
08-07-2003, 22:13
Nhân tiện cho đệ hỏi mí wuynh thuật toán xóa cây nhị phân luôn nhoa. Bữa trước có wuynh nào post lên nhưng đem dzìa nhà đệ coi thử thấy kì wá,hông đúng :rolleyes: . Mí wuynh trả lời sớm cho đệ nhoa, gần thi gòi.Xin cảm ơn trước.

Boy4is
09-07-2003, 23:41
Nhân tiện cho đệ hỏi mí wuynh thuật toán xóa cây nhị phân luôn nhoa. Bữa trước có wuynh nào post lên nhưng đem dzìa nhà đệ coi thử thấy kì wá,hông đúng :rolleyes: . Mí wuynh trả lời sớm cho đệ nhoa, gần thi gòi.Xin cảm ơn trước.

Tặng bác thêm cây AVL luôn :)

Boy4is
09-07-2003, 23:45
Ua sao Attach hông duoc ? 8K thôi mà ?????????

thodinh
11-07-2003, 09:02
ôin chời, tui chỉ xin thuật toán xóa cây nhị phân thui mà, đâu cần phải đưa hết cho cho mất công,post thuật toán đó thui wuynh ui okie?. :helpsmili

Boy4is
11-07-2003, 10:20
Tui viết nhưng quăng tùm lum à : Coi rồi sửa sang lại nhá :
#ifndef _NODE_H_
#define _NODE_H_

#include <iostream.h>

typedef int BalanceFactor;
typedef int ErrorCode;

#define FAIL 0
#define SUCCESS 1
#define DUPLICATE 2

#define LEFT_HIGHER -1
#define EQUAL_HEIGHT 0
#define RIGHT_HIGHER 1

#define INFINITY 65535
#define INCREASE 0
#define DECREASE 1
#define NULL 0


template <class NodeEntry>
class CNode
{
public:
CNode()
{
left = NULL;
right = NULL;
}
CNode(const NodeEntry &data)
{
left = NULL;
right = NULL;
entry = data;
}
virtual ~CNode()
{
left = NULL;
right = NULL;
}
public:
virtual void SetBalance(BalanceFactor b)
{
}
virtual BalanceFactor GetBalance() const
{
return EQUAL_HEIGHT;
}
public:
CNode<NodeEntry> *left;
CNode<NodeEntry> *right;
NodeEntry entry;
};

template<class NodeEntry>
class CAVLNode : public CNode<NodeEntry>
{
public:
CAVLNode():balance(EQUAL_HEIGHT) {}
CAVLNode(const NodeEntry &x):CNode<NodeEntry>(x)
{
balance = EQUAL_HEIGHT;
}
virtual ~CAVLNode() {};
public:
void SetBalance(BalanceFactor b)
{
balance = b;
}
BalanceFactor GetBalance() const
{
return balance;
}
protected:
BalanceFactor balance;
};

template <class NodeEntry,int Size>
class CTrieNode
{
public:
NodeEntry *data;
CTrieNode *branch[Size];
CTrieNode()
{
data = NULL;
for (int i = 0;i < Size;i++)
branch[i] = NULL;
}
};

#endif
// BTree.h: interface for the CBTree class.
//////////////////////////////////////////////////////////////////////
#ifndef _TREE_H_
#define _TREE_H_

#include "Node.h"

template <class NodeEntry>
class CBTree
{
protected:
CNode<NodeEntry>* root;
public:
CBTree()
{
root = NULL;
}
//Copy constructor : alloc new tree
CBTree(CBTree<NodeEntry>& tree)
{
root = NULL;
*this = tree;
}
CBTree(CNode<NodeEntry>* node)
{
root = node;
}
virtual ~CBTree()
{
Recursive_Clear(root);
}
public:
//Reverse all (left <=> right) and (right <=> left) branches
void ReverseLeftRight()
{
Recursive_ReverseLeftRight(root);
}
//Search a key, return the pointer to if found, else return NULL
CNode<NodeEntry>* Search(const NodeEntry& key)
{
return Recursive_FindKey(root,key);
}
//Assignment operator
CBTree<NodeEntry>& operator = (const CBTree<NodeEntry>& tree)
{
if (this->root != tree.root)
Recursive_CopyTree(root,tree.root);
return *this;
}
//Is a Binary Search Tree...
bool IsABSTree()
{
int min = 0,max = 0;
return Recursive_IsABSTree(root,min,max);
}
//Visit node
static void VisitNode(NodeEntry& data)
{
cout << data << " " << flush;
}
//Compare all of keys between two trees
bool operator == (CBTree& tree)
{
if (this->root == tree.root) return true;
return Recursive_Compare(root,tree.root);
}
//Return 'True' if this tree is empty
bool Empty()
{
return (root == NULL);
}
//Return Width of this tree
int Width()
{
int Width = 0;
for (int degree = 0;degree < Height();degree++)
{
int nSize = 0;
Recursive_DegreeOrder(root,degree,NULL,nSize);
if (nSize > Width) Width = nSize;
}
return Width;
}
//Insert a node with following method:
// + If root == NULL ==> Make it as root
// + If height of the LeftTree <= height of the RightTree ==> Insert Left
// + Else Insert Right...
//Return TRUE if success.
bool Insert(const NodeEntry& data)
{
return Recursive_InsertNode(data,root);
}
void InOrder(void (*visit)(NodeEntry &))
{
Recursive_InOrder(root,visit);
}
void PreOrder(void (*visit)(NodeEntry &))
{
Recursive_PreOrder(root,visit);
}
void PostOrder(void (*visit)(NodeEntry &))
{
Recursive_PostOrder(root,visit);
}
//Traversal over the tree with method : increase level(degree)
void DegreeOrder(void (*visit)(NodeEntry &))
{
for (int degree = 0;degree < Height();degree++)
{
int Width = 0;
cout << "Level " << degree << " : ";
Recursive_DegreeOrder(root,degree,visit,Width);
cout << " ==> So nut : " << Width << endl;
}
}
//Return number of leaves of this tree
int NumOfLeaves()
{
return Recursive_NumOfLeaves(root);
}
//Return the height of this tree
int Height()
{
return Recursive_Height(root);
}
//Return number of nodes of this tree
int Size()
{
return Recursive_NumOfNodes(root);
}
//Clear the tree
void Clear()
{
Recursive_Clear(root);
}
//Remove all nodes from tree in level 'degree'
bool RemoveNodeFollowLevel(int degree)
{
return Recursive_RemoveNodeFollowLevel(root,degree);
}
//Remove node from key target
bool RemoveNodeFollowKey(const NodeEntry& key)
{
return Recursive_RemoveNodeFollowKey(root,key);
}
//Heap Sort
void HeapSort(bool flag = INCREASE)
{
}
void Draw(int xo)
{
for (int degree = 0;degree < Height();degree++)
{
Recursive_Print(root,xo,xo,degree);
}
}
protected:
void PrintNode(CNode<NodeEntry>* node,int xo)
{
char fillchar = '-';
for (int i = 0;i < xo-1;i++)
cout << fillchar << flush;
cout << "[" << node->entry << "]" << endl;
}
void Recursive_Print(CNode<NodeEntry> *sub_root,int xo,int dx,int degree)
{
if (sub_root == NULL) return;
if (degree == 0)
{
PrintNode(sub_root,xo);
return;
}
Recursive_Print(sub_root->left,xo-dx/2,dx/2,degree-1);
Recursive_Print(sub_root->right,xo+dx/2,dx/2,degree-1);
}
bool RemoveNode(CNode<NodeEntry>*& sub_root)
{
if (sub_root == NULL) return false;
CNode<NodeEntry> *temp_node = sub_root;
if (sub_root->right == NULL)
sub_root = sub_root->left;
else if (sub_root->left == NULL)
sub_root = sub_root->right;
else
{
CNode<NodeEntry> *parent = sub_root;
CNode<NodeEntry> *rightmost = sub_root->left;

//Get right-most node
while (rightmost->right != NULL)
{
parent = rightmost;
rightmost = rightmost->right;
}
sub_root->entry = rightmost->entry;
if (parent == sub_root)
parent->left = rightmost->left;
else parent->right = rightmost->left;
temp_node = rightmost;
}
delete temp_node;
return true;
}
virtual bool Recursive_RemoveNodeFollowKey(CNode<NodeEntry>*& sub_root,const NodeEntry& key)
{
if (sub_root == NULL) return true;
if (sub_root->entry == key) return RemoveNode(sub_root);
bool leftOK = Recursive_RemoveNodeFollowKey(sub_root->left,key);
if (!leftOK)
return Recursive_RemoveNodeFollowKey(sub_root->right,key);
return leftOK;
}
bool Recursive_RemoveNodeFollowLevel(CNode<NodeEntry>*& sub_root,int degree)
{
if (sub_root == NULL) return true;
if (degree == 0) return RemoveNode(sub_root);
else
{
return (Recursive_RemoveNodeFollowLevel(sub_root->left,degree-1)&&
Recursive_RemoveNodeFollowLevel(sub_root->right,degree-1));
}
}
void Recursive_DegreeOrder(CNode<NodeEntry>* sub_root,int degree,void (*visit)(NodeEntry &),int& nWidth)
{
if (sub_root == NULL) return;
if (degree == 0)
{
if (visit != NULL)
(*visit)(sub_root->entry);
nWidth++;
return;
}
Recursive_DegreeOrder(sub_root->left,degree-1,visit,nWidth);
Recursive_DegreeOrder(sub_root->right,degree-1,visit,nWidth);
}
bool Recursive_Compare(const CNode<NodeEntry>* sub_root,const CNode<NodeEntry>* source)
{
if ((sub_root == NULL&&source != NULL)||
(sub_root != NULL&&source == NULL)) return false;
if (sub_root != NULL&&source != NULL)
{
return (Recursive_Compare(sub_root->left,source->left)
&&Recursive_Compare(sub_root->right,source->right)
&&sub_root->entry == source->entry);
}
return true;
}
virtual bool Recursive_InsertNode(const NodeEntry& data,CNode<NodeEntry>*& sub_root)
{
if (sub_root == NULL)
{
sub_root = new CNode<NodeEntry>(data);
if (sub_root != NULL) return true;
return false;
}
int nLeftHeight = Recursive_Height(sub_root->left);
int nRightHeight = Recursive_Height(sub_root->right);
if (nLeftHeight <= nRightHeight)
return Recursive_InsertNode(data,sub_root->left);
else return Recursive_InsertNode(data,sub_root->right);
}
void Recursive_Clear(CNode<NodeEntry>*& sub_root)
{
if (sub_root)
{
Recursive_Clear(sub_root->left);
Recursive_Clear(sub_root->right);
/* Debug only */
//cout << "\nXoa khoa : " << sub_root->entry << flush;
/**/
delete sub_root;
sub_root = NULL;
}
}
void Recursive_InOrder(CNode<NodeEntry> *sub_root,void (*visit)(NodeEntry &))
{
if (sub_root == NULL) return;
Recursive_InOrder(sub_root->left,visit);
(*visit)(sub_root->entry);
Recursive_InOrder(sub_root->right,visit);
}
void Recursive_PreOrder(CNode<NodeEntry> *sub_root,void (*visit)(NodeEntry &))
{
if (sub_root == NULL) return;
(*visit)(sub_root->entry);
Recursive_PreOrder(sub_root->left,visit);
Recursive_PreOrder(sub_root->right,visit);
}
void Recursive_PostOrder(CNode<NodeEntry> *sub_root,void (*visit)(NodeEntry &))
{
if (sub_root == NULL) return;
Recursive_PostOrder(sub_root->left,visit);
Recursive_PostOrder(sub_root->right,visit);
(*visit)(sub_root->entry);
}
int Recursive_NumOfLeaves(const CNode<NodeEntry> *sub_root)
{
if (sub_root != NULL)
{
if (sub_root->left == sub_root->right)
return 1;
return Recursive_NumOfLeaves(sub_root->left)
+Recursive_NumOfLeaves(sub_root->right);
}
return 0;
}
int Recursive_NumOfNodes(const CNode<NodeEntry> *sub_root)
{
if (sub_root == NULL)
return 0;
return Recursive_NumOfNodes(sub_root->left)
+Recursive_NumOfNodes(sub_root->right)+1;
}
int Recursive_Height(const CNode<NodeEntry> *sub_root)
{
if (sub_root == NULL)
return 0;
int nBranchLeft = Recursive_Height(sub_root->left)+1;
int nBranchRight = Recursive_Height(sub_root->right)+1;
return (nBranchLeft>nBranchRight)?nBranchLeft:nBranchRight;
}
//Call by Assignment operator method
void Recursive_CopyTree(CNode<NodeEntry>*& sub_root,const CNode<NodeEntry>* source)
{
if (source == NULL)
{
if (sub_root != NULL)
Recursive_Clear(sub_root);
return;
}
if (sub_root != NULL)
sub_root->entry = source->entry;
else
sub_root = new CNode<NodeEntry>(source->entry);
Recursive_CopyTree(sub_root->left,source->left);
Recursive_CopyTree(sub_root->right,source->right);
}
//Return TRUE if this is a Binary Search Tree
bool Recursive_IsABSTree(const CNode<NodeEntry>* sub_root,int& nMin,int& nMax)
{
if (sub_root == NULL)
return true;
if (sub_root->left == sub_root->right) /* == NULL */
{
nMin = (nMin < sub_root->entry)?nMin:sub_root->entry;
nMax = (nMax > sub_root->entry)?nMax:sub_root->entry;
return true;
}
nMax = -INFINITY;
bool leftOK = Recursive_IsABSTree(sub_root->left,nMin,nMax);
if (leftOK&&sub_root->entry > nMax)
{
nMin = INFINITY;
bool rightOK = Recursive_IsABSTree(sub_root->right,nMin,nMax);
return rightOK&&sub_root->entry < nMin;
}
return false;
}
//Call by Search
virtual CNode<NodeEntry>* Recursive_FindKey(CNode<NodeEntry>* sub_root,const NodeEntry& key)
{
if (sub_root == NULL)
return NULL;
if (sub_root->entry == key)
return sub_root;
CNode<NodeEntry> *node = Recursive_FindKey(sub_root->left,key);
if (node == NULL)
return Recursive_FindKey(sub_root->right,key);
else return node;
}
//Reverse all (left <=> right) and (right <=> left) branches
void Recursive_ReverseLeftRight(CNode<NodeEntry>*& sub_root)
{
if (sub_root == NULL)
return;
Recursive_ReverseLeftRight(sub_root->left);
Recursive_ReverseLeftRight(sub_root->right);
CNode<NodeEntry>* temp_node = sub_root->left;
sub_root->left = sub_root->right;
sub_root->right = temp_node;
}
};

#endif

thodinh
11-07-2003, 10:49
Thanks nha, để tui đem dzìa coi thử :)