50分急求！！数据结构课程设计，c链表的基本操作和二叉树的几种遍历！！！！

急求数据结构课程设计：二叉树的遍历

#ifndef BinaryTree_H
#define BinaryTree_H

#include
#include

class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;

TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}

}TreeNode, *PTreeNode;

public:
enum TraverseType
{
PREORDER = 0, // 前序
INORDER = 1, // 中序
POSTORDER = 2, // 后序
LEVELORDER = 3 // 层序
};

BinaryTree(Item Array[], int nLength);
~BinaryTree();

PTreeNode GetRoot()
{
return m_pRoot;
}

// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void Traverse(TraverseType traversetype, bool bRec = true);

private:
PTreeNode CreateTreeImpl(Item Array[], int nLength);
void DetroyTreeImpl(PTreeNode pTreenode);

void PreTraverseImpl(PTreeNode pTreenode); // 递归前序遍历树
void InTraverseImpl(PTreeNode pTreenode); // 递归中序遍历树
void PostTraverseImpl(PTreeNode pTreenode); // 递归后序遍历树

void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非递归前序遍历树
void NoRecInTraverseImpl(PTreeNode pTreenode); // 非递归中序遍历树
void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非递归后序遍历树

void LevelTraverseImpl(PTreeNode pTreenode);

PTreeNode m_pRoot; // 根结点

// 采用STL里面的stack作为模拟保存链表结点的stack容器
typedef std::stack TreeNodeStack;
};

#endif
#include
#include
#include
#include "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)
: m_pRoot(NULL)
{
assert(NULL != Array);
assert(nLength > 0);

m_pRoot = CreateTreeImpl(Array, nLength);
}

BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}

// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
int mid = nLength / 2;
PTreeNode p = new TreeNode(Array[mid]);

if (nLength > 1)
{
p->pLeft = CreateTreeImpl(Array, nLength / 2);
p->pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
}

return p;
}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
if (NULL != pTreenode->pLeft)
{
DetroyTreeImpl(pTreenode->pLeft);
}
if (NULL != pTreenode->pRight)
{
DetroyTreeImpl(pTreenode->pRight);
}

delete pTreenode;
pTreenode = NULL;
}

// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /**//*= true*/)
{
switch (traversetype)
{
case PREORDER: // 前序
{
if (true == bRec)
{
std::cout << "递归前序遍历树
";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout << "非递归前序遍历树
";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;

case INORDER: // 中序
{
if (true == bRec)
{
std::cout << "递归中序遍历树
";
InTraverseImpl(m_pRoot);
}
else
{
std::cout << "非递归中序遍历树
";
NoRecInTraverseImpl(m_pRoot);
}
}
break;

case POSTORDER: // 后序
{
if (true == bRec)
{
std::cout << "递归后序遍历树
";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout << "非递归后序遍历树
";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;

case LEVELORDER: // 层序
{
std::cout << "层序遍历树
";
LevelTraverseImpl(m_pRoot);
}
}

std::cout << std::endl;
}

// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

std::cout Node << std::endl;

PreTraverseImpl(pTreenode->pLeft);

PreTraverseImpl(pTreenode->pRight);
}

// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
std::cout Node << std::endl; // 访问当前结点
NodeStack.push(pNode->pLeft); // 左子树根结点入栈
}
NodeStack.pop(); // 左子树根结点退栈
if (!NodeStack.empty())
{
pNode = NodeStack.top();
NodeStack.pop(); // 当前结点退栈
NodeStack.push(pNode->pRight); // 当前结点的右子树根结点入栈
}
}
}

// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
InTraverseImpl(pTreenode->pLeft);
}

std::cout Node << std::endl;

if (NULL != pTreenode->pRight)
{
InTraverseImpl(pTreenode->pRight);
}
}

// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
NodeStack.push(pNode->pLeft);
}

NodeStack.pop();

if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
{
std::cout Node << std::endl;
NodeStack.pop();
NodeStack.push(pNode->pRight);
}
}
}

// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
PostTraverseImpl(pTreenode->pLeft);
}

if (NULL != pTreenode->pRight)
{
PostTraverseImpl(pTreenode->pRight);
}

std::cout Node << std::endl;
}

// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode1, pNode2;
NodeStack.push(pTreenode);
pNode1 = pTreenode->pLeft;

