學院

計算機科學與教育軟件學院

年級、專業、班

計算機科學與技術172班

姓名

?

學號

17061

實驗課程名稱

數據結構實驗

成績

?

實驗項目名稱

實驗二 樹和二叉樹的實現

指導老師

?

一、實驗目的

理解并運用樹的操作方法

二、使用儀器、器材

微機一臺

操作系統：Win10

編程軟件：C++

三、實驗內容及原理

自己選擇存儲方法、自己設計輸入輸出方式，在實驗報告中清晰說明。

樹的高度（設空樹高度為-1）不小于3，包含兒子數為0、1、2、3的結點。

樹的高度（設空樹高度為-1）不小于4，包含了兒子數為0、1、2的結點。選做：二叉樹的總結點（或葉片）數目的統計。

3.補充下列程序，使該程序能正確運行。

題目要求：由先序遍歷序列建立二叉樹的515二叉鏈表，中序線索化二叉樹并找出結點的前驅和后繼。

?

• 實驗過程原始數據記錄

1、輸入一棵多元樹，進行多種遍歷

樹的高度（設空樹高度為-1）不小于3，包含兒子數為0、1、2、3的結點。

Tree.h

#pragma once

#include <stdio.h>

#include <malloc.h>

#define MaxSize 100

typedef struct tnode

{

??? char data;???????????????????????? //節點的值

??? struct tnode *hp;????????????? //指向兄弟

??? struct tnode *vp;????????????? //指向孩子節點

} TSBNode;???????????????????????????? //孩子兄弟鏈存儲結構類型

?

TSBNode *CreateTree(char *str);???????? //由str建立孩子兄弟鏈存儲結構

void DispTree(TSBNode *t);???? //輸出孩子兄弟鏈存儲結構

void DestroryTree(TSBNode *&t);??? //銷毀樹t

int TreeHeight2(TSBNode *t);

?

void PreOrder(TSBNode *b);???? //先序遍歷的遞歸算法

void PostOrder(TSBNode *b);??? ??? //后序遍歷的遞歸算法

void LevelOrderTraverse(TSBNode *b);//層次遍歷

?

tree.cpp

#include"pch.h"

#include "tree.h"

?

TSBNode * CreateTree(char * str)

{

??? struct

??? {

???????? TSBNode *nodep;??????????????? //節點指針

???????? int num;????????????????? //孩子個數

??? } St[MaxSize];???????????????????? //順序棧

??? int top = -1;????????????????????? //棧頂指針

??? int i = 0, j; char ch = str[i];

??? TSBNode *t = NULL, *p=NULL, *q;

??? while (ch != '\0')

??? {

???????? switch (ch)

???????? {

???????? case '(': top++; St[top].nodep = p;

???????????? St[top].num = 0;?????????????? //當前節點p進棧

???????????? break;

???????? case ')':top--;?? break;??????????? //退棧

???????? case ',':St[top].num++; break; //棧頂節點增加一個孩子

???????? default:

???????????? p = (TSBNode *)malloc(sizeof(TSBNode));

??? ???????? p->data = ch;????????????????? //建立一個節點p存放ch

???????????? p->hp = p->vp = NULL;

???????????? if (t == NULL)???????????????? //原為空樹

????????????????? t = p;

???????????? else????????????????????? //將其作為棧頂節點的一個孩子

???????????? {

????????????????? if (St[top].num == 0)????? //第一個孩子用vp指向它

????????????????????? St[top].nodep->vp = p;

????????????????? else????????????????? //其他孩子用棧頂節點的孩子節點的hp指向它

????????????????? {

????????????????????? q = St[top].nodep->vp;

????????????????????? for (j = 1; j < St[top].num; j++)

????????????????????????? q = q->hp;

????????????????????? q->hp = p;

????????????????? }

???????????? }

???????????? break;

???????? }

???????? i++;

???????? ch = str[i];

??? }

??? return t;

}

?

void DispTree(TSBNode * t)

