二叉树操作
const int MaxSize=30;
BTreeNode* q[MaxSize];
int front=0,rear=0;
BTreeNode* p;
if(BT!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=BT;
}
while(front!=rear){
front=(front+1)%MaxSize;
p=q[front];
coutdata<<' ';
if(p->left!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=p->left;
}
if(p->right!=NULL){
rear=(rear+1)%MaxSize;
q[rear]=p->right;
}
}
#include
#include
#include
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//基于先序遍历算法创建二叉树
//要求输入先序序列，其中加入虚结点"#"以示空指针的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//先序遍历
void Preorder(BinTree T){
if(T){
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//中序遍历
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//后序遍历
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法
int TreeDepth(BinTree 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; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//主函数
void main(){
BinTree root;
int i,depth;
printf("
");
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do{ //从菜单中选择遍历方式，输入序号。
printf("********** select ************
");
printf("1: Preorder Traversal
");
printf("2: Iorder Traversal
");
printf("3: Postorder traversal
");
printf("4: PostTreeDepth,Node number,Leaf number
");
printf("0: Exit
");
printf("*******************************
");
scanf("%d",&i); //输入菜单序号（0-4）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("
");
}while(i!=0);
}
//按层遍历
Levelorder( BinTNode *root){
BinTNode * q[Max]; //定义BinTNode类型的队列 用于存放节点 队列长最大为20个元素
int front=0,rear=0; //初始化队列为空
BinTNode *p; //临时节点指针
if(root!=NULL){ //将根节点进队
rear=(rear+1)%Max;
q[rear]=root;
}
while(front!=rear){
front=(front+1)%Max;
p=q[front]; //删除队首的元素 让两个节点（左右节点）孤立
printf("%c",p->data); //输出队列首元素的值
if(p->left!=null){ //如果存在左孩子节点，则左孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->left;
}
if(p->right!=null){ //如果存在右孩子节点，则右孩子节点进入队列
rear=(rear+1)%Max;
q[rear]=p->right;
}
}
}
源文件名：P3.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>
#include <stack>
using namespace std;
typedef int DataType;
const max=100;
typedef struct
{ DataType data[max];
int top;
}SeqStack;
struct BiTNode //二叉树结点类型
{
int data; //数据
int tem1,tem2; //辅助数据（实习题不用）
BiTNode *left; //左子树指针
BiTNode *right; //右子树指针
};
BiTNode *Tree; //本程序操作的二叉树根指针
int elem[max]; //存放原始数据
//从键盘输入个数和随机数种子，在数组elem中生成指定个数的数据，供其他程序使用，0表示数据结束
void init0(int list[]);
//在本程序所在的位置生成文本文件Map.txt，其中显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree);
//从键盘输入个数和随机数种子，以Tree为根指针，生成指定结点个数的二叉树，供其他程序使用
BiTNode *init1();
//主函数，显示功能菜单（包括生成二叉树、显示二叉树），键盘选择后执行对应功能
void Preorder(BiTNode *Tree);//先序遍历
void Inorder(BiTNode *Tree); //中序遍历
void Postorder(BiTNode *Tree); //后序遍历
int leafs(BiTNode *Tree); //总叶子数
void swap(BiTNode *Tree); //交换左右子树
int depth(BiTNode *Tree); //计算二叉树的深度
void search(BiTNode *T); //查找结点
BiTNode *CreatBST(int A[],int n) ;/
void insert(BiTNode *Tree);
int ELEM(int A[]);/
void del(BiTNode *Tree);/
void preorderl(BiTNode *Tree);/
void main()
{
//int list[max];
char choice;
while (1)
{
system("cls");
cout << "\n\n\n\n";
cout << "\t\t 二叉树操作 \n";
cout << "\t\t======================================";
cout << "\n\n";
cout << "\t\t a：生成二叉树 \n";
cout << "\t\t b：显示 \n";
cout << "\t\t c：先序遍历 \n";
cout << "\t\t d：中序遍历 \n";
cout << "\t\t e：后序遍历 \n";
cout << "\t\t f：计算二叉树中叶子结点的数目 \n";
cout << "\t\t g：计算二叉树的深度 \n";
cout << "\t\t h：左、右子树相互交换 \n";
cout << "\t\t i：构建以Tree为根指针的二叉排序树 \n";
cout << "\t\t j：查找结点 \n";
cout << "\t\t k：删除结点 \n";
cout << "\t\t l：不用递归，先序遍历以Tree为根指针的二叉树。 \n";
cout << "\t\t m：凹入表示法的表示以Tree为根指针的二叉树 \n";
cout << "\t\t n：用广义表表示以Tree为根指针的二叉树 \n";
cout << "\t\t o：从根结点开始，逐层从左到右输出各结点的数据 \n";
cout << "\t\t p：生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度 \n";
cout << "\t\t 0：退出 \n";
cout << "\n";
cout << "\t\t请选择：" << flush;
choice = getch();
system("cls");
switch(choice)
{
case 'a':
Tree=init1();
break;
case 'b':
showBinTree(Tree);
break;
case 'c':
cout<<"先序遍历："<<endl;
Preorder(Tree);
cout <<flush;
getch();
break;
case 'd':
cout<<"中序遍历："<<endl;
Inorder(Tree);
cout <<flush;
getch();
break;
case 'e':
cout<<"后序遍历："<<endl;
Postorder(Tree);
cout <<flush;
getch();
break;
case 'f':
cout<<"二叉树的总叶子结点数为："<<leafs(Tree)<<endl;
cout <<flush;
getch();
break;
case 'g':
cout<<"二叉树的深度为："<<depth(Tree)<<endl;
cout <<flush;
getch();
break;
case 'h':
swap(Tree);
cout<<"交换成功！"<<endl;
showBinTree(Tree);
cout <<flush;
getch();
break;
case 'i':
init0(elem);
Tree=CreatBST(elem,ELEM(elem));
break;
case 'j':
cout<<"请输入要查找的元素：";
search(Tree);
cout <<flush;
getch();
break;
case 'k':
cout<<"请输入需要删除的元素：";
del(Tree);
Tree=CreatBST(elem,ELEM(elem));
showBinTree(Tree);
cout <<flush;
getch();
break;
case 'l':
break;
case 'm':
break;
case 'n':
break;
case 'o':
break;
case 'p':
break;
case 'q':
break;
case 'r':
break;
case '0':
exit(0);
}
}
}
#include "BinT.h"
//公用的等待函数
void wait()
{
cout << "\n\n请按任意键继续" << flush;
getch();
}
void Preorder(BiTNode *T)//先序遍历
{
if(T)
{
cout<<T->data<<" ";
Preorder(T->left);
Preorder(T->right);
}
}
void Inorder(BiTNode *T)//中序遍历
{
if(T)
{
Inorder(T->left);
cout<<T->data<<" ";
Inorder(T->right);
}
}
void Postorder(BiTNode *T)//后序遍历
{
if(T)
{
Postorder(T->left);
Postorder(T->right);
cout<<T->data<<" ";
}
}
int leafs(BiTNode *T)//总叶子数
{
if(T==NULL)
return 0;
if((T->left==NULL) && (T->right==NULL))
return 1;
else
return leafs(T->left) + leafs(T->right);
}
int depth(BiTNode *T)//计算二叉树的深度
{
int n1,n2;
if(!T)
return 0;
else
{
n1=depth(T->left);
n2=depth(T->right);
if(n1>n2)
return n1+1;
else
return n2+1;
}
}
void swap(BiTNode *T)//交换左右子树
{
BiTNode *Q;
if(T)
{
Q = T->left ;
T->left = T->right ;
T->right = Q;
swap(T->left);
swap(T->right);
}
}
int InsertBST(BiTNode *&T,int k)
{
if (T==NULL)
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=k;
T->left=T->right=NULL;
return 1;
}
else if (k==T->data)
return 0;
else if (k<T->data)
return InsertBST(T->left,k);
else
return InsertBST(T->right,k);
}
BiTNode *CreatBST(int A[],int n)
{
BiTNode *bt=NULL;
int i=0;
while (i<n)
{
InsertBST(bt,A[i]);
i++;
}
return bt;
}
void search(BiTNode *T)//查找结点
{
int x,count=0;
cin>>x;
while(T!=NULL)
{
if(T->data==x)
{
count++;break;
}
else if(x<T->data)
{
T=T->left;
}
else
{
T=T->right;
}
}
if(count>0)
{
cout<<"查找到该元素。"<<endl;
}
else
{
cout<<"不存在该元素。"<<endl;
}
}
int ELEM(int A[])
{
int i;
for(i=0;elem[i]!=0;i++);
return i;
}
void del(BiTNode *T)
{
int x,i=0,j=-1;
cin>>x;
for(i;elem[i]!=0;i++)
{
if(elem[i]==x)
{
j=i;break;
}
}
if(j>=0)
{
for(j;elem[j]!=0;j++)
{
elem[j]=elem[j+1];
}
cout<<"删除成功。"<<endl;
}
else
{
cout<<"删除元素不存在。"<<endl;
}
}
void preorderl(BiTNode T) //不用递归，先序遍历以Tree为根指针的二叉树
{
SeqStack s;
s.top= -1;
while(T||s.top!= -1) //当前处理的子树不为空或栈不为空则循环
{
while(T)
{printf(“%c”,T->data);
s.top++;
s.data[s.top]=T;
T=T->left;
}
If(s.top>-1)
{T=pop(&s);
T=T->right;
}
}
}
/*
2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树。
3、编写递归算法，计算二叉树中叶子结点的数目。
4、编写递归算法，计算二叉树的深度。
5、编写递归算法，将二叉树中所有结点的左、右子树相互交换。
6、使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树。
7、在以Tree为根指针的二叉排序树中查找结点。
8、从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）。
9、不用递归，先序遍历以Tree为根指针的二叉树。
提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能。
10、用凹入表示法的表示以Tree为根指针的二叉树，例如：
// 324
// 123
// 746
// 690
// 567
11、用广义表表示以Tree为根指针的二叉树，例如
// (324(123(746(),()),(690(),())),(567(),()))
12、对以Tree为根指针的二叉树，从根结点开始，逐层从左到右输出各结点的数据。
提示：用数组 BiTNode *queue[max] 构成队列，利用这个队列实现功能
提高题：
13*、根据Huffman编码原理，使用数组elem中的随机数序列（以0表示结束，不包括0）作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。
14*、（1）随机生成二叉树。 （2）生成并保存先（后）序、中序输出序列。 （3）按照保存的一对输出序列恢复出二叉树。（4）生成先（后）序输出序列。
*/
推荐你看下严蔚敏的数据结构，上面的算法都有。
二叉树怎么操作?
答：（1）以先序递归遍历思想建立二叉树。①建立二叉树的根结点；②先序建立二叉树的左子树；③先序建立二叉树的右子树。（2）构造二叉树的操作算法。输入一个二叉树的先序序列，构造这棵二叉树。为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊...
在二叉排序树上进行插入、查找及删除等操作?
答：对于插入操作，我们需要首先遍历二叉排序树，找到插入节点的位置。具体步骤如下：如果二叉排序树为空，则新节点成为根节点 如果插入节点的值等于当前节点的值，则插入失败，结束操作 如果插入节点的值小于当前节点的值，则在左子树中继续查找插入位置 如果插入节点的值大于当前节点的值，则在右子树中继续查找...
二叉树的操作及其应用:1、以二叉链表作存储结构,试编写前序、中序...
答：{ // 操作结果：构造空二叉树T T=NULL;} void CreateBiTree(BiTree &T){ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改 int number;scanf("%d",&number); // 输入结点的值 if(number==Nil...
二叉树操作
答：5、编写递归算法,将二叉树中所有结点的左、右子树相互交换。 6、使用数组elem中的随机数序列(以0表示结束,不包括0),生成以Tree为根指针的二叉排序树。 7、在以Tree为根指针的二叉排序树中查找结点。 8、从以Tree为根指针的二叉排序树中删除结点(适用各种位置的结点)。 9、不用递归,先序遍历以Tree为根指针的...
数据结构二叉树的基本操作~~~
答：1．以二叉链表表示二叉树，建立一棵二叉树；2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果；4．输出二叉树的后序遍历结果；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；7．计算二叉树的深度。8．交换二叉树每个结点的左孩子和右孩子；include <malloc.h> include <stdio.h...
二叉树的遍历
答：．先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( ) 访问根结点 ( ) 遍历左子树 ( ) 遍历右子树 ．后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )遍历右子树 ( )访问根结点 ．中序遍历的算法实现 用二叉链表做为存储结构 中序遍历算法可描述为 ...
二叉树的遍历
答：1．遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作： （1）访问结点本身(N)， （2）遍历该结点的左子树(L)， （3）遍历该结点的右子树(R)。以上三种操作有六种执行次序： NLR、LNR、LRN、NRL...
树和二叉树的运行与操作
答：首先，提供个满二叉树大小的数组，然后其中数值按完全二叉树存储。显然，此种顺序存储方法：第i号（这里编号指对应的完全二叉树的位序）结点的左右孩子一定保存在第2i及2i+1号单元中。故此，为兼顾存储的直观与遍历等操作的方便，从顺序数组向左右子节点存储方式的转化也就十分重要。1-转化方法 分为几...
二叉树遍历演示
答：（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如...
二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上...
答：a. 若其左孩子不为空,则将p入栈,并将p的左孩子设置为当前的p,然后对当前结点再进行相同的操作; b. 若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的p置为栈顶结点的右孩子; c. 直到p为空并且栈为空,则遍历结束。 //中序非递归遍历二叉树int NoInOrderTraverse(BiTree t) ...
