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. 二叉鏈表存儲樹，根結點的右指針是空嗎怎麼不是指向最右孩子
以二叉鏈表作樹的存儲結構，即用孩子兄弟表示法來表示樹，鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點，根結點沒有兄弟結點，所以右指針是空的