Data Structure FQA
文章目錄
- 1.在實作二叉樹碰到的問題Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
- 2.二叉樹的順序存儲實作(存儲在數組中)
- 3.這個版本的二叉樹順序實作比較好了解
1.在實作二叉樹碰到的問題Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType));
Status(Visit)(TElemType)這是函數指針
本質是一個指針,該指針的位址指向了一個函數,是以它是指向函數的指針。我們知道,函數的定義是存在于代碼段,是以,每個函數在代碼段中,也有着自己的入口位址,函數指針就是指向代碼段中函數入口位址的指針。
函數指針的聲明方法為:
傳回值類型 ( * 指針變量名) ([形參清單]);
注1:“傳回值類型”說明函數的傳回類型,“(指針變量名 )”中的括号不能省,括号改變了運算符的優先級。若省略整體則成為一個函數說明,說明了一個傳回的資料類型是指針的函數,後面的“形參清單”表示指針變量指向的函數所帶的參數清單。例如:
int func(int x); /* 聲明一個函數 */
int (*f) (int x); /* 聲明一個函數指針 */
f=func; /* 将func函數的首位址賦給指針f */
或者使用下面的方法将函數位址賦給函數指針:
f = &func;
指派時函數func不帶括号,也不帶參數,由于func代表函數的首位址,是以經過指派以後,指針f就指向函數func(x)的代碼的首位址。
注2:函數括号中的形參可有可無,視情況而定。
詳細内容移步
(*visit)(TElemType e )函數指針了解
2.二叉樹的順序存儲實作(存儲在數組中)
在輸入過程中,前序序列必須輸入完整帶空結點^的序列
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* 狀态碼 */
#define TRUE 1 // 真/是
#define FALSE 0 // 假/否
#define OK 1 // 通過/成功
#define ERROR 0 // 錯誤/失敗
#define MAX_TREE_SIZE 1024
/* 狀态碼類型 */
typedef int Status;
typedef char TElemType;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
// 測試函數,列印元素
Status PrintElem(TElemType c) {
printf("%c", c);
return OK;
}
// 先序周遊的内部實作
static Status PreTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
// 越界
if(i >= MAX_TREE_SIZE) {
return ERROR;
}
if(T[i]) {
if(Visit(T[i])) {
if(PreTraverse(T, Visit, 2 * i + 1)) {
if(PreTraverse(T, Visit, 2 * i + 2)) {
return OK;
}
}
}
return ERROR;
// 遇到空樹則無需繼續計算
} else {
return OK;
}
}
// 中序周遊的内部實作
static Status InTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
// 越界
if(i >= MAX_TREE_SIZE) {
return ERROR;
}
if(T[i]) {
if(InTraverse(T, Visit, 2 * i + 1)) {
if(Visit(T[i])) {
if(InTraverse(T, Visit, 2 * i + 2)) {
return OK;
}
}
}
return ERROR;
// 遇到空樹則無需繼續計算
} else {
return OK;
}
}
// 後序周遊的内部實作
static Status PostTraverse(SqBiTree T, Status(Visit)(TElemType), int i) {
// 越界
if(i >= MAX_TREE_SIZE) {
return ERROR;
}
if(T[i]) {
if(PostTraverse(T, Visit, 2 * i + 1)) {
if(PostTraverse(T, Visit, 2 * i + 2)) {
if(Visit(T[i])) {
return OK;
}
}
}
return ERROR;
// 遇到空樹則無需繼續計算
} else {
return OK;
}
}
Status InitBiTree(SqBiTree T){
memset(T, '\0', sizeof(SqBiTree));
return 1;
}
int DestroyBiTree(SqBiTree T) {
// 二叉樹的順序存儲結構無法銷毀
return 0;
}
Status ClearBiTree(SqBiTree T) {
// 使用空字元填充二叉樹的順序結構
memset(T, '\0', sizeof(SqBiTree));
return OK;
}
// 建立二叉樹的内部函數
static void CreateTree(SqBiTree T, int i) {
char ch;
scanf("%c", &ch);
if(ch == '^') {
T[i] = '\0';
} else {
T[i] = ch;
printf("%c",T[i]);
CreateTree(T, 2 * i + 1); // 建立左子樹
CreateTree(T, 2 * i + 2); // 建立右子樹
}
}
Status CreateBiTree(SqBiTree T) {
printf("請輸入二叉樹的先序序列,如果沒有子結點,使用^代替:\n");
CreateTree(T, 0);
return OK;
}
Status BiTreeEmpty(SqBiTree T) {
return T[0] == '\0' ? 1 : 0;
}
// 求二叉樹深度的内部函數
static int TreeDepth(SqBiTree T, int i) {
int ld, rd; // 記錄左右子樹的深度
if(T[i] == '\0') {
return 0;
} else {
ld = TreeDepth(T, 2 * i + 1);
rd = TreeDepth(T, 2 * i + 2);
return (ld >= rd ? ld : rd) + 1;
}
}
int BiTreeDepth(SqBiTree T) {
return TreeDepth(T, 0);
}
Status PreOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
Status status;
status = PreTraverse(T, Visit, 0);
printf("\n");
return status;
}
/*
* 中序周遊
*/
Status InOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
Status status;
status = InTraverse(T, Visit, 0);
printf("\n");
return status;
}
/*
* 後序周遊
*/
Status PostOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
Status status;
status = PostTraverse(T, Visit, 0);
printf("\n");
return status;
}
/*
* 層序周遊
*/
Status LevelOrderTraverse(SqBiTree T, Status(Visit)(TElemType)) {
int i;
int deep;
int len;
// 二叉樹層數
deep = BiTreeDepth(T);
if(deep == 0) {
return OK;
}
// 二叉樹元素數量(最大值)
len = (int) pow(2, deep) - 1;
for(i = 0; i < len; i++) {
if(T[i] != '\0') {
if(!Visit(T[i])) {
// 如果遇到通路錯誤,會即時傳回
return ERROR;
}
}
}
printf("\n");
return OK;
}
// 傳回二叉樹結點e的索引号,i是結點p的索引号
static int EIndex(SqBiTree T, TElemType e, int i) {
int cl, cr;
// 已經越界
if(i >= MAX_TREE_SIZE) {
return -1;
}
// e的值不合規
if(e == '\0') {
return -1;
}
// 找到了元素e
if(T[i] == e) {
return i;
}
// 在左子樹中查找
cl = EIndex(T, e, 2 * i + 1);
if(cl != -1) {
return cl;
}
// 在右子樹中查找
cr = EIndex(T, e, 2 * i + 2);
if(cr != -1) {
return cr;
}
return -1;
}
// 摘下二叉樹T中的子樹i,将其插入為二叉樹R的子樹j
static void Transfer(SqBiTree T, int i, SqBiTree R, int j) {
R[j] = T[i];
if(T[i] != '\0') {
Transfer(T, 2 * i + 1, R, 2 * j + 1);
Transfer(T, 2 * i + 2, R, 2 * j + 2);
T[i] = '\0';
}
}
// 删除二叉樹T中的子樹i
static void Delete(SqBiTree T, int i) {
if(T[i] != '\0') {
T[i] = '\0';
Delete(T, 2 * i + 1);
Delete(T, 2 * i + 2);
}
}
/*
* 取值
*
* 傳回二叉樹中指定結點的值。
*/
TElemType Value(SqBiTree T, TElemType e) {
int index;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
} else {
return T[index];
}
}
/*
* 指派
*
* 為二叉樹指定的結點指派。
*/
Status Assign(SqBiTree T, TElemType e, TElemType value) {
int index;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return ERROR;
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return ERROR;
} else {
// 進行指派
T[index] = value;
return OK;
}
}
/*
* 根
*
* 傳回二叉樹的根結點。
*/
TElemType Root(SqBiTree T) {
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
return T[0];
}
/*
* 雙親
*
* 傳回二叉樹中結點e的雙親結點。
*/
TElemType Parent(SqBiTree T, TElemType e) {
int index;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
// 如果e是根結點
} else if(index == 0) {
return '\0';
} else {
// 傳回父結點
return T[(index - 1) / 2];
}
}
/*
* 左孩子
*
* 傳回二叉樹中結點e的左孩子結點。
*/
TElemType LeftChild(SqBiTree T, TElemType e) {
int index;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
} else {
// 傳回左孩子
return T[2 * index + 1];
}
}
/*
* 右孩子
*
* 傳回二叉樹中結點e的右孩子結點。
*/
TElemType RightChild(SqBiTree T, TElemType e) {
int index;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
} else {
// 傳回右孩子
return T[2 * index + 2];
}
}
/*
* 左兄弟
*
* 傳回二叉樹中結點e的左兄弟結點。
*/
TElemType LeftSibling(SqBiTree T, TElemType e) {
int index, p;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
// 如果e是根結點
} else if(index == 0) {
return '\0';
} else {
// 擷取父結點的索引
p = (index - 1) / 2;
// 如果結點e是右孩子,則傳回其左兄弟
if(T[2 * p + 2] == e) {
return T[2 * p + 1];
} else {
return '\0';
}
}
}
/*
* 右兄弟
*
* 傳回二叉樹中結點e的右兄弟結點。
*/
TElemType RightSibling(SqBiTree T, TElemType e) {
int index, p;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return '\0';
}
// 擷取結點e的索引
index = EIndex(T, e, 0);
// 如果沒有找到元素e
if(index == -1) {
return '\0';
// 如果e是根結點
} else if(index == 0) {
return '\0';
} else {
// 擷取父結點的索引
p = (index - 1) / 2;
// 如果結點e是左孩子,則傳回其右兄弟
if(T[2 * p + 1] == e) {
return T[2 * p + 2];
} else {
return '\0';
}
}
}
/*
* 插入
*
* 已知c為與T不相交的非空二叉樹,且c的右子樹為空,
* 根據LR的取值(0或1),将c插入為T中結點p的左子樹/右子樹,
* 并且,将p結點原有的左子樹/右子樹嫁接為二叉樹c的右子樹。
*/
Status InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c) {
int index;
// 如果待插入的樹為空樹則無需繼續計算
if(BiTreeEmpty(c)) {
return ERROR;
}
// 擷取結點p的索引
index = EIndex(T, p, 0);
// 如果p結點不存在,則傳回錯誤提示
if(index == -1) {
return ERROR;
}
// 将c插入為p的左子樹
if(LR==0) {
// 如果p處存在左子樹
if(T[2*index+1]!='\0') {
// 将p的左子樹插入為c的右子樹
Transfer(T, 2*index+1, c, 2);
}
Transfer(c, 0, T, 2*index+1);
// 将c插入為p的右子樹
} else {
// 如果p處存在右子樹
if(T[2*index+2]!='\0') {
// 将p的右子樹插入為c的右子樹
Transfer(T, 2*index+2, c, 2);
}
Transfer(c, 0, T, 2*index+2);
}
return OK;
}
/*
* 删除
*
* 根據LR的取值(0或1),删除結點p的左子樹/右子樹。
*/
Status DeleteChild(SqBiTree T, TElemType p, int LR) {
int index;
// 如果待删除的樹為空樹則無需繼續計算
if(BiTreeEmpty(T)) {
return ERROR;
}
// 擷取結點p的索引
index = EIndex(T, p, 0);
// 如果待删除結點不存在,則傳回錯誤提示
if(index == -1) {
return ERROR;
}
// 如果需要删除p的左子樹
if(LR == 0) {
Delete(T, 2 * index + 1);
// 如果需要删除p的右子樹
} else {
Delete(T, 2 * index + 2);
}
return OK;
}
void PrintTree(SqBiTree T) {
int level, width;
int i, j, k, w;
int begin;
int distance;
TElemType** tmp;
// 遇到空樹則無需繼續計算
if(BiTreeEmpty(T)) {
printf("\n");
return;
}
level = BiTreeDepth(T); // (完全)二叉樹結構高度
width = (int)pow(2, level)-1; // (完全)二叉樹結構寬度
// 動态建立行
tmp = (TElemType**)malloc(level* sizeof(TElemType*));
// 動态建立列
for(i = 0; i < level; i++) {
tmp[i] = (TElemType*)malloc(width* sizeof(TElemType));
// 初始化記憶體值為空字元
memset(tmp[i], '\0', width);
}
// 周遊樹中所有元素,将其安排到二維數組tmp中合适的位置
for(i = 0; i < level; i++) {
w = (int) pow(2, i); // 二叉樹目前層的寬度
distance = width / w; // 二叉樹目前層的元素間隔
begin = width / (int) pow(2, i + 1); // 二叉樹目前層首個元素之前的空格數
for(k = 0; k < w; k++) {
j = begin + k * (1 + distance);
tmp[i][j] = T[(int) pow(2, i) + k - 1];
}
}
for(i = 0; i < level; i++) {
for(j = 0; j < width; j++) {
if(tmp[i][j] != '\0') {
printf("%c", tmp[i][j]);
} else {
printf(" ");
}
}
printf("\n");
}
}
int main(){
SqBiTree T;
printf("████████ InitBiTree \n");
{
printf("█ 初始化空二叉樹 T ...\n");
int a;
a = InitBiTree(T);
printf("%d\n",a);
}
printf("████████ CreateBiTree \n");
{
printf("█ 按先序序列建立二叉樹 T ...\n");
CreateBiTree(T);
}
printf("████████ BiTreeDepth \n");
{
printf("█ 二叉樹 T 的深度為:%d \n", BiTreeDepth(T));
}
printf("████████ PrintTree \n");
{
printf("█ 按二叉樹的結構列印樹 T ...\n");
PrintTree(T);
}
printf("████████ PreOrderTraverse \n");
{
printf("█ 前序周遊二叉樹 T = ");
PreOrderTraverse(T, PrintElem);
}
printf("████████ InOrderTraverse \n");
{
printf("█ 中序周遊二叉樹 T = ");
InOrderTraverse(T, PrintElem);
}
printf("████████ PostOrderTraverse \n");
{
printf("█ 後序周遊二叉樹 T = ");
PostOrderTraverse(T, PrintElem);
}
printf("████████ LevelOrderTraverse \n");
{
printf("█ 層序周遊二叉樹 T = ");
LevelOrderTraverse(T, PrintElem);
}
printf("████████ Value \n");
{
TElemType e = 'F';
printf("█ 結點 %c 的值為 %c\n", e, Value(T, e));
}
printf("████████ Assign \n");
{
TElemType e = 'F';
TElemType value = 'X';
printf("█ 将結點 %c 指派為 %c 後,T = \n", e, value);
Assign(T, e, value);
PrintTree(T);
}
printf("████████ Root \n");
{
printf("█ T 的根結點為 %c\n", Root(T));
}
printf("████████ Parent \n");
{
TElemType e = 'E';
printf("█ 結點 %c 的雙親為:%c \n", e, Parent(T, e));
}
printf("████████ LeftChild、RightChild \n");
{
TElemType e = 'E';
printf("█ 結點 %c 的左孩子結點值為:%c ,右孩子結點值為:%c\n", e, LeftChild(T, e), RightChild(T, e));
}
printf("████████ LeftSibling \n");
{
TElemType e = 'I';
printf("█ 結點 %c 的左兄弟為:%c\n", e, LeftSibling(T, e));
}
printf("████████ RightSibling \n");
{
TElemType e = 'H';
printf("█ 結點 %c 的右兄弟為:%c\n", e, RightSibling(T, e));
}
return 0;
}
3.這個版本的二叉樹順序實作比較好了解
代碼實作來自部落格Mogon_girl
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#include<cmath>
#include <math.h>
/* 狀态碼 */
#define TRUE 1 // 真/是 ABCDE^F^^G A B D E G C F
#define FALSE 0 // 假/否
#define OK 1 // 通過/成功
#define ERROR 0 // 錯誤/失敗
typedef int Status;
#define MAX_TREE_SIZE 100//二叉樹的最大結點數
typedef char ElemType;
typedef ElemType SqBiTree[MAX_TREE_SIZE];//0号單元存儲根節點
//typedef struct{
// int level;//結點所在層
// int order;//結點在本層序号(按完全二叉樹計算)
//}Pos;
//1.構造空二叉樹T
void InitBiTree_Sq(SqBiTree &T){
for(int i=0;i<MAX_TREE_SIZE;i++){
T[i]='\0';//空樹無結點,以空字元填充數組
}
}
//5.按層序序列構造二叉樹
void CreateBiTree_Le_Sq(SqBiTree &T){
char ch;
int i=0;
while(1){
ch=getchar();
if(ch=='\n')break;
if(ch=='^'){
T[i++]='\0';
}else{
T[i++]=ch;
}
}
}
//7.傳回二叉樹長度
int BiTreeLength_Sq(SqBiTree T){
int len;
for(len=MAX_TREE_SIZE;len-1>=0;len--){
if(T[len-1]!='\0'){
break;
}
}
return len;
}
//8.傳回二叉樹深度(層數)
BiTreeDepth_Sq(SqBiTree T){
int level=0;
while((int)pow(2,level)-1<BiTreeLength_Sq(T)){
level++;
}
return level;
}
//17.層次周遊二叉樹
void LevelOrderTraverse_Sq(SqBiTree T){
int len=BiTreeLength_Sq(T);
for(int i=0;i<len;i++){
if(T[i]!='\0'){
printf("%c ",T[i]);
}
}
printf("\n");
}
//18.前序周遊二叉樹
void PreOrderTraverse_Sq(SqBiTree T,int i){
if(T[i]!='\0'){
printf("%c ",T[i]);
PreOrderTraverse_Sq(T,2*i+1);
PreOrderTraverse_Sq(T,2*i+2);
}
}
//19.中序周遊二叉樹
void InOrderTraverse_Sq(SqBiTree T,int i){
if(T[i]!='\0'){
InOrderTraverse_Sq(T,2*i+1);
printf("%c ",T[i]);
InOrderTraverse_Sq(T,2*i+2);
}
}
//20.後序周遊二叉樹
void PostOrderTraverse_Sq(SqBiTree T,int i){
if(T[i]!='\0'){
PostOrderTraverse_Sq(T,2*i+1);
PostOrderTraverse_Sq(T,2*i+2);
printf("%c ",T[i]);
}
}
void PrintTree(SqBiTree T) {
int level, width;
int i, j, k, w;
int begin;
int distance;
ElemType** tmp;
level =BiTreeDepth_Sq(T); // (完全)二叉樹結構高度
width = (int)pow(2, level)-1; // (完全)二叉樹結構寬度
// 動态建立行
tmp = (ElemType**)malloc(level* sizeof(ElemType*));
// 動态建立列
for(i = 0; i < level; i++) {
tmp[i] = (ElemType*)malloc(width* sizeof(ElemType));
// 初始化記憶體值為空字元
memset(tmp[i], '\0', width);
}
// 周遊樹中所有元素,将其安排到二維數組tmp中合适的位置
for(i = 0; i < level; i++) {
w = (int) pow(2, i); // 二叉樹目前層的寬度
distance = width / w; // 二叉樹目前層的元素間隔
begin = width / (int) pow(2, i + 1); // 二叉樹目前層首個元素之前的空格數
for(k = 0; k < w; k++) {
j = begin + k * (1 + distance);
tmp[i][j] = T[(int) pow(2, i) + k - 1];
}
}
for(i = 0; i < level; i++) {
for(j = 0; j < width; j++) {
if(tmp[i][j] != '\0') {
printf("%c", tmp[i][j]);
} else {
printf(" ");
}
}
printf("\n");
}
}
int main(){
SqBiTree T;
printf("————————————————————————————△初始化空二叉樹\n");
InitBiTree_Sq(T);//初始化
printf("————————————————————————————△層次序列建立\n");
CreateBiTree_Le_Sq(T);
printf("————————————————————————————△深度和長度\n");
printf("此時T的長度為:%d,深度為:%d\n",BiTreeLength_Sq(T),BiTreeDepth_Sq(T));
int len=BiTreeLength_Sq(T);
printf("————————————————————————————△層序周遊\n");
LevelOrderTraverse_Sq(T);
printf("————————————————————————————△前序周遊\n");
PreOrderTraverse_Sq(T,0);
printf("\n");
printf("————————————————————————————△中序周遊\n");
InOrderTraverse_Sq(T,0);
printf("\n");
printf("————————————————————————————△後序周遊\n");
PostOrderTraverse_Sq(T,0);
printf("████████ PrintTree \n");
PrintTree(T);
return 0;
}