{

??? TSBNode *p;

??? if (t != NULL)

??? {

???????? printf("%c", t->data);

???????? if (t->vp != NULL)??????? //有孩子時輸出一個'('

???????? {

???????????? printf("(");

???????????? p = t->vp;??????????? //p指向節點t的第一個孩子

???????????? while (p != NULL)

???????????? {

????????????????? DispTree(p);

????????????????? p = p->hp;

????????????????? if (p != NULL)

????????????????????? printf(",");

???????????? }

???????????? printf(")");????? //輸出一個')'

???????? }

??? }

}

?

void DestroryTree(TSBNode *& t)

{

??? if (t != NULL)

??? {

???????? DestroryTree(t->vp);

???????? DestroryTree(t->hp);

???????? free(t);????????????? //釋放根節點

??? }

}

?

int TreeHeight2(TSBNode * t)

{

??? TSBNode *p;

??? int h, maxh = 0;

??? if (t == NULL) return 0;?????? //空樹返回0

??? else

??? {

???????? p = t->vp;??????????????? //指向第1個孩子節點

???????? while (p != NULL)???????? //掃描t的所有子樹

???????? {

???????????? h = TreeHeight2(p);?? //求出p子樹的高度

???????????? if (maxh < h) maxh = h;??? //求所有子樹的最大高度

???????????? p = p->hp;??????????? //繼續處理t的其他子樹

???????? }

???????? return(maxh + 1);???????? //返回maxh+1

??? }

}

?

void PreOrder(TSBNode * b)

{

??? //st1為處理整個樹的棧，st2為處理其兄弟節點的棧

??? TSBNode *st1[100], *st2[100], *p = NULL;

??? int top1 = -1, top2 = -1;

??? if (b != NULL)

??? {

???????? p = b;

???????? top1++;

???????? st1[top1] = p;???????????????????? //先將根節點進棧

???????? while (top1 >= 0)????????????? //棧不空時循環

???????? {

???????????? p = st1[top1];

???????????? top1--;??????????????????????? //退棧

???????????? printf("%c ", p->data);??????? //打印輸出

???????????? if (p->vp)??????????????? //若該節點存在兄弟節點

???????????? {

????????????????? p = p->vp;

????????????????? while (p != NULL)???? //將兄弟節點依次進棧

????????????????? {

????????????????????? top2++;

????????????????????? st2[top2] = p;

????????????????????? p = p->hp;

????????????????? }

????????????????? while (top2 >= 0)???? //將兄弟節點依次退棧st2并將退棧的元素放到st1中

????????????????? {

????????????????????? top1++;

????????????????????? st1[top1] = st2[top2];

????????????????????? top2--;

????????????????? }

???????????? }

???????? }

??? }

}

?

?

void PostOrder(TSBNode * b)

{

??? if (b == NULL)

???????? return;

??? TSBNode *p = b->vp;

??? PostOrder(p);?????????????????????????????? //遞歸打印孩子節點

?

??? if (p != NULL)

???????? p = p->hp;

??? while (p)?????????????????????????????????????? //該節點不空則遞歸打印兄弟節點

??? {

???????? PostOrder(p);

???????? p = p->hp;

??? }

??? printf("%c ", b->data);???????????????????? //打印輸出

}

}

?

void LevelOrderTraverse(TSBNode * b)

{

}

?

Main.cpp

#include "pch.h"

#include <iostream>

#include"tree.h"

int main()

{

?

??? TSBNode *t;

??? t = CreateTree("A(B(E,F),C(G(J)),D(H,I(K,L,M)))");

??? printf("t:"); DispTree(t);

??? printf("\n樹t的高度:%d\n", TreeHeight2(t));

??? printf("\n樹t的先根遍歷結果為:"); PreOrder(t);

??? printf("\n");

??? printf("\n樹t的后根遍歷結果為:"); PostOrder(t);

??? DestroryTree(t);

??? return 1;

}

2、輸入一棵二叉樹進行多種遍歷。

樹的高度（設空樹高度為-1）不小于4，包含了兒子數為0、1、2的結點。選做：二叉樹的總結點（或葉片）數目的統計。