bool bVisitRoot = false; // 标志位,是否访问过根结点
while (!NodeStack.empty())
{
while (NULL != pNode1) // 向左走到尽头
{
NodeStack.push(pNode1);
pNode1 = pNode1->pLeft;
}

pNode1 = NodeStack.top();
NodeStack.pop();

if (NULL == pNode1->pRight) // 如果没有右子树就是叶子结点
{
std::cout Node << std::endl;
pNode2 = pNode1;
pNode1 = NodeStack.top();

if (pNode2 == pNode1->pRight) // 如果这个叶子结点是右子树
{
std::cout Node << std::endl;
NodeStack.pop();
pNode1 = NULL;
}
else // 否则访问右子树
{
pNode1 = pNode1->pRight;
}
}
else // 访问右子树
{
if (pNode1 == pTreenode && true == bVisitRoot) // 如果已经访问过右子树那么就退出
{
std::cout Node << std::endl;
return;
}
else
{
if (pNode1 == pTreenode)
{
bVisitRoot = true;
}

NodeStack.push(pNode1);
pNode1 = pNode1->pRight;
}
}
}
}

// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

// 层序遍历用于保存结点的容器是队列
std::queue NodeQueue;
PTreeNode pNode;
NodeQueue.push(pTreenode);

while (!NodeQueue.empty())
{
pNode = NodeQueue.front();
NodeQueue.pop();
std::cout Node << std::endl;

if (NULL != pNode->pLeft)
{
NodeQueue.push(pNode->pLeft);
}
if (NULL != pNode->pRight)
{
NodeQueue.push(pNode->pRight);
}
}
}
#include "BinaryTree.h"

#include
#include
#include
#include

void DisplayArray(int array[], int length)
{
int i;

for (i = 0; i < length; i++)
{
printf("array[%d] = %d
", i, array[i]);
}
}

void CreateNewArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256 + i;
}
}

int main()
{
int array[10];
srand(time(NULL));

// 创建数组
CreateNewArray(array, 10);
DisplayArray(array, 10);

BinaryTree *pTree = new BinaryTree(array, 10);

// 测试前序遍历
pTree->Traverse(BinaryTree::PREORDER);
std::cout GetRoot()->Node << std::endl;
std::cout left = " GetRoot()->pLeft->Node << std::endl;
std::cout right = " GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::PREORDER, false);

// 测试中序遍历
pTree->Traverse(BinaryTree::INORDER);
std::cout GetRoot()->Node << std::endl;
std::cout left = " GetRoot()->pLeft->Node << std::endl;
std::cout right = " GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::INORDER, false);
// 测试后序遍历
pTree->Traverse(BinaryTree::POSTORDER);
std::cout GetRoot()->Node << std::endl;
std::cout left = " GetRoot()->pLeft->Node << std::endl;
std::cout right = " GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::POSTORDER, false);
// 测试层序遍历
pTree->Traverse(BinaryTree::LEVELORDER);

system("pause");

delete pTree;

return 0;
}

#include
#include
#include
#define MAX 100
//定义二叉树链表
struct Bitree
{
char c;
struct Bitree *lchild,*rchild;
};
//定义队列
struct Quene
{
struct Bitree *p;//指向数的节点的指针
struct Quene *next;
};
//定义哈夫曼树的结构
struct Huffman
{
int weight;//权值
int tag;
int parent,lchild,rchild;
char ch;
};

