A. 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法
//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;
void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}
}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;
createBTree(&(*tree)->left);
createBTree(&(*tree)->right);
}
}
void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}
void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}
visitBTree(q);
}
}
B. 已知二叉树采用二叉链表存储，编写算法实现层次遍历二叉树
这是我以前写的程序，包含了前序中序后序 层次便利：若只需层序便利 只要把其余的删掉就行！
#include"stdafx.h"
#include<stdlib.h>
#include<math.h>
typedef structbitnode{
char data;
struct bitnode *lchild,*rchild;
}bitnode,*bitree;
typedef structqnode{
bitree data;
struct qnode *next;
}qnode;
typedef struct{
qnode * front;
qnode * rear;
}linkqueue;
intinitqueue(linkqueue &q)
{
q.front=q.rear=(qnode*)malloc(sizeof(qnode));
if(!q.front) exit(OVERFLOW);
q.front->next=NULL;
return 1;
}
intenqueue(linkqueue &q,bitree e)
{
qnode *p;
p=(qnode*)malloc(sizeof(qnode));
if(!p) exit(OVERFLOW);
p->data=e;p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
intoutqueue(linkqueue & q,bitree &e)
{ qnode *p;
if(q.front==q.rear) return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
return 1;
}
intcreatebitree(bitree &t)
{
char ch;
scanf("%c",&ch);
if(ch=='.')
t=NULL;
else{
if(!(t=(bitnode*)malloc(sizeof(bitnode))))
exit(OVERFLOW);
t->data=ch;
createbitree(t->lchild);
createbitree(t->rchild);
}
return 1;
}
int visit(char e)
{
printf("%c",e);
return 1;
}
intpreordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(visit(t->data))
if(preordertraverse(t->lchild,visit))
if(preordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intinordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(inordertraverse(t->lchild,visit))
if(visit(t->data))
if(inordertraverse(t->rchild,visit))return 1;
return 0;
}else return 1;
}
intpostordertraverse(bitree t,int (*visit)(char e))
{
if(t){
if(postordertraverse(t->lchild,visit))
if(postordertraverse(t->rchild,visit))
if(visit(t->data))
return 1;
return 0;
}else return 1;
}
voidlevelordertraverse(bitree t)
{
linkqueue q;
bitree e;
initqueue(q);
enqueue(q,t);
while(outqueue(q,e)){
if(e)
{
visit(e->data);
enqueue(q,e->lchild);
enqueue(q,e->rchild);
}
}
}
int main(int argc,char* argv[])
{
bitree t;
printf("输入字符：");
createbitree(t);
printf("输出先序遍历：");
preordertraverse(t, visit);
printf("\n");
printf("输出中序遍历：");
inordertraverse(t,visit);
printf("\n");
printf("输出后序遍历：");
postordertraverse(t,visit);
printf("\n");
printf("输出层序遍历：");
levelordertraverse(t);
printf("\n");
return 0;
}
C. 设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
按层次遍历算法如下：
#include <iostream>
using namespace std;
typedef struct treenode { //树结点结构
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;
typedef struct stack{ //栈结点结构
TreeNode *node;
struct stack *next;
}STACK;
void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根结点入栈
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //栈顶结点的左结点入栈
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}
if (head->node->right != NULL) //栈顶结点的右结点入栈
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //结点出栈
temp = head;
head = head->next;
delete(head);
}
}
D. 建立二叉树的二叉链表表示，实现二叉树的先序、中序、后序和按层次遍历，统计并输出结点个数。
以下是程序代码，里面还包括求树的深度和叶子，已经运行通过了。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode; //自定义二叉树的结点类型
typedef BTNode *BTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNUm为结点数，leaf为叶子数
BTree CreatBTree(void)
{BTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BTNode *)malloc(sizeof(BTNode));//生成结点
T->data=ch;
T->lchild=CreatBTree();//构造左子树
T->rchild=CreatBTree();//构造右子树
return(T);
}
}
void Preorder(BTree T) //先序遍历
{
if(T){
printf("%c",T->data);//访问结点
Preorder(T->lchild);//先序遍历左子树
Preorder(T->rchild);//先序遍历右子树
}
}
void Inorder(BTree T)//中序遍历
{
if(T)
{
Inorder(T->lchild);//中序遍历左子树
printf("%c",T->data);//访问结点
Inorder(T->rchild);//中序遍历右字树
}
}
void Postorder(BTree T)//后序遍历
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
int TreeDepth(BTree T)//后序遍历求二叉树的深度，结点数和叶子数
{
int hl,hr,max;
if(T)
{
hl=TreeDepth(T->lchild);//求左深度
hr=TreeDepth(T->rchild);//求右深度
max=hl>hr?hl:hr;//取左右深度的最大值
NodeNum=NodeNum+1;//求结点数
if(hl==0&&hr==0)
leaf=leaf+1;
return(max+1);
}
else return(0);
}
void Levelorder(BTree T)//层次遍历二叉树
{
int front=0,rear=1;
BTNode *cq[Max],*p;//定义结点的指针数组cq
cq[1]=T;//根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front];//出队
printf("%c",p->data);//出队，输出结点的值
if(p->lchild!=NULL)
{rear=(rear+1)%NodeNum;
cq[rear]=p->rchild;//右子树入队
}
}
}
void main()
{
BTree root;
int i,depth;
printf("\n");
printf("创建二叉树，请输入完全二叉树的先序序列，用#代表虚结点:");
root=CreatBTree();//返回根结点
do{
printf("********************SELECT********************\n");
printf("\t1:先序遍历\n");
printf("\t2:中序遍历\n");
printf("\t3:后序遍历\n");
printf("\t4:深度、结点数、叶子数\n");
printf("\t5:层次遍历\n");
printf("备注：选择层次遍历之前，需要先选择4，求出该树的结点数。");
printf("\t0:Exit\n");
printf("\t*********************************************\n");
scanf("%d",&i);//输入菜单序号
switch(i)
{
case 1:printf("先序遍历结果为:");
Preorder(root);
break;
case 2:printf("中序遍历结果为:");
Inorder(root);
break;
case 3:printf("后序遍历结果为:");
Postorder(root);
break;
case 4:depth=TreeDepth(root);
printf("深度=%d 结点数=%d",depth,NodeNum);
printf("叶子数=%d",leaf);
break;
case 5:printf("层次遍历为:");
Levelorder(root);
break;
default:exit(1);
}
printf("\n");
}
while(i!=0);
}
E. 二叉树以二叉链表方式存储,以后序遍历或层次遍历的方式求各结点中最大元素的值
以下的函数以后序遍历的方法求解
void findMax(BtNode *root, int &maxValue)
{
if(root == NULL)
{
return; // 若当前节点指针为空，则直接返回
}
findMax(root->leftChild, maxValue); // 先遍历左子树
findMax(root->rightChild, maxValue); // 再遍历右子树
if(maxValue < root->data)
{
maxValue = root->data; // 将当前节点的值与maxValue比较，如果大于maxValue，则将maxValue改为当前节点的值
}
}
F. 二叉树的链式存储结构的数据结构定义、创建、先序和后序遍历，并将结果序列输出。
1、建立一个单链表，并从屏幕显示单链表元素列表。
2、从键盘输入一个数，查找在以上创建的单链表中是否存在该数;如果存在，显示它的位置;如果不存在，给出相应提示。
3、在上述的单链表中的指定位置插入指定的元素
4、删除上述单链表中指定位置的元素。
源程序：头文件
#include<iostream.h>
#include<malloc.h>
typedef char ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct LNode{
ElemType data;
LNode *next;
}LNode,*LinkList;
void about(){ //版本信息
cout<<"单链表的操作"
}
void showmenu(){ //功能列表
cout<<endl <<" **********功能**********"<<endl
<<" * 1.输出单链表的全部数据*"<<endl
<<" * 2.查找链表元素 *"<<endl
<<" * 3.链表插入元素 *"<<endl
<<" * 4.链表删除元素 *"<<endl
<<" * 5.结束 *"<<endl
<<" ************************"<<endl
<<"请输入所需功能: ";
}
//*******查看输入的全部数据*********
void PrintList(LinkList L){
LinkList p;
cout<<endl<<"你输入的数据为: ";
p=L->next; //从头结点开始扫描
while(p){ //顺指针向后扫描，直到p->next为NULL或i=j为止
cout<<p->data;
p=p->next; }
cout<<endl; }
//逆序输入 n 个数据元素，建立带头结点的单链表
void CreateList_L(LinkList &L, int n) {
int i;
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
cout<<"逆序输入 n 个数据元素，建立带头结点的单链表"<<endl;
for (i = n; i > 0; --i) {
p = new LNode;
cin>>p->data; // 输入元素值
p->next = L->next; L->next = p; // 插入
}
}
// L是带头结点的链表的头指针，以 e 返回第 i 个元素
Status GetElem_L(LinkList L, int i, ElemType &e) {
int j;
LinkList p;
p = L->next; j = 1; // p指向第一个结点，j为计数器
while (p && j<i) { p = p->next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空
if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;
}
// 本算法在链表中第i 个结点之前插入新的元素 e
Status ListInsert_L(LinkList L, int i, ElemType e) {
int j;
LinkList p,s;
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于1
s = new LNode; // 生成新结点
if ( s == NULL) return ERROR;
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
}
Status ListDelete_L(LinkList L, int i, ElemType &e)
{LinkList p,q;
int j;
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 寻找第 i 个结点，并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; free(q);
return OK;
}
#include"LinkList.h"
void main()
{LinkList L;
int n,choice,i;
ElemType e;
about();
cout<<"请输入链表中元素的个数";
cin>>n;
CreateList_L(L, n);
showmenu(); //功能列表
cin>>choice;
while(choice!=5)
{ //输入时候退出程序
switch(choice){
case 1:PrintList(L);break; //1.查看输入的全部数据
case 2:{
cout<<"输入你要查找的元素的位置： ";
cin>>i;GetElem_L(L, i, e);
cout<<"第"<<i<<"个元素的值是"<<e<<endl;
break;} //2.查找链表元素
case 3:
{cout<<"请输入你要插入元素的位置i： ";
cin>>i;
cout<<endl<<"请输入你要插入元素的值： ";
cin>>e;
ListInsert_L(L, i,e);
break;} //3.链表插入元素
case 4:
{cout<<"请输入你要删除元素的位置";
cin>>i;
ListDelete_L(L, i, e) ;
break;} //4.链表删除元素
default:cout<<"输入错误,请输入-5,输入重显示功能表^_^ "<<endl;
}
cout<<endl<<"输入功能序号:";
cin>>choice;
}
}
G. 建立一棵二叉树，输出该二叉树的前序遍历、中序遍历和后序遍历以及层序遍历，并实现对结点全职的查找。
template <class T>
struct BiNode //二叉树的结点结构
{
T data;
BiNode<T> *lchild, *rchild;
};
template <class T>
struct element
{
BiNode<T> *ptr;
int flag;
};
template <class T>
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间
BiNode<T>* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode<T> *root); //前序遍历二叉树
void InOrder(BiNode<T> *root); //中序遍历二叉树
void PostOrder(BiNode<T> *root); //后序遍历二叉树
void LeverOrder(BiNode<T> *root); //层序遍历二叉树
BiNode<T> * Find(BiNode<T> *&root,T item) ;//查找结点
private:
BiNode<T> *root; //指向根结点的头指针
BiNode<T> *Creat(); //有参构造函数调用
void Release(BiNode<T> *root); //析构函数调用
};
template<class T>
BiTree<T>::BiTree()
{
this->root = Creat();
}
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"请输入创建一棵二叉树的结点数据"<<endl;
cin >> ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一个结点
root->data=ch;
root->lchild = Creat(); //递归建立左子树
root->rchild = Creat(); //递归建立右子树
}
return root;
}
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
template <class T>
void BiTree<T>::PreOrder(BiNode<T> *root) //前序遍历
{
if (root == NULL) return;
else {
cout << root->data << ' ';
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
template <class T>
void BiTree<T>::InOrder(BiNode<T> * root) //中序遍历
{
if (root == NULL) return;
else {
InOrder(root->lchild);
cout << root->data << " ";
InOrder(root->rchild);
}
}
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root) //后续遍历
{
if (root == NULL) return;
else
{
PostOrder(root->lchild);
PostOrder(root->rchild);
cout << root->data << " ";
}
}
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root) //层序遍历
{
const int MaxSize = 100;
int front = 0;
int rear = 0;
BiNode<T>* Q[MaxSize];
BiNode<T>* q;
if (root == NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<< q->data << " ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}
template<class T>
BiNode<T> * BiTree::Find(BiNode<T> *&root,T item) //查找data为item的结点
{
if(root==NULL) return NULL;
if(Root->data==item) return root;
BiNode<T> *p;
if((p=Find(root->lchild,item))!=NULL) return p;
if((p=Find(root->rchild,item))!=NULL) return p;
return NULL;
}