Btree.h

#pragma once

#include"pch.h"

#include <stdio.h>

#include <malloc.h>

#define MaxSize 100

typedef char ElemType;

typedef struct node

{

??? ElemType data;??????????? //數據元素

??? struct node *lchild;? //指向左孩子節點

??? struct node *rchild;? //指向右孩子節點

} BTNode;

void CreateBTree(BTNode * &b, char *str);?? //創建二叉樹

void DestroyBTree(BTNode *&b);

BTNode *FindNode(BTNode *b, ElemType x);

BTNode *LchildNode(BTNode *p);

BTNode *RchildNode(BTNode *p);

int BTHeight(BTNode *b);

void DispBTree(BTNode *b);//輸出二叉樹

?

//二叉樹的遍歷算法

void PreOrder1(BTNode *b);//先序遍歷非遞歸算法1

void PreOrder2(BTNode *b);//先序遍歷非遞歸算法2

void InOrder1(BTNode *b);//中序遍歷非遞歸算法1

void PostOrder1(BTNode *b);//后序遍歷非遞歸算法1

?

//有關棧的操作

typedef struct

{

??? BTNode *data[MaxSize];???????? //存放棧中的數據元素

??? int top;?????????????????????? //存放棧頂指針，即棧頂元素在data數組中的下標

} SqStack;???????????????????????????? //順序棧類型

?

void InitStack(SqStack *&s);??????????? //初始化棧

void DestroyStack(SqStack *&s);???????? //銷毀棧

bool StackEmpty(SqStack *s);??????????? //判斷棧是否為空

bool Push(SqStack *&s, BTNode *e); //進棧

bool Pop(SqStack *&s, BTNode *&e); //出棧

bool GetTop(SqStack *s, BTNode *&e);??? //取棧頂元素

Btree.cpp

#include"pch.h"

#include "btree.h"

?

void CreateBTree(BTNode *& b, char * str) //創建二叉樹

{??

??? BTNode *St[MaxSize], *p = NULL;

??? int top = -1, k, j = 0;

??? char ch;

??? b = NULL;???????????????? //建立的二叉樹初始時為空

??? ch = str[j];

??? while (ch != '\0')? ? //str未掃描完時循環

??? {

???????? switch (ch)

???????? {

???????? case '(':top++; St[top] = p; k = 1; break;?????? //為左孩子節點

???????? case ')':top--; break;

???????? case ',':k = 2; break;??????????????????? ?????? //為孩子節點右節點

???????? default:p = (BTNode *)malloc(sizeof(BTNode));

???????? ??? p->data = ch; p->lchild = p->rchild = NULL;

???????????? if (b == NULL)??????????????????? ??? //*p為二叉樹的根節點

????????????????? b = p;

???????????? else? ???????????????????????????????? //已建立二叉樹根節點

???????????? {

????????????????? switch (k)

????????????????? {

????????????????? case 1:St[top]->lchild = p; break;

????????????????? case 2:St[top]->rchild = p; break;

????????????????? }

???????????? }

???????? }

???????? j++;

???????? ch = str[j];

??? }

}

?

void DestroyBTree(BTNode *& b)

{??

??? if (b != NULL)

??? {

???????? DestroyBTree(b->lchild);

???????? DestroyBTree(b->rchild);

???????? free(b);

??? }

}

?

BTNode * FindNode(BTNode * b, ElemType x)

{??

??? BTNode *p;

??? if (b == NULL)

???????? return NULL;

??? else if (b->data == x)

???????? return b;

??? else

??? {

???????? p = FindNode(b->lchild, x);

???????? if (p != NULL)

???????????? return p;

???????? else

???????????? return FindNode(b->rchild, x);

??? }

}

?

BTNode * LchildNode(BTNode * p)

{

??? return p->lchild;

}

?

BTNode * RchildNode(BTNode * p)

{

??? return p->rchild;

}

?

int BTHeight(BTNode * b)