struct Bitree *creatBt()
{
struct Bitree *btree;
char ch;
cin>>ch;
// "访问"操作为生成根结点
if(ch!='#')
{
btree=(struct Bitree * )malloc(sizeof(struct Bitree )) ;
btree->c=ch;
btree->lchild=creatBt(); // 递归建(遍历)左子树
btree->rchild=creatBt(); // 递归建(遍历)右子树
}
if(ch=='#')
{
btree=NULL;
}
return btree;
}
//先序遍历递归
void preOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
coutc<<" ";
preOrder1(p->lchild);
preOrder1(p->rchild);
}
}
//中序遍历递归
void inOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
inOrder1(p->lchild);
coutc<<" ";
if(p->rchild!=NULL)
inOrder1(p->rchild);
}
//后序遍历递归
void postOrder1(struct Bitree *btree)
{
struct Bitree *p;
p=btree;

if(p->lchild!=NULL)
postOrder1(p->lchild);
if(p->rchild!=NULL)
postOrder1(p->rchild);
coutc<<" ";


}
//非递归先序遍历
void preOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do
{
while(p!=NULL)
{
coutc<<" ";
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
p=p->rchild;
}
}
while(top>0||p!=NULL);
}
//非递归中序遍历
void inOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
do// while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
coutc<<" ";
p=p->rchild;
}
} while(top>0||p!=NULL);
}
//非递归后序遍历
void postOrder2(struct Bitree *btree)
{
struct Bitree *p, *node[MAX];
int top=0;
p=btree;
while(top>0||p!=NULL)
{
while(p!=NULL)
{
node[top]=p;
top++;
p=p->lchild;
}
if(top>0)
{
top--;
p=node[top];
if(p->rchild==NULL)
coutc<<" ";
p=p->rchild;
}
}
p=btree;
coutc<<" ";
}
//二叉树的高度
int btHeigh(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int hl=0, h2=0, max=0;
if(p!=NULL)
{
hl=btHeigh(p->lchild); //求左子树的深度
h2=btHeigh(p->rchild); //求右子树的深度
max=hl>h2?hl: h2;
return(max+1);// 返回树的深度
}
else
return 0;
}
//求二叉树的叶子个数
int numLeave(struct Bitree *btree)
{
struct Bitree *p;
p=btree;
int static n=0;//静态变量计数
if(p!=NULL)
{
if(p->lchild==NULL&&p->rchild==NULL)
n++; //若root所指结点为叶子, 则累加
numLeave(p->lchild);
numLeave(p->rchild);
return n;
}
else
return 0;
}
//借助队列实现二叉树的层次遍历。
void btQuene(struct Bitree *btree)
{
struct Quene *head,*rear,*temp;
head=(struct Quene*)malloc(sizeof(struct Quene));//给队列头指针分配器空间
head->p=btree;
head->next=NULL;
rear=head;
while(head!=NULL)
{
if(head->p->lchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));//中间变量暂时保存数的结点
temp->p=head->p->lchild;
temp->next=NULL;
rear->next=temp;//将新结点连接在前一个结点的后面
rear=temp;
}
if(head->p->rchild!=NULL)
{
temp=(struct Quene *)malloc(sizeof(struct Quene));
temp->p=head->p->rchild;
temp->next=NULL;
rear->next=temp;
rear=temp;
}
temp=head;
coutp->c;
head=head->next;
free(temp);
}
}
//建立哈夫曼树
void creatHfm()
{
struct Huffman *HF;
int num;
int i,j,x1,x2,m1,m2;
cout<<"输入字符个数；";
cin>>num;
if(num<=1)
{
cout<<"不能建立哈夫曼树！"<<endl;
return ;
}
HF=new struct Huffman[2*num-1];
char c;
//构造叶子结点数为num,权值为weight的哈夫曼树HF[]
for(i=0;i<num;i++)
{
cout<<"请输入第"<<i+1<<"个字符值:";
cin>>c;
HF[i].ch=c;
cout<<"请输入该字符的权值:";
cin>>HF[i].weight;
HF[i].parent=-1;
HF[i].lchild=-1;
HF[i].rchild=-1;
HF[i].tag=0;
}
//构造非叶子结点
for(i=0;i<num-1;i++)//合并n-1次
{
m1=m2=32767;//m1是最小值单元，m2为次小值
x1=x2=0;//x1，x2为下标号
for(j=0;j<num+1;j++)//找最小权值和次小权值
{
if(HF[i].weight<m1&&HF[j].tag==0)
{
m2=m1;
x2=x1;
m1=HF[j].weight;
x1=j;
}
else if(HF[j].weight<m2&&HF[j].tag==0)
{
m2=HF[j].weight;
x2=j;
}
}
//将两棵子树合并成一棵新树
HF[x1].parent=num+i;//x1,x2对应的子树分别作为n+i的左右子树
HF[x2].parent=num+i;
HF[x1].tag=1;
HF[x2].tag=1;
HF[num+i].weight=HF[x1].weight+HF[x2].weight;//新书跟的权值为左右树根的权值之和
HF[num+i].lchild=x1;//n+i的做孩子是x1
HF[num+i].rchild=x2;
}
cout<<"哈夫曼树创建成功!"<<endl;
}


