求两个数据结构实验的代码

Question

二叉树的基本操作：
以二叉链表作存储结构，编写程序，实现如下的功能：
1、根据输入的数据建立一个二叉树；
2、分别采用前序、中序、后序的遍历方式显示输出二叉树的遍历结果
3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和最小值。

快速排序
假设待排的序列为{R[S], R[S+1], R[S+2],……， R[T]},
首先任意选取一个记录，R[S]作为枢轴，然后重新排列其它记录。将所有关键字比它小的记录都放在它的前面，其它所有关键字比它大的记录放在它的后面。由此可以将记录以“枢轴”为界，将记录分为两个子序列，这个过程称为一趟快速排序。以后再分别对两个子序列进行快速排序，重复进行这个过程，直到整个序列全部有序为止。
快速排序的平均时间为 Tavg(n)=kn ln n，其中n为待排记录的个数。K为某个常数，经验证明在所有的同数量级的先进排序方法之中，快排的k最小。

Answer 1

二叉树的遍历：前序，中序，后序，层序－－包括递归和非递归实现
后序遍历还没有明白，继续学习^_^，过几天写个huffman编码的例子来玩玩，不多说了，看代码吧，注意：程序申请的空间并没有释放^_^
/**//********************************************************************
created: 2005/12/30
created: 30:12:2005 10:39
filename: bintree.h
author: Liu Qi

purpose: 二叉树的3种遍历方式(包括非递归实现),前序，后序和中序，先访问根节点就是
前序(部分书籍称为先根遍历,个人觉得该说法更好^_^)，类似的，最后访问根节点就是后序
*********************************************************************/

#ifndef TREE_H
#define TREE_H

#include <stdio.h>
#include <malloc.h>
#include <stack>
#include <queue>
#include <assert.h>

using namespace std;

typedef int ElemType;

typedef struct treeT
{
ElemType key;
struct treeT* left;
struct treeT* right;
}treeT, *pTreeT;

/**//*===========================================================================
* Function name: visit
* Parameter: root:树根节点指针
* Precondition:
* Description:
* Return value:
* Author: Liu Qi, //-
===========================================================================*/
static void visit(pTreeT root)
{
if (NULL != root)
{
printf(" %d\n", root->key);
}
}

/**//*===========================================================================
* Function name: BT_MakeNode
* Parameter: target:元素值
* Precondition: None
* Postcondition: NULL != pTreeT
* Description: 构造一个tree节点，置左右指针为空，并且返回指向新节点的指针
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
static pTreeT BT_MakeNode(ElemType target)
{
pTreeT pNode = (pTreeT) malloc(sizeof(treeT));

assert( NULL != pNode );

pNode->key = target;
pNode->left = NULL;
pNode->right = NULL;

return pNode;
}

/**//*===========================================================================
* Function name: BT_Insert
* Parameter: target:要插入的元素值, pNode:指向某一个节点的指针
* Precondition: NULL != ppTree
* Description: 插入target到pNode的后面
* Return value: 指向新节点的指针
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
pTreeT BT_Insert(ElemType target, pTreeT* ppTree)
{
pTreeT Node;

assert( NULL != ppTree );

Node = *ppTree;
if (NULL == Node)
{
return *ppTree = BT_MakeNode(target);
}

if (Node->key == target) //不允许出现相同的元素
{
return NULL;
}
else if (Node->key > target) //向左
{
return BT_Insert(target, &Node->left);
}
else
{
return BT_Insert(target, &Node->right);
}
}

/**//*===========================================================================
* Function name: BT_PreOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 前序遍历
* Return value: void
* Author: Liu Qi, [12/29/2005]
===========================================================================*/
void BT_PreOrder(pTreeT root)
{
if (NULL != root)
{
visit(root);
BT_PreOrder(root->left);
BT_PreOrder(root->right);
}
}

/**//*===========================================================================
* Function name: BT_PreOrderNoRec
* Parameter: root:树根节点指针
* Precondition: Node
* Description: 前序(先根)遍历非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_PreOrderNoRec(pTreeT root)
{
stack<treeT *> s;

while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
visit(root);
s.push(root);
root = root->left;
}
else
{
root = s.top();
s.pop();
root = root->right;
}
}
}

/**//*===========================================================================
* Function name: BT_InOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_InOrder(pTreeT root)
{
if (NULL != root)
{
BT_InOrder(root->left);
visit(root);
BT_InOrder(root->right);
}
}

/**//*===========================================================================
* Function name: BT_InOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 中序遍历,非递归算法
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_InOrderNoRec(pTreeT root)
{
stack<treeT *> s;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
visit(root);
s.pop();
root = root->right;
}
}
}

/**//*===========================================================================
* Function name: BT_PostOrder
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历
* Return value: void
* Author: Liu Qi, [12/30/2005]
===========================================================================*/
void BT_PostOrder(pTreeT root)
{
if (NULL != root)
{
BT_PostOrder(root->left);
BT_PostOrder(root->right);
visit(root);
}
}

/**//*===========================================================================
* Function name: BT_PostOrderNoRec
* Parameter: root:树根节点指针
* Precondition: None
* Description: 后序遍历,非递归算法
* Return value: void
* Author: Liu Qi, // [1/1/2006]
===========================================================================*/
void BT_PostOrderNoRec(pTreeT root)
{
//学习中，尚未明白
}

/**//*===========================================================================
* Function name: BT_LevelOrder
* Parameter: root:树根节点指针
* Precondition: NULL != root
* Description: 层序遍历
* Return value: void
* Author: Liu Qi, [1/1/2006]
===========================================================================*/
void BT_LevelOrder(pTreeT root)
{
queue<treeT *> q;
treeT *treePtr;

assert( NULL != root );

q.push(root);

while (!q.empty())
{
treePtr = q.front();
q.pop();
visit(treePtr);

if (NULL != treePtr->left)
{
q.push(treePtr->left);
}
if (NULL != treePtr->right)
{
q.push(treePtr->right);
}

}
}

#endif
希望能有些用。

Answer 2

二叉树的遍历，快速排序，得慢慢看。

Answer 3

看了你的问题，好像我现在只能帮上你第一个二叉树问题的第二个小问中的中序

遍历方式显示输出二叉树的遍历结果。代码如下（C语言版）

二叉树的中序遍历

#include <stdio.h>
#define NULL 0
typedef struct node
{
char data;
struct node *lchild,*rchild;
}treenode;
treenode * creat()
{
treenode *t;char ch;
ch=getchar();
if(ch=='#')
return NULL;
else
{
t=(treenode *) malloc(sizeof(treenode));
t->data=ch;
t->lchild=creat();
t->rchild=creat();
return t;
}
}
void inorder(treenode *p)
{
if(p!=NULL)
{
inorder(p->lchild);
printf("%c",p->data);
inorder(p->rchild);
}
}

main()
{
treenode *t;
t=creat();
inorder(t);
}

希望对你能有一些小小的帮助！

Answer 4

数据结构没学好，这个你到一些编程的网站看看有公开的愿代码，自己再修改下就好了