{??

??? int lchildh, rchildh;

??? if (b == NULL) return(0); ????????????? //空樹的高度為0

??? else

??? {

???????? lchildh = BTHeight(b->lchild); //求左子樹的高度為lchildh

???????? rchildh = BTHeight(b->rchild); //求右子樹的高度為rchildh

???????? return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);

??? }

}

?

void DispBTree(BTNode * b)

{

??? if (b != NULL)

??? {

???????? printf("%c", b->data);

???????? if (b->lchild != NULL || b->rchild != NULL)

???????? {

???????????? printf("(");?????????????????????? //有孩子節點時才輸出(

???????????? DispBTree(b->lchild);????????????? //遞歸處理左子樹

???????????? if (b->rchild != NULL) printf(","); //有右孩子節點時才輸出,

???????????? DispBTree(b->rchild);????????????? //遞歸處理右子樹

???????????? printf(")");?????????????????????? //有孩子節點時才輸出)

???????? }

??? }

}

?

void PreOrder1(BTNode * b)

{

??? BTNode *p;

??? SqStack *st;?????????????????? //定義一個順序棧指針st

??? InitStack(st);???????????????????? //初始化棧st

??? Push(st, b);?????????????????? //根節點進棧

??? while (!StackEmpty(st))??????? //棧不為空時循環

??? {

???????? Pop(st, p);?????????????? //退棧節點p并訪問它

???????? printf("%c ", p->data);?? //訪問節點p

???????? if (p->rchild != NULL) //有右孩子時將其進棧

???????????? Push(st, p->rchild);

???????? if (p->lchild != NULL) //有左孩子時將其進棧

???????????? Push(st, p->lchild);

??? }

??? printf("\n");

??? DestroyStack(st);????????????? //銷毀棧

}

?

void PreOrder2(BTNode * b)

{

??? BTNode *p;

??? SqStack *st;?????????????????? //定義一個順序棧指針st

??? InitStack(st);???????????????????? //初始化棧st

??? p = b;

??? while (!StackEmpty(st) || p != NULL)

??? {

???????? while (p != NULL)????????????? //訪問節點p及其所有左下節點并進棧

???????? {

???????????? printf("%c ", p->data);?? //訪問節點p

???????????? Push(st, p);????????????? //節點p進棧

???????????? p = p->lchild;??????????? //移動到左孩子

???????? }

???????? if (!StackEmpty(st))????? //若棧不空

???????? {

???????????? Pop(st, p);?????????????? //出棧節點p

???????????? p = p->rchild;??????????? //轉向處理其右子樹

???????? }

??? }

??? printf("\n");

??? DestroyStack(st);????????????? //銷毀棧

}

?

void InOrder1(BTNode * b)

{

??? BTNode *p;

??? SqStack *st;?????????????????????? //定義一個順序棧指針st

??? InitStack(st);???????????????????????? //初始化棧st

??? if (b != NULL)

??? {

???????? p = b;

???????? while (!StackEmpty(st) || p != NULL)

???????? {

???????????? while (p != NULL)????????????? //掃描節點p的所有左下節點并進棧

???????????? {

????????????????? Push(st, p);????????????? //節點p進棧

????????????????? p = p->lchild;??????????? //移動到左孩子

???????????? }

???????????? if (!StackEmpty(st))????? //若棧不空

???????????? {

????????????????? Pop(st, p);?????????????? //出棧節點p

????????????????? printf("%c ", p->data);?? //訪問節點p

????????????????? p = p->rchild;??????????? //轉向處理其右子樹

???????????? }

???????? }

???????? printf("\n");

??? }

??? DestroyStack(st);????????????? //銷毀棧

}

?

void PostOrder1(BTNode * b)