//删除值为x的结点，并释放相应的空间
void btFree(struct Bitree *btree,char x)
{
struct Bitree *p;
p=btree;
if(p!=NULL)
{
if(p->c==x)
{
free(p);
cout<<"释放成功！"<<endl;
}
else
{
btFree(p->lchild,x);
btFree(p->rchild,x);
}

}
else
cout<<"空间释放失败！"<<endl;
}
void main()
{
int key;
int depth;
int numLea;
struct Bitree *btree;
cout<<"输入数的节点，'#'表示空节点:"<<endl;
btree=creatBt();
cout<<"二叉树创建成功!"<<endl;
cout<<endl;

cout<<"***********************************"<<endl;
cout<<" 选择菜单 "<<endl;
cout<<"1、递归先序遍历二叉树 "<<endl;
cout<<"2、递归中序遍历二叉树 "<<endl;
cout<<"3、递归后序遍历二叉树 "<<endl;
cout<<"4、非递归先序遍历二叉树 "<<endl;
cout<<"5、非递归中序遍历二叉树 "<<endl;
cout<<"6、非递归后序遍历二叉树 "<<endl;
cout<<"7、求二叉树的高度 "<<endl;
cout<<"8、求二叉树的叶子结点个数 "<<endl;
cout<<"9、队列实现二叉树层次遍历"<<endl;
cout<<"10、建立哈夫曼树 "<<endl;
cout<<"11、释放空间 "<<endl;
cout<<"***********************************"<<endl;
for(;key!=0;)
{
cout<<"输入选项，(0表示结束操作):";
cin>>key;
switch(key)
{

case 1:
cout<<"递归先序遍历结果是:";
preOrder1(btree);
cout<<endl;
break;
case 2:
cout<<"递归中序遍历结果是:";
inOrder1(btree);
cout<<endl;
break;
case 3:
cout<<"递归后序遍历结果是:";
postOrder1(btree);
cout<<endl;
break;
case 4:
cout<<"非递归先序遍历结果是:";
preOrder2(btree);
cout<<endl;
break;
case 5:
cout<<"非递归中序遍历结果是:";
inOrder2(btree);
cout<<endl;
break;
case 6:
cout<<"非递归后序遍历结果是:";
postOrder2(btree);
cout<<endl;
break;
case 7:
depth=btHeigh(btree);
cout<<"二叉树的高度为";
cout<<depth<<endl;
break;
case 8:
numLea=numLeave(btree);
cout<<"二叉树的叶子结点数为";
cout<<numLea<<endl;
break;
case 9:
cout<<"层次遍历的结果为:";
btQuene(btree);
cout<<endl;
break;
case 10:
creatHfm();
break;
case 11:
char c;
cout<<"输入要释放的结点:";
cin>>c;
btFree(btree,c);
break;
default:
printf("
输入选项错误！
");
}
}
}

这是关于线性表的代码.
#define ElemType int
typedef int Status;

// 链表类型
typedef struct Node
{
ElemType data;
struct Node *next;
} Node, *LinkList;

// 建立一个带头结点的空线性链表L
void InitList(LinkList &L)
{
L=(LinkList) malloc(sizeof(Node)); //生成新结点
if (!L) return; //存储分配失败
else L->next=NULL;
} //InitList

// 输出线性链表L中的所有数据元素
void PrintList(LinkList L)
{
LinkList p=L->next;
printf("\nL = ( ");
while (p)
{
printf("%d ",p->data);
p=p->next;
}
printf(")\n");
} //PrintList

// 计算线性链表L中结点的个数
Status LengthList(LinkList L)
{
LinkList p=L->next;
int i=0;
while (p)
{
++i;
p=p->next;
}
return (i);
} //LengthList

// 在线性链表L中第i个结点之前插入新的数据元素e
void InsertList(LinkList &L,int i,ElemType e)
{
LinkList q; //=(LinkList) malloc(sizeof(Node));
InitList(q);
q->data=e;
int j=1;
LinkList p=L;
while (p->next && j<i)
{
++j;
p=p->next;
} //寻找第i个结点
if (p->next) q->next=p->next;
p->next=q;
} //InsertLinst

// 删除线性链表L中的第i个结点
void DeleteList(LinkList &L,int i)
{
LinkList q;
int j=1;
LinkList p=L;
while (p->next && j<i)
{
++j;
p=p->next;
} //寻找第i个结点
if (p->next)
{
q=p->next;
p->next=q->next;
free(q); //删除并释放结点
}
} //DeleteList

// 用数据元素e更新线性链表L中第i个数据元素的值
void PutList(LinkList &L,int i,ElemType e)
{
LinkList p=L->next;
int j=1;
while (p && j<i)
{
++j;
p=p->next;
}
if (p) p->data=e;
} //PutList

// 销毁线性链表L
void DestroyList(LinkList &L)
{
free(L);
L=NULL;
printf("\n线性链表L已销毁\n");
} //DestroyList

这是关于二叉树的
#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <conio.h>
typedef char ElemType;
char Str[256]; //存放字符型二叉树
int Sk=1;

// 二叉树(二叉)链表的存储结构
typedef struct BiTNode
{
ElemType data; //叶子结点的值
struct BiTNode *Lchild; //左孩子链表指针
struct BiTNode *Rchild; //右孩子链表指针
bool Tag; //0:分支结点, 1:叶子结点
} *BiTree;

// 链栈(队列)类型
typedef struct SNode
{
struct BiTNode *tnode; //数据域
struct SNode *next; //指针域
int Level; //结点所在的层次
} *LinkStack;

// 构造一个带头结点的空链栈(队列)S
int StackInit(LinkStack &S)
{
S=(LinkStack) malloc(sizeof(SNode));
if(!S) return 0; //存储分配失败
S->next=NULL;
S->Level=1; //根结点的层序号
return 1;
}//StackInit

// 向链栈S的栈顶压入一个新的数据元素Tdata
int Push(LinkStack &S,BiTree Tdata)
{
LinkStack p=(LinkStack) malloc(sizeof(SNode));
if(!S) return 0;
p->tnode=Tdata;
p->next=S->next;
S->next=p;
return 1;
}//Push

// 弹出链栈S中的栈顶元素，并用Tdata返回
void Pop(LinkStack &S,BiTree &Tdata)
{
LinkStack p=S->next;
if(p)
{
S->next=p->next;
Tdata=p->tnode;
free(p);
}
else Tdata=NULL;
}//Pop

// 向链队列S插入新的数据元素Tdata和Tlevel
int Qinsert(LinkStack &S,BiTree Tdata,int Tlevel)
{
LinkStack p=(LinkStack) malloc(sizeof(SNode));
if(!p) return 0;
LinkStack q=S;
while(q->next) q=q->next;
p->tnode=Tdata;
p->Level=Tlevel;
q->next=p;
p->next=NULL;
return 1;
}//Qinsert

// 删除链队列S中的队首元素，并用Tdata和Tlevel返回
void Qdelete(LinkStack &S,BiTree &Tdata,int &Tlevel)
{
LinkStack p=S->next;
if(p)
{
S->next=p->next;
Tdata=p->tnode;
Tlevel=p->Level;
free(p);
}
else
{
Tdata=NULL;
Tlevel=0;
}
}//Pop

// 判断字符S1是否属于数据元素值域
int BiTreeElemTypeS(char S1)
{
if(isalpha(S1)||S1=='+'||S1=='-'||S1=='*'||S1=='/') return 1;
if(isdigit(S1)||S1==' '||S1=='^') return 1;
return 0;
}//BiTreeElemTypeS

// 判断两个运算符的大小：> 1，= 0，< -1
int InOperator(ElemType S1,ElemType S2)
{
if(S2=='*' || S2=='/') return 0;
if(S1=='*' || S1=='/') return 1;
if(S1=='+') return 0;
if(S1=='-' && S2=='+') return 0;
if(S1=='-') return 1;
if(S1=='(' && S2==')') return 0;
if(S1=='(' || S2=='(') return -1;
if(S1==')' && S2=='(') return 2;
if(S1==')' || S2==')') return 1;
return 2; //表示无效运算符
}//InOperator

// 去掉二叉树字符串中不符合要求的字符
void BiTreeString(char *St)
{
int j=0,k=0;
char ch=St[0];
while(ch && ch!=';')
{
if(ch=='('||ch==')'||ch==','||BiTreeElemTypeS(ch)==1)
{
St[k]=ch;
++k;
}
++j;
ch=St[j];
}
St[k]='\0';
j=k=0;
ch=St[0];
Str[0]=' ';
while(ch && ch!=';')
{
if(ch=='(' && St[j+1]==')') j+=2;
if(ch==',' && St[j+1]==')') ++j;
++k;
Str[k]=St[j];
++j;
ch=St[j];
}
Str[k+1]='\0';
}//BiTreeString

// 构造一个带头结点的空二叉树链表T
int BiTreeInit(BiTree &T)
{
T=(BiTree) malloc(sizeof(BiTNode));
if(!T) return 0;
T->Lchild=T->Rchild=NULL;
T->Tag=0;
return 1;
}//BiTreeInit

// 根据字符串型二叉树建立二叉树链表T的存储结构(递归算法)
void BiTreeCreate(BiTree &T)
{
BiTree p;
char ch=Str[Sk];
while(ch && ch!=';')
{
if(BiTreeElemTypeS(ch)==1)
{
BiTreeInit(p);
p->data=ch;
p->Tag=0;
if(Str[Sk-1]==',') T->Rchild=p;
else T->Lchild=p;
++Sk;
BiTreeCreate(p);
}
else if(ch=='(' && Str[Sk+1]==',') Sk+=2;
else if(ch==',' && Str[Sk+1]==')'||ch=='(') ++Sk;
else if(ch==')'||ch==',')
{
++Sk;
return;
}
ch=Str[Sk];
}
}//BiTreeCreate

// 根据层序输入建立二叉树链表T的存储结构(非递归算法)
// 输入结点值：无左或右孩子时输入空格，输入#或;结束
void BiTreeCreateL(BiTree Tl)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree q,p=Tl;
char N; //存放结点值
int Lr=1,Ln=1,N1=1,Sk=1; //Lr左右标识 N1层号
printf("\nInput Root (Input #, Over.): ");
N=getche();
while(N!='#' && N!=';')
{
BiTreeInit(q);
q->data=N;
q->Tag=0;
if(Lr==1) p->Lchild=q;
if(Lr==2) p->Rchild=q;
if(Ln==Sk)
{
++N1;
printf("\nLevel %d:",N1);
Ln=0;
Sk*=2;
}
Qinsert(S,q,1);
Qinsert(S,q,2);
N=' ';
while(N==' ')
{
Qdelete(S,p,Lr);
++Ln;
if(Lr==1) N='L';
else N='R';
printf("\n %c.%c: ",p->data,N); N=getche();
}
}
free(S);
S->next=NULL;
}//BiTreeCreateL

