A. 假设树的存储结构采用孩子兄弟表示法,写出树的先序遍历算法。该算法的函数头为: voidPreOrderTree(
以下两种描述形式之一均可:
void PreOrderTree(TNode *root, void (*Visit)())
{ p= root; if(p){Visit(p-> data);
PreOrderTree(p- > firstchild);
PreOrderTree(p-> nextsibling) ;}}
或者:
void PreOrderTree(TNode*root, void ( * Visit)())
{ p= root;
while(p | | ! StackEmpty(s)){
while(p) {Visit(p- > data) ;Push(s,p) ;p=p- > firstchild;}
p= Pop(s);p= p-> nextsibling;}}
(1)树孩子兄弟链表存储结构扩展阅读
孩子兄弟表示法,采用的是链式存储结构,其存储树的实现思想是:从树的根节点开始,依次用链表存储各个节点的孩子节点和兄弟节点。
因此,该链表中的节点应包含以下 3 部分内容:
1、节点的值;
2、指向孩子节点的指针;
3、指向兄弟节点的指针;
用 C 语言代码表示节点结构为:
#define ElemType char
typedef struct CSNode{
ElemType data;
struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;
B. 树采用孩子兄弟链表来表示,编写算法,统计树中结点总数
孩子兄弟表示法是一颗二叉树,其左孩子为原树的孩子,右孩子是其兄弟
若有树表示为
typedef
struct
BiTNode
{
int
data;
struct
BiTNode
*lchild,*rchild;
}BiTNode,*BTree;
那么,统计结点总数
int
fun(BTree
tree)
{
if(tree)//树非空时候
return
fun(tree->lchild)+fun(tree->rchild)+1;
else
return
0;//否则返回0
}
C. 树的存储结构转换
//声明树中的类以及结点结构,文件名为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;
}
D. 编写计算树中每一个结点的度,树用孩子-兄弟表示的二叉链表存储
typedef struct CSNode
{
ElemType data;int degree;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
void Degree(CSTree T, int &d)
{
if(T != NULL)
{
if(T->firstchild != null)
{
p = T->firstchild;
n = 1;
while(p->nextsibling != NULL)
{
p = p->nextsibling;
n++;
}
T->degree=n;
}
Degree(T->firstchild, d+1);
Degree(T->nextsibling, d);
}
}
E. 树的孩子兄弟表示法实例(C++实现的)}
孩子兄弟表示法
树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法。每个结点除了data域外,还含有两个域,分别指向该结点的最左儿子和右邻兄弟。这种表示法常用二叉链表实现,因此又称为二叉链表表示法。若用指针实现,其类型定义为:
typedef
NodeType
*TPosition;
struct
NodeType
ElemType
data;
TPosition
Leftmost_Child,Right_Sibling;
}
用树的左儿子右兄弟表示法可以直接实现树的大部分操作,只有在对树结点作Parent操作时需遍历树。如果要反复执行Parent操作,可在结点记录中再开辟一个指向父结点的指针域,也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针)。当执行Parent(v)时,可以先通过Right_Sibling逐步找出结点v的最右兄弟,再通过最右兄弟的Right_Sibling(父亲指针)找到父结点。这个结点就是结点v的父亲。在这样的表示法下,求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数。不过,这时每个记录中需要多用一位(bit)空间,用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲。
考虑到对于现在的计算机,内存已经不是很重要的限制因素了。我们下面就采取增加一个parent域的方案,以改进左儿子右兄弟表示法中Parent操作的效率。因此重新定义树的类型如下:
typedef
NodeType
*TPosition;
struct
NodeType
ElemType
data;
TPosition
Parent,Leftmost_Child,Right_Sibling;
//增加一个Parent域
}
如果是
二叉树,还可以用
一维数组表示,父节点i(i从1开始)
,
左孩子2i,右孩子
2i+1;
F. 假设树t以孩子兄弟链表表示法为存储结构,编写一非递归算法求树中节点X的度数
14.由孩子兄弟链表表示的树,求高度的递归模型是:若树为空,高度为零;若第一子女为空,高度为1和兄弟子树的高度的大者;否则,高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列,逐层遍历树,取得树的高度。int Height(CSTree bt) //递归求以孩子兄弟链表表示的树的深度{int hc,hs; if (bt==null) return (0);elseif (!bt->firstchild) return (1+height(bt->nextsibling);//子女空,查兄弟的深度else // 结点既有第一子女又有兄弟,高度取子女高度+1和兄弟子树高度的大者{hc=height(bt->firstchild); //第一子女树高hs=height(bt->nextsibling);//兄弟树if(hc+1>hs)return(hc+1); elsereturn (hs); }}//结束heightint height(CSTree t) //非递归遍历求以孩子兄弟链表表示的树的深度{if(t==null) return(0);else{int front=1,rear=1; //front,rear是队头队尾元素的指针int last=1,h=0; //last指向树中同层结点中最后一个结点,h是树的高度Q=t; //Q是以树中结点为元素的队while(frontfirstchild) Q=t->firstchild; //第一子女入队t=t->nextsibling; //同层兄弟指针后移}if(front>last) //本层结束,深度加1(初始深度为0)h++;last=rear;} //last再移到指向当前层最右一个结}//while(front
G. 关于树的孩子兄弟存储结构
就是孩子兄弟链表中该结点的孩子构成的森林,自然是从firstchild开始
自己的高度肯定是孩子的最大高度加1
然后和兄弟的高度比较,留下最大值
H. 树的孩子链表表示法
存储结构 /*树的孩子链表存储表示*/typedefstructCTNode{//孩子节点intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata;//节点的数据元素ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//节点数和根节点的位置}CTree;
I. 二叉链表存储树,根结点的右指针是空吗怎么不是指向最右孩子
以二叉链表作树的存储结构,即用孩子兄弟表示法来表示树,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点,根结点没有兄弟结点,所以右指针是空的