数据结构二叉树的程序设计
设计一个程序至少要包含以下算法
二叉树的创建算法、二叉树的遍历算法（主要是非递归德三种算法）、二叉树线索化算法、二叉排序树的创建算法、二叉排序树节点增加的算法、二叉排序树节点删除的算法、哈夫曼编码
有哪位高手能弄出来的话高分追加
1楼的能麻烦改成C的吗？
我用的是.c文件，直接用VC打开，老师要求的
能弄吗？可以追加100分以上的，谢谢
先说明我定的是C++程序
先实现二叉树的，把以下代码复制粘贴即可
#include <iostream>
using namespace std;
//****Lqueue.h
#define MAXQSIZE 100
typedef int Status;
template <class QElemType>
class Lqueue
{
public:
void InitQueue();
void DestroyQueue();
void ClearQueue();
Status QueueEmpty();
Status QueueLength();
void GetHead(QElemType & e);
void EnQueue(QElemType e);
void DeQueue(QElemType & e);
private:
struct SqQueue
{
QElemType * base;
int front;
int rear;
};
SqQueue Q;
};
//********Lqueue.cpp********
template <class QElemType>
void Lqueue<QElemType>::InitQueue()
{
Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
if(!Q.base) exit(0);
Q.front = Q.rear = 0;
}
template <class QElemType>
void Lqueue<QElemType>::DestroyQueue()
{
free(Q.base);
}
template <class QElemType>
void Lqueue<QElemType>::ClearQueue()
{
Q.front = Q.rear = 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueEmpty()
{
if(Q.front == Q.rear) return 1;
return 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueLength()
{
return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
}
template <class QElemType>
void Lqueue<QElemType>::GetHead(QElemType & e)
{
if(Q.front == Q.rear) e = NULL;
else
{
e = Q.base[Q.front];
}
}
template <class QElemType>
void Lqueue<QElemType>::EnQueue(QElemType e)
{
if((Q.rear + 1)%MAXQSIZE == Q.front) cout << "ERROR" << endl;
else
{
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1)%MAXQSIZE;
}
}
template <class QElemType>
void Lqueue<QElemType>::DeQueue(QElemType & e)
{
if(Q.front == Q.rear) cout << "ERROR" << endl;
else
{
e = Q.base[Q.front];
Q.front = (Q.front + 1)%MAXQSIZE;
}
}
//******************Lqueue.cpp***************
//*****stack.h
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
template<class QElemType>
class stack
{
public:
void InitStack();
void DestroyStack();
void ClearStack();
Status StackEmpty();
Status StackLength();
void GetTop(QElemType & e);
void Push(QElemType e);
void Pop(QElemType & e);
private:
struct SqStack{
QElemType *base;
QElemType *top;
int stacksize;
}S;
};
//******stack.cpp------
template<class QElemType>
void stack<QElemType>::InitStack()
{
S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
template <class QElemType>
void stack<QElemType>::DestroyStack()
{
free(S.base);
}
template <class QElemType>
void stack<QElemType>::ClearStack()
{
S.top = S.base;
}
template <class QElemType>
Status stack<QElemType>::StackEmpty()
{
if(S.top == S.base) return 1;
else return 0;
}
template <class QElemType>
Status stack<QElemType>::StackLength()
{
return (S.top - S.base);
}
template <class QElemType>
void stack<QElemType>::GetTop(QElemType & e)
{
if(S.top != S.base)
e = *(S.top - 1);
else e = NULL;
}
template <class QElemType>
void stack<QElemType>::Push(QElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
template <class QElemType>
void stack<QElemType>::Pop(QElemType & e)
{
if(S.top == S.base) e = NULL;
else
e = * --S.top;
}
//**********stack.cpp
//****************BiTree.h
template <class TElemType>
struct BiTNode{
TElemType data;
BiTNode<TElemType> *lchild,*rchild;
};
template <class TElemType>
class BiTree
{
public:
void CreateBiTree(BiTNode<TElemType> *&T);
void CreateBiTree();
void PreOrderTraverse(BiTNode<TElemType> *T);
void PreOrderTraverse();
void InOrderTraverse(BiTNode<TElemType> *T);
void InOrderTraverse();
void PostOrderTraverse(BiTNode<TElemType> *T);
void PostOrderTraverse();
void LevelOrderTraverse();
private:
BiTNode<TElemType> *T;
};
template <class TElemType>
void BiTree<TElemType>::CreateBiTree(BiTNode<TElemType> *&T)
{
TElemType ch;
cin >> ch;
if(sizeof(ch) == 1 && ch == '0') T = NULL;
else if(ch == -1) T = NULL;
else
{
if(!(T = (BiTNode<TElemType> *)malloc(sizeof(BiTNode<TElemType>)))) exit(0);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
template <class TElemType>
void BiTree<TElemType>::CreateBiTree()
{
CreateBiTree(T);
}
template <class TElemType>
//递归先序遍历
void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
cout << T->data << " ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
} //PreOrderTraverse
template <class TElemType>
void BiTree<TElemType>::PreOrderTraverse()
{
PreOrderTraverse(T);
}
//非递归先序遍历
/*void BiTree<TElemType>::PreOrderTraverse()
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
cout << p->data << " ";
p = p->lchild;
}
else
{
S.Pop(p);
p = p->rchild;
}
}
S.DestroyStack();
} */
//递归中序遍历
template <class TElemType>
void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
}
template <class TElemType>
void BiTree<TElemType>::InOrderTraverse()
{
InOrderTraverse(T);
}
//非递归中序遍历
/*void BiTree<TElemType>::InOrderTraverse()
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
p = p->lchild;
}
else
{
S.Pop(p);
cout << p->data << " ";
p = p->rchild;
}
}
S.DestroyStack();
} */
//递归后序遍历
template <class TElemType>
void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << " ";
}
}
template <class TElemType>
void BiTree<TElemType>::PostOrderTraverse()
{
PostOrderTraverse(T);
}
//非递归后序遍历
/*void BiTree<TElemType>::PostOrderTraverse()
{
BiTNode<TElemType> * p = T;
BiTNode<TElemType> * q = NULL;
stack<BiTNode<TElemType> *> S;
S.InitStack();
S.Push(p);
p = p->lchild;
while(!S.StackEmpty())
{
if(p)
{S.Push(p);p = p->lchild;}
else
{
S.GetTop(p);
p = p->rchild;
if(!p)
{
S.Pop(p);
cout << p->data << " ";
S.GetTop(q);
while(q && p == q->rchild)
{
S.Pop(p);
cout << p->data << endl;
S.GetTop(q);
//if(q == NULL) break;
}
if(q)
{
S.GetTop(q);
p = q->rchild;
}
}
}
}
S.DestroyStack();
} */
//非递归层次遍历
template <class TElemType>
void BiTree<TElemType>::LevelOrderTraverse()
{
Lqueue<BiTNode<TElemType> *> que;
que.InitQueue();
if(T) que.EnQueue(T);
while(!que.QueueEmpty())
{
que.GetHead(T);
if(T->lchild) que.EnQueue(T->lchild);
if(T->rchild) que.EnQueue(T->rchild);
que.DeQueue(T);
cout << T->data << " ";
}
que.DestroyQueue();
}
//**************BiTree.h
int main()
{
BiTree<char> tree;
cout << "请按树的先序遍历输入数据(0表示空(字符型),-1表示空（实数型）):" << endl;
tree.CreateBiTree();
tree.InOrderTraverse();
tree.PreOrderTraverse();
tree.PostOrderTraverse();
tree.LevelOrderTraverse();
cout << endl;
return 0;
}
演示程序如图，结果中包含了各种遍历。此程序中输入的表示顶点的是字符。若要用一个数表示顶点，可在main()中把BiTree<char> tree;改成
BiTree<int> tree; 当然也可以改成float.
我实现的是模板类，可实例化各种类型。
再打开一个C++的窗口，把以下赫夫曼的代码粘贴进去即可。
#include <iostream>
#include <string.h>
#include <iomanip>
using namespace std;
struct Huffmantree
{
unsigned int weight;
unsigned int lchild,rchild,parent;
};
struct wch
{
char ch;
unsigned int weight;
};
void HuffmanCoding(Huffmantree *& HT,char **&htcode,wch *&w,int n);
void Select(Huffmantree * HT,int n,int &s1,int &s2);
void DestroyHuffman(Huffmantree *& HT,char **&htcode,wch *&w,int n);
int main()
{
Huffmantree *HT = NULL;
wch *w = NULL;
char **htcode = NULL;
int n;
cout << "输入字符个数:" << endl;
cin >> n;
HuffmanCoding(HT,htcode,w,n);
for(int i = 0;i < n;i ++)
cout << w[i].ch << " " << htcode[i] << endl;
DestroyHuffman(HT,htcode,w,n);
return 0;
}
void HuffmanCoding(Huffmantree *&HT,char **&htcode,wch *&w,int n)
{//n个结点的赫夫曼树有2n-1个结点
int i;
int start,p,q,s1,s2;
w = (wch *)malloc(n * sizeof(wch));
cout << "输入" << n << "个字符及其相应的权值" << endl;
for(i = 0;i < n;i ++)
cin >> w[i].ch >> w[i].weight;
//构造赫夫曼树
HT = (Huffmantree *)malloc((2*n-1) * sizeof(Huffmantree));
for(i = 0;i < n;i ++)
{
HT[i].weight = w[i].weight;
HT[i].lchild = 0,HT[i].rchild = 0;
HT[i].parent = 0;
}
for(;i < 2*n-1;i ++)
{
HT[i].weight = 0;
HT[i].lchild = 0,HT[i].rchild = 0;
HT[i].parent = 0;
}
for(i = n;i < 2*n-1;i ++)
{
Select(HT,i-1,s1,s2);
HT[i].lchild = s1,HT[i].rchild = s2;
HT[s1].parent = i,HT[s2].parent = i;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
//构造完成
htcode = (char **)malloc(n * sizeof(char *));
char *cd = (char *)malloc(n * sizeof(char));
cd[n-1] = '\0';
for(i = 0;i < n;i ++)
{
start = n-1;
for(p = i;HT[p].parent != 0;p = HT[p].parent)
{
q = HT[p].parent;
if(p == HT[q].lchild) cd[--start] = '0';
else cd[--start] = '1';
}
htcode[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(htcode[i],&cd[start]);
}
}
void Select(Huffmantree *HT,int n,int &s1,int &s2)
{
int i;
s1 = s2 = -1;
for(i = 0;i <= n;i ++)
{
if(HT[i].parent == 0 && s1 == -1)
s1 = i;
if(HT[i].parent == 0 && HT[i].weight < HT[s1].weight)
s1 = i;
}
for(i = 0;i <= n;i ++)
{
if(HT[i].parent == 0 && s2 == -1 && i != s1)
s2 = i;
if(HT[i].parent == 0 && HT[i].weight < HT[s2].weight && s1 != i) //此处易出错,漏掉s1 != i
s2 = i;
}
}
void DestroyHuffman(Huffmantree *&HT,char **&htcode,wch *&w,int n)
{
free(HT);
free(w);
for(int i = 0;i < n;i ++)
free(htcode[i]);
free(htcode);
}