//访问结点p的描述函数
void Visit(BiTree p)
{
printf("%c ",p->data);
}//Visit

// 根据二叉树链表输出字符串型二叉树T
void BiTreePrintS(BiTree T)
{
if(!T) return;
printf("%c",T->data);
if(T->Lchild)
{
printf("(");
BiTreePrintS(T->Lchild);
}
else
{
if(!T->Rchild) return;
else printf("(");
}
if(T->Rchild)
{
printf(",");
BiTreePrintS(T->Rchild);
printf(")");
}
while(!T->Rchild)
{
printf(")");
return;
}
}//BiTreePrintS

// 根据二叉树链表求二叉树T的深度(高度)
int BiTreeDepth(BiTree T)
{
if(!T) return 0;
int dep1=BiTreeDepth(T->Lchild);
int dep2=BiTreeDepth(T->Rchild);
if(dep2>dep1) dep1=dep2;
return dep1+1;
}//BiTreeDepth

// 根据字符串型二叉树求二叉树T的深度(高度)
int BiTreeDepthS(char *St)
{
char ch=St[1];
if(!BiTreeElemTypeS(ch)) return 0;
int i=0,j=0,k=1; //j记录"("的最大曾数
while(ch && ch!=';')
{
if(ch=='(')
{
++i;
if(i>j) j=i;
}
if(ch==')') --i;
++k;
ch=St[k];
}
return j+1;
}//BiTreeDepthS