{

??? BTNode *p, *r;

??? bool flag;

??? SqStack *st;?????????????????????? //定義一個順序棧指針st

??? InitStack(st);???????????????????????? //初始化棧st

??? p = b;

??? do

??? {

???????? while (p != NULL)????????????????? //掃描節點p的所有左下節點并進棧

???????? {

???????????? Push(st, p);?????????????????? //節點p進棧

???????????? p = p->lchild;???????????????? //移動到左孩子

???????? }

???????? r = NULL;????????????????????????????? //r指向剛剛訪問的節點，初始時為空

???????? flag = true;?????????????????????? //flag為真表示正在處理棧頂節點

???????? while (!StackEmpty(st) && flag)

???????? {

???????????? GetTop(st, p);???????????????? //取出當前的棧頂節點p

???????????? if (p->rchild == r)??????????? //若節點p的右孩子為空或者為剛剛訪問過的節點

???????????? {

????????????????? printf("%c ", p->data);?? //訪問節點p

????????????????? Pop(st, p);

????????????????? r = p;??????????????????? //r指向剛訪問過的節點

???????????? }

???????????? else

???????????? {

????????????????? p = p->rchild;??????????? //轉向處理其右子樹

????????????????? flag = false;???????????? //表示當前不是處理棧頂節點

???????????? }

???????? }

??? } while (!StackEmpty(st));???????? //棧不空循環

??? printf("\n");

??? DestroyStack(st);????????????? //銷毀棧

}

?

void InitStack(SqStack *& s)

{

??? s = (SqStack *)malloc(sizeof(SqStack));//分配一個是順序?？臻g，首地址存放在s中

??? s->top = -1;????????????? ???????? //棧頂指針置為-1

}

?

void DestroyStack(SqStack *&s)???? //銷毀棧

{

??? free(s);

}

?

bool StackEmpty(SqStack * s)

{

??? return(s->top == -1);

}

?

bool Push(SqStack *& s, BTNode * e)

{

??? if (s->top == MaxSize - 1)???????? //棧滿的情況，即棧上溢出

???????? return false;

??? s->top++;????????????????????????? //棧頂指針增1

??? s->data[s->top] = e;?????????????? //元素e放在棧頂指針處

??? return true;

}

?

bool Pop(SqStack *& s, BTNode *& e)

{

??? if (s->top == -1)????????????????? //棧為空的情況，即棧下溢出

???????? return false;

??? e = s->data[s->top];?????????????? //取棧頂指針元素的元素

??? s->top--;????????????????????????? //棧頂指針減1

??? return true;

}

?

bool GetTop(SqStack * s, BTNode *& e)

{

??? if (s->top == -1)????????????????? //棧為空的情況，即棧下溢出

???????? return false;

??? e = s->data[s->top];?????????????? //取棧頂元素

??? return true;

}

?

Main.cpp

int main()

{

??? BTNode *b;

??? CreateBTree(b, "A(B(D(G,H(,J)),E(,I)),C(,F))");

??? DispBTree(b);

??? printf("\n");

??? printf("先序遍歷序列1:"); PreOrder1(b);

??? printf("先序遍歷序列2:"); PreOrder2(b);

??? printf("中序遍歷序列:"); InOrder1(b);

??? printf("后序遍歷序列:"); PostOrder1(b);

??? DestroyBTree(b);

??? printf("\n");

}

?

3、補充下列程序，使該程序能正確運行。

步驟一：新建工程，新建一個頭文件,命名為 thread.h，一個源文件命名為thread.cpp

?

步驟二：

在thread.h中編輯代碼，代碼如下：

#include <iostream>

using namespace std;

typedef char DataType;

?

typedef struct Node

{

?????? DataType data;

?????? int????? Ltag;

?????? int????? Rtag;

__struct Node__ *LChild;?? /*填空1、指針域的數據類型*/

?????? __struct Node__ *RChild;

}BTNode;

?

BTNode *pre;

void CreateBiTree(BTNode? *&root, DataType Array[]) ; //創建初始化二叉樹

void? Inthread(BTNode *root); //實現中序線索二叉樹

BTNode * InPre(BTNode *p);? //求中序線索二叉樹結點的前驅

BTNode * InNext(BTNode * p) ; //求中序線索二叉樹結點的后驅

?

在Thread.cpp中編輯代碼，代碼如下：

#include "thread.h" ???????????/*11、填空：請填空：包含頭文件*/

