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. 樹的鏈式存儲結構中每個結點的結構類型主要有哪兩種形式
覺得應該是比較多的