// 将二叉树链表T中所有值为x的数据元素都替换为y
void BiTreeReplace(BiTree &T,ElemType x,ElemType y)
{
if(!T) return;
if(T->data==x) T->data=y;
if(T->Lchild) BiTreeReplace(T->Lchild,x,y);
else if(!T->Rchild) return;
if(T->Rchild) BiTreeReplace(T->Rchild,x,y);
while(!T->Rchild) return;
}//BiTreeReplace

// 求二叉树链表T中值为x的数据元素所在的层次
int BiTreeLevel(BiTree T,ElemType x)
{
if(!T) return 0;
if(T->data==x) return 1;
if(T->Lchild)
{
++Sk;
if(BiTreeLevel(T->Lchild,x)) return 1;
--Sk;
}
if(T->Rchild)
{
++Sk;
if(BiTreeLevel(T->Rchild,x)) return 1;
--Sk;
}
return 0;
}//BiTreeLevel

// 在二叉树T中查找数据元素x的递归算法(查找成功时返回该结点的指针)
BiTree BiTreeSearch(BiTree T, ElemType x)
{
if(!T) return NULL;
if(T->data==x) return T; //查找成功
BiTree p;
if(T->Lchild)
{
p=BiTreeSearch(T->Lchild,x);
if(p) return p;
}
if(T->Rchild)
{
p=BiTreeSearch(T->Rchild,x);
if(p) return p;
}
return NULL; //查找失败出口
}//BiTreeSearch

// 先序遍历二叉树T的递归算法
void PreOrder(BiTree T)
{
if(!T) return; //递归出口
Visit(T);
PreOrder(T->Lchild);
PreOrder(T->Rchild);
}//PreOrder