?

void CreateBiTree(BTNode? *&root, DataType Array[])

{

?????? static int count=0;????? //靜態變量count

?? char item=Array[count];//讀取Array[]數組中的第count個元素

?????? count++;

?????? if(item == '#') //如果讀入#字符，創建空樹

?????? ?? { root = NULL; return ;}

?? else

?????? {

????????????? root = __ (BTNode *)malloc(sizeof(BTNode))__;/*填空3：生成一個新結點*/

? ??????___ root->data___ = item; /*填空4：將ch做為新結點的數據域的值*/

????????????? root->Ltag=0;

????????????? root->Rtag=0;

????????????? __ CreateBiTree(root->LChild, Array)_; /*填空5: 遞歸的方法，生成左子樹，注意實參的表示方法*/

?????? __ CreateBiTree(root->RChild, Array)_; /*填空6: 遞歸的方法，生成右子樹，注意實參的表示方法*/

?

????? ?}

}

?

void? Inthread(BTNode *root)

/* 對root所指的二叉樹進行中序線索化，其中pre始終指向剛訪問過的結點，其初值為NULL */

{

?????? if (root!=NULL)

?????? {

????????????? Inthread(root->LChild);? /* 線索化左子樹 */

????????????? if (root->LChild==NULL)

????????????? {

???????????????????? root->Ltag=___ 1__;

???????????????????? __ root->LChild_=pre;? /*填空7-8：置前驅線索 */

????????????? }

????????????? if (pre!=NULL&& pre->RChild==NULL)? /* 填空9-10：置后繼線索 */

{

???????????????????? pre->Rtag=__ 1___;

???????????????????? __ root->RChild __=root;

????????????? }

?????? ?? pre=root;

?????? ?? Inthread(root->RChild);? /*線索化右子樹*/

?????? }

}

?

/* 在中序線索二叉樹中查找p的中序前驅, 并用pre指針返回結果 */

BTNode * InPre(BTNode *p)

{?

?????? BTNode *q;

?????? if(p->Ltag==1)

????????????? pre = __p->LChild__;? /*填空13：直接利用線索找前驅*/

?????? else

?????? { /* 填空14-15：在p的左子樹中查找"最右下端"結點 */

????????????? for(q = p->LChild;q->Rtag==__0__;q=q->_ RChild __);

????????????? pre=q;

?????? }

?????? return(pre);

}

?

/*在中序線索二叉樹中查找p的中序后繼結點，并用next指針返回結果*/

BTNode * InNext(BTNode * p)

{

?????? BTNode *Next;

?????? BTNode *q;

?????? if (p->Rtag==1)?

????????????? Next = p->RChild;? /*填空16：直接利用線索*/

?????? else

?????? { /*填空17-18： 在p的右子樹中查找"最左下端"結點*/

????????????? for(q=p->RChild; q->Ltag==___0___ ;q=q->__ LChild ___);

????????????? Next=q;

?????? }

?????? return(Next);

}

?

void main()

{

?????? BTNode *root,*q;

?????? DataType A[]="AB#CD##E##F#G##";//以"#"補充空分支后的某個遍歷序列

?

?????? CreateBiTree(root,A);//以先序遍歷序列建立二叉樹

pre = NULL;

?????? Inthread(root);

?????? q =InPre(root); /*找根結點的前驅，大家試找其它結點的前驅*/

?????? cout<<root->data<<"的前驅為"<<q->data<<endl;

?????? q =InNext(root); /*找根結點的后驅，大家試找其它結點的后驅*/

?????? cout<<root->data<<"的后繼為"<<q->data<<endl;

};

??

• 實驗結果及分析

1.輸入一棵多元樹，進行多種遍歷

多元樹存儲結構為孩子兄弟存儲結構，遍歷算法:先跟遍歷采用非遞歸算法，后根遍歷采用遞歸算法。

2.輸入一棵二叉樹進行多種遍歷。

?

遍歷算法均為非遞歸算法

3.補充下列程序，使該程序能正確運行。

?

?