A. 树的存储结构
常用的有：1、双亲表示，2、孩子链表表示，3、双亲孩子链表表示，4、孩子兄弟链表表示
B. 设二叉树bt存储结构如下
字符a是根结点,a的左分支是b,而a没有右分支.
二叉树示意图:
a
/
b
/
cd
//
efg
//
hi
/
j
二叉树的(链式)逻辑结构示意图:
#a^
/
#b#
/
#c^#d#
//
^e^#f^#g^
//
^h^#i^
/
^j^
上述示意图,符号#表示指针域,符号^表示NULL(空指针)
先序遍历序列:abcedfhgij
中序遍历序列:ecbhfdjiga
后序遍历序列:echfjigdba
//C语言测试程序
#include"stdio.h"
#include"stdlib.h"
structtree
{
chardata;
structtree*left;
structtree*right;
};
typedefstructtreetreenode;
typedeftreenode*btree;
btreecreatebtree(char*data,intpos,intmaxPos)//递归创建法
{
btreenewnode;
if(data[pos]==0||pos>maxPos)
{
returnNULL;
}
else
{
newnode=(btree)malloc(sizeof(treenode));
newnode->data=data[pos];
newnode->left=createbtree(data,2*pos,maxPos);
newnode->right=createbtree(data,2*pos+1,maxPos);
returnnewnode;
}
}
voidpreorder(btreeptr)//先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%C",ptr->data);
preorder(ptr->left);
preorder(ptr->right);
}
}
voidinorder(btreeptr)//中序遍历(递归法)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%C",ptr->data);
inorder(ptr->right);
}
}
voidpostorder(btreeptr)//后序遍历(递归法)
{
if(ptr!=NULL)
{
postorder(ptr->left);
postorder(ptr->right);
printf("%C",ptr->data);
}
}
intmain()
{
btreeroot=NULL;
inti;
chardata[64]={0,'a','b',0,'c','d',0,0,
'e',0,'f','g',0,0,0,0,
0,0,0,0,'h',0,'i',0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,'j',0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0};
root=createbtree(data,1,63);
printf("二叉树的顺序存储内容:");
for(i=1;i<64;i++)
{
if(data[i]==0)
{
printf("^");
}
else
{
printf("%c",data[i]);
}
}
printf(" 二叉树的先序遍历序列:");
preorder(root);
printf(" 二叉树的中序遍历序列:");
inorder(root);
printf(" 二叉树的后序遍历序列:");
postorder(root);
printf(" ");
return0;
}
C. 数据结构，树的常用存储方式
存入文本文件，每行：孩子节点-父节点。
这样也方便用Hadoop进行处理。
D. 设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换
1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根结点地址*/
}
void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}
如果还没解决你的问题，可以加我网络HI账号。
E. 树的存储结构转换
//声明树中的类以及结点结构，文件名为tree.h
#ifndef TREE_H
#define TREE_H
template <class T>//树中结点采用孩子兄弟表示法
struct TNode
{
T data;
TNode<T> *firstchild, *rightsib;
};
template <class T>
class Tree
{
public:
Tree( ); //构造函数，初始化一棵树，其前序序列由键盘输入
~Tree(void); //析构函数，释放树中各结点的存储空间
TNode<T>* Getroot( ); //获得指向根结点的指针
void PreOrder(TNode<T> *root); //前序遍历树
void PostOrder(TNode<T> *root); //后序遍历树
void LeverOrder(TNode<T> *root); //层序遍历树
private:
TNode<T> *root; //指向根结点的头指针
void Release(TNode<T> *root); //析构函数调用
};
#endif
//定义类中的成员函数，文件名为tree.cpp
#include<iostream>
#include<string>
#include"tree.h"
using namespace std;
/*
*前置条件：树不存在
*输 入：无
*功 能：构造一棵树
*输 出：无
*后置条件：产生一棵树
*/
template<class T>
Tree<T>::Tree( )
{
const int MaxSize = 100;
int end = 0;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
int j = 0;
TNode<T>* queue[MaxSize]; //声明一个队列
TNode<T>* tempNode; //声明指向结点类型的指针
TNode<T>* brotherNode; //工作指针
TNode<T>* q;
T ch;
cout<<"请输入创建一棵树的根结点数据"<<endl;
cin>>ch;
root = new TNode<T>;
root->data = ch;
root->firstchild = NULL;
root->rightsib = NULL;
queue[rear++] = root;
while (!end) //若继续创建树
{
T ch1,ch2;
cout<<"请输入创建一棵树的父结点数据和孩子结点数据"<<endl;
cin>>ch1>>ch2;
TNode<T>* p = new TNode<T>; //生成一个结点
p->data = ch2;
p->firstchild = NULL;
p->rightsib = NULL;
queue[rear++] = p;
tempNode = queue[front];//头结点出队，同时对头元素的标识符后移
while(ch1 != tempNode->data)
tempNode = queue[front++];
if(tempNode->firstchild == NULL) tempNode->firstchild = p;
else{
brotherNode = tempNode->firstchild; //工作指针指向结点的第一个孩子
while (brotherNode != NULL) //若第一个孩子有兄弟结点
{
q = brotherNode;
brotherNode = brotherNode->rightsib;//工作指针指向第一个孩子的右兄弟
}
q->rightsib = p;
}
cout<<"创建结束? 如果结束请按1否则请按0 "<<endl;
cin>>end;
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：释放树中各结点的存储空间
*输 出：无
*后置条件：树不存在
*/
template<class T>
Tree<T>::~Tree(void)
{
Release(root);
}
/*
*前置条件：树已存在
*输 入：无
*功 能：获取指向树根结点的指针
*输 出：指向树根结点的指针
*后置条件：树不变
*/
template<class T>
TNode<T>* Tree<T>::Getroot( )
{
return root;
}
/*
*前置条件：树已存在
*输 入：无
*功 能：前序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::PreOrder(TNode<T> *root) //前序遍历树
{
if (root == NULL) return; //递归调用的结束条件
else{
cout<<root->data; //打印根节点
PreOrder(root->firstchild); //前序递归遍历root的第一个孩子
PreOrder(root->rightsib); //前序递归遍历root的右兄弟
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：后序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::PostOrder(TNode<T> *root)
{
if (root == NULL) return; //递归调用的结束条件
else{
PostOrder(root->firstchild); //后序递归遍历root的第一个孩子
cout<<root->data; //打印出root结点
PostOrder(root->rightsib); //后序递归遍历root的右兄弟
}
}
/*
*前置条件：树已存在
*输 入：无
*功 能：层序遍历树
*输 出：树中结点的一个线性排列
*后置条件：树不变
*/
template<class T>
void Tree<T>::LeverOrder(TNode<T> *root)
{
const int MAX_QUEUE_SIZE = 100;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
TNode<T>* queue[MAX_QUEUE_SIZE]; //声明一个队列
TNode<T>* tempNode; //声明指向结点类型的指针
TNode<T>* brotherNode; //工作指针
if (root == NULL) return;//循环结束条件
queue[rear++] = root; //否则结点入队
while (front != rear) //若队列中有结点
{
tempNode = queue[front++];//头结点出队，同时对头元素的标识符后移
cout<<tempNode->data; //打印出头结点
brotherNode = tempNode->firstchild; //工作指针指向结点的第一个孩子
while (brotherNode != NULL) //若第一个孩子有兄弟结点
{
queue[rear++] = brotherNode; //第一个孩子结点入队
brotherNode = brotherNode->rightsib;//工作指针指向第一个孩子的右兄弟
}
}
}
/*
*前置条件：树已经存在
*输 入：无
*功 能：释放树的存储空间，析构函数调用
*输 出：无
*后置条件：树不存在
*/
template <class T>
void Tree<T>::Release(TNode<T>* root)
{
if (root != NULL){
Release (root->firstchild); //释放第一个孩子
Release (root->rightsib); //释放右兄弟
delete root;
}
}
//有关树的实现的主函数，文件名为treemain.cpp
#include <iostream>
#include <string>
#include"tree.cpp"
using namespace std;
void main()
{
Tree<string> t; //创建一棵树
TNode<string>* p = t.Getroot( ); //获取指向根结点的指针
cout<<"------前序遍历------ "<<endl;
t.PreOrder(p);
cout<<endl;
cout<<"------后序遍历------ "<<endl;
t.PostOrder(p);
cout<<endl;
cout<<"------层序遍历------ "<<endl;
t.LeverOrder(p);
cout<<endl;
}
F. 数据结构中的二叉树题目,求大神帮忙做下,谢谢!
设二叉树bt的一种存储结构如表所示。其中，bt为树根结点指针，lchild、rchild分别为结点的左、右孩子指针域，使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成：（1）画出二叉树bt的树形表示。（2）写出按先序、中序和后序遍历二叉树bt所得到的结点序列。
G. 树的存储结构的问题
a是根节点，没有parent，parent置为-1，b和c是a的子节点，所以b和c的parent中是的a所在的位置0，后面类似。
H. 如何根据二叉树存储结构表构造二叉树，表中含左右孩子指针域，结点数据域。
typedef struct node
{char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *creat( )
{
printf(“i,x=”);
scanf(“%d,%d”,&i,&x);
while((i!=0)&&(x!=0))
{
q=new BTNode;
q->data=x; q->lchild=null;
q->rchild=null;
s[i]=q;
if(i==1)
t=q;
else
{
j=i/2;
if (i%2==0)
s[j]->lchild=q;
else s[j]->rchild=q;}
printf(“i,x=”);
scanf(“%d%d”,&i,&x);}
return(t);
}
}
I. 树的链式存储结构中每个结点的结构类型主要有哪两种形式
觉得应该是比较多的