// 先序遍历二叉树T的非递归算法
void PreOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Visit(p);
Push(S,p);
p=p->Lchild;
}
Visit(p);
while(p && !p->Rchild) Pop(S,p);
if(p && p->Rchild) p=p->Rchild;
}
}//PreOrderS

// 中序遍历二叉树T的递归算法
void InOrder(BiTree T)
{
if(!T) return;
InOrder(T->Lchild);
Visit(T);
InOrder(T->Rchild);
}//InOrder

// 中序遍历二叉树T的非递归算法
void InOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Push(S,p);
p=p->Lchild;
}
Visit(p);
while(p && !p->Rchild)
{
Pop(S,p);
if(p) Visit(p);
}
if(p && p->Rchild) p=p->Rchild;
}
}//InOrderS

// 后序遍历二叉树T的递归算法
void PostOrder(BiTree T)
{
if(!T) return;
if(T->Lchild) PostOrder(T->Lchild);
if(T->Rchild) PostOrder(T->Rchild);
Visit(T);
}//PostOrder

// 后序遍历二叉树T的非递归算法
void PostOrderS(BiTree T)
{
LinkStack L;
if(!StackInit(L)) return;
LinkStack R;
if(!StackInit(R)) return;
BiTree q,p=T->Lchild;
while(p)
{
while(p->Lchild)
{
Push(L,p);
p=p->Lchild;
}
while(p && !p->Rchild)
{
Visit(p);
q=p;
while(R->next && R->next->tnode->Rchild==q)
{
Pop(R,q);
Visit(q);
}
Pop(L,p);
}
if(p && p->Rchild)
{
Push(R,p);
p=p->Rchild;
}
}
}//PostOrderS

// 层序遍历二叉树链表T的非递归算法
void LevelOrderS(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p=T->Lchild;
while(S && p)
{
Visit(p);
if(p->Lchild) Qinsert(S,p->Lchild,1);
if(p->Rchild) Qinsert(S,p->Rchild,2);
Qdelete(S,p,Sk); //Pop(S,p);
}
}//LevelOrderS

// 分层输出二叉树链表T的非递归算法
void BiTreeLevel(BiTree T)
{
LinkStack S;
if(!StackInit(S)) return;
int k=0,Ln=1; //Ln层次计数
BiTree p=T->Lchild;
while(S && p)
{
if(Ln!=k)
{
printf("\n");
k=Ln;
}
Visit(p);
if(p->Lchild) Qinsert(S,p->Lchild,k+1);
if(p->Rchild) Qinsert(S,p->Rchild,k+1);
Qdelete(S,p,Ln);
}
}//BiTreeLevel

// 先序后继线索化二叉树Tl的非递归算法
void PreOrderT(BiTree Tl)
{
LinkStack S;
if(!StackInit(S)) return;
BiTree p0,p=p0=Tl->Lchild;
while(p)
{
while(p->Lchild)
{
Push(S,p);
p=p->Lchild;
}
if(p->Rchild) p=p->Rchild;
else
{
while(p && !p->Rchild)
{
if(!p->Lchild) p0=p;
Pop(S,p);
}
if(p && p->Rchild)
{
p=p->Rchild;
if(!p0->Tag)
{
p0->Rchild=p;
p0->Tag=1;
}
}
}
}
}//PreOrderT

// 输出先序后继线索化二叉树Tl的数据元素值
void PreOrderPrint(BiTree Tl)
{
BiTree p=Tl->Lchild;
while(p)
{
Visit(p);
if(p->Lchild) p=p->Lchild;
else p=p->Rchild;
}
}//PreOrderPrint

void main()
{
char s0[]="A(B(D(,a),b),C(E(c,d),F(G(f),e)));";
BiTreeString(s0);
printf("\nStr= %s",s0);

BiTree p;
BiTreeInit(p);
BiTreeCreate(p);
printf("\n→T= ");
BiTreePrintS(p->Lchild);

printf("\n\nBiTreeDepth= %d",BiTreeDepth(p->Lchild));
printf("\nStringDepth= %d\n",BiTreeDepthS(Str));

BiTreeReplace(p,'e','s');
printf("\nReplace-T= ");
BiTreePrintS(p->Lchild);

Sk=0;
char s='d';
int k=BiTreeLevel(p->Lchild,s);
if (!k) printf("\n\nBiTreeLevel of %c is 0\n",s);
else printf("\n\nBiTreeLevel of %c is %d",s,Sk+1);
printf("\nElement %c at %d\n",s,BiTreeSearch(p,s));

printf("\nPre-T= ");
PreOrder(p->Lchild);
printf("\nPreST= ");
PreOrderS(p);

printf("\n\n In-T= ");
InOrder(p->Lchild);
printf("\nInS-T= ");
InOrderS(p);

printf("\n\nPost-T= ");
PostOrder(p->Lchild);
printf("\nPostST= ");
PostOrderS(p);

printf("\n\nLevel-T= ");
LevelOrderS(p);

Sk=BiTreeDepth(p->Lchild);
BiTreeLevel(p);

PreOrderT(p);
printf("\n\nPreThread= ");
PreOrderPrint(p);

printf("\n\n");
free(p);
}

