二叉树操作 求数据结构达人啊！！！！！！！！！！！

Question

/*
源文件名：P5.cpp
功能：二叉树操作
*/
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct BiTNode //二叉树结点类型
{
int data; //数据
int tem1,tem2; //辅助数据（实习题不用）
BiTNode *left; //左子树指针
BiTNode *right; //右子树指针
};

BiTNode *Tree; //本程序操作的二叉树根指针

const max=100;
int elem[max]; //存放原始数据

//从键盘输入个数和随机数种子，在数组elem中生成指定个数的数据，供其他程序使用，0表示数据结束
void init0(int list[]);

//在本程序所在的位置生成文本文件Map.txt，其中显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree);

//从键盘输入个数和随机数种子，以Tree为根指针，生成指定结点个数的二叉树，供其他程序使用
void init1(BiTNode *&Tree);

//主函数，显示功能菜单（包括生成二叉树、显示二叉树），键盘选择后执行对应功能
void main()
{
}

#include "BinT.h"

//先序、中序、后序遍历以Tree为根指针的二叉树

//使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树

//在以Tree为根指针的二叉排序树中查找结点

//从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）

//对以Tree为根指针的二叉树,从根结点开始，逐层从左到右输出各结点的数据
//提示：用数组 BiTNode *queue[max] 构成队列，利用这个队列实现功能

//*1、随机生成二叉树。 2、生成并保存先（后）序、中序输出序列。 3、按照保存的一对输出序列恢复出二叉树。 4、生成先（后）序、中序输出序列。 5、比较两对输出序列。

//*不用递归，先序、中序、后序遍历以Tree为根指针的二叉树
//提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能

//*用缩入格式的多行文本表示以Tree为根指针的二叉树，例如：
// 324
// 123
// 746
// 690
// 567

//*用广义表表示以Tree为根指针的二叉树，例如
// (324(123(746()())(690()()))(567()()))

//*使用数组elem中的随机数序列（以0表示结束，不包括0），生成赫夫曼树，计算平均带权路径长度

Answer 1

//求二叉树的深度
template <class ElemType>
int BinaryTree<ElemType>::_Depth(BTNode<ElemType>* T)
{
if (!T)
return 0;

int h1,h2;
h1 = _Depth(T->lchild);
h2 = _Depth(T->rchild);

return h1 > h2 ? h1 + 1 : h2 + 1;
}
//先序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType> ::_PreorderTraverse(BTNode<ElemType>* T,void (*visit)(const ElemType &e))
{
if (T){
visit(T->data);
_PreorderTraverse(T->lchild,visit);
_PreorderTraverse(T->rchild,visit);
}
}
//中序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType> ::_InorderTraverse(BTNode<ElemType>* T,void (*visit)(const ElemType &e))
{
if (T) {
_InorderTraverse (T->lchild,visit);
visit(T->data);
_InorderTraverse (T->rchild,visit);
}
}
//后序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType> ::_PostorderTraverse(BTNode<ElemType>* T,void (*visit)(const ElemType &e))
{
if (T){
_PostorderTraverse (T->lchild,visit);
_PostorderTraverse (T->rchild,visit);
visit (T->data);
}
}

//后序递归遍历方式换孩子
template <class ElemType>
void BinaryTree<ElemType> ::_PostTranChild(BTNode<ElemType>* T)
{ BTNode<ElemType> *p;
if (T){
_PostTranChild(T->lchild);
_PostTranChild(T->rchild);
p = T->lchild;
T->lchild = T->rchild;
T->rchild = p ;
}
}

//统计树叶结点个数
template <class ElemType>
void BinaryTree <ElemType>::_Countleaf(BTNode<ElemType>* T,int &n)
{
BTNode<ElemType> *p;
if (T){
_Countleaf(T->lchild, n);
_Countleaf(T->rchild, n);
if(!T->lchild && !T->rchild)
n++;
}
}

// 先序遍历二叉树的非递归算法(利用栈)
template <class ElemType>
void BinaryTree<ElemType> ::PreorderTraverseNonRecursive(void (*visit)(const ElemType &e))
{
stack<BTNode<ElemType> *> S;
BTNode<ElemType> *p;
S.push (m_root); //根指针进栈

while (!S.empty ()) {
p = S.top ();

while (p) {
visit(p->data);
p = p->lchild;
S.push(p); // 向左走到尽头
}

S.pop(); // 空指针退栈

if (!S.empty()){ // 访问结点,向右一步
p = S.top ();
S.pop();
S.push(p->rchild);
}
}
}

// 中序遍历二叉树的非递归算法(利用栈)
template <class ElemType>
void BinaryTree<ElemType> ::InorderTraverseNonRecursive(void (*visit)(const ElemType &e))
{
stack<BTNode<ElemType> *> S;
BTNode<ElemType> *p;
S.push (m_root); //根指针进栈

while (!S.empty ()) {
p = S.top ();

while (p) {
p = p->lchild;
S.push(p); // 向左走到尽头
}

S.pop(); // 空指针退栈

if (!S.empty()){ // 访问结点,向右一步
p = S.top ();
S.pop();
visit(p->data);
S.push(p->rchild);
}
}
}

// 后序遍历二叉树的非递归算法(利用栈)
template <class ElemType>
void BinaryTree<ElemType> ::PostorderTraverseNonRecursive(void (*visit)(const ElemType &e))
{
stack<BTNode<ElemType> *> S;
BTNode<ElemType> *p,*q = NULL;
S.push (m_root); //根指针进栈

while (!S.empty ()) {
p = S.top ();

while (p) {
p = p->lchild;
S.push(p); // 向左走到尽头
}

S.pop(); // 空指针退栈

if (!S.empty()){
p = S.top ();
if ( p->rchild )
S.push ( p->rchild );
else {
visit ( p->data );
S.pop();
if (!S.empty())
q = S.top ();
while ( q && q->rchild == p ) {
visit ( q->data );
p = q;
S.pop();
q = NULL;
if (!S.empty())
q = S.top ();
}
S.push ( NULL );
}//else
}//if
}//while
}

// 层次遍历二叉树的非递归算法(利用队列)
template <class ElemType>
void BinaryTree<ElemType> ::LevelTraverse(void (*visit)(const ElemType &e)){
queue<BTNode<ElemType> *> Q;

if (m_root)
Q.push (m_root);

while (!Q.empty ()){
BTNode<ElemType> *p;
p = Q.front ();
Q.pop ();

visit ( p->data );

if (p->lchild)
Q.push (p->lchild);
if (p->rchild)
Q.push (p->rchild);
}
}本回答被提问者采纳