这是我们老师的代码,都没有问题的，如果还有不懂的地方,我们可以继续探讨.

数据结构课程设计,有向图,C语言高手进
答：已编译确认：/* 图的深度优先遍历 */ include <stdlib.h> include <stdio.h> include <conio.h> struct node /* 图顶点结构定义 */ { int vertex; /* 顶点数据信息 */ struct node *nextnode; /* 指下一顶点的指标 */ };typedef struct node *graph; /* 图形的结构新型态 */ struct...

用C设计哈希表——数据结构课程设计
答：用C设计哈希表——数据结构课程设计 [问题描述]针对自己的班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。[基本要求]假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有... [问题描述]针对自己的班集体中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成...

数据结构C语言版课程设计
答：幂次(0 0结束) : 1 1系数 幂次(0 0结束) : -2 0系数 幂次(0 0结束) : 0 0B(x) = 1.00x^4 - 3.00x^2 + 1.00x - 2.00C(x) = 3.00x^6 + 2.00x^5 - 8.00x^4 - 3.00x^3 - 7.00x^2 - 3.00x - 2.00A(2.00) = 17.0000B(2.00) = 4.0000C...

数据结构课程设计c语言方向!
答：或是要进来，那么电梯停止、开门，等候出去的人出完，进来的人进来（当然，这是不允许超载的）。 你也可以选择H或是h来查看帮助菜单。最后你可以选择esc退出。·概要设计 在开始之前会让用户输入楼层数及电梯数，程序根据数据构造整个建筑。楼层中有等候的地方有两个按钮，...

急求数据结构C语言设计(高手进)
答：define m 4/*课程数*/ using namespace std;//---声明一个结构--- struct Student { char m_Name[20];unsigned int m_ID;float m_Score[m];};typedef struct Student Node;//---函数声明--- Node* Init(Node* stu,const int cN,float* Asum,int nSum);float* Sort(float* Agrade...

数据结构 课程设计C语言版 本人现..跪求一道课程设计答案 有哪..位的...
答：数据结构 课程设计C语言版 本人现..跪求一道课程设计答案 有哪..位的大仙帮帮我,现在只能给100分,完了追 题目:职工工资管理系统(编号、姓名、年龄、性别、基础工资、补贴工资、扣除工资、总工资){密码启动、修改模块、数据输入模块、数据插入模块、数据统计模块(分别统计基础工资、补贴... 题目:职工工资管理系统...

数据结构c语言版的 课程设计
答：数据结构c语言版的 课程设计 设计题目有:停车场管理系统,哈夫曼编/译码器,一元稀疏多项式.望各位高手指点一下,可加分!!!... 设计题目有:停车场管理系统,哈夫曼编/译码器,一元稀疏多项式.望各位高手指点一下,可加分!!! 展开  我来答 3个回答 #活动#...

[数据结构课程设计代码]C编写,好的话追加80分,谢谢]
答：typedef struct { unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */ typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */ /* 求赫夫曼编码 */ include"c1.h"include"c6-7.h"include"func6-1.c"void HuffmanCoding(...

c语言的数据结构和程序设计
答：一般认为,一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构;数据必须在计算机内存储,数据的存储结构是数据结构的实现形式,是其在计算机内的表示;此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中,数据结构的选择是一个基...

急!!!数据结构课程设计
答：2011-09-14 救急!!!数据结构课程设计 2014-11-22 数据结构课程设计,谁懂编程的,赶紧救救急啊!!! 2011-01-01 急求一份数据结构的课程设计!!! 2010-12-23 急~~!很急,真的很急~数据结构课程设计:简易家谱系统! 3 2009-12-19 急求C语言数据结构课程设计!!! 1 更多类似问题 > 为你...