一、題目
採用字元型別為元素資訊,用順序儲存結構和鏈式儲存結構,實現二叉樹抽象資料型別。
adt bitree, h是如下二元關係:
(1) 在d中存在唯一的稱為根的資料元素root,它在關係h下無前驅;
(2) 若d – ≠ φ,則存在d – 的乙個劃分dl dr ,dl∩dr =φ;
(3) 若dl ≠ φ,則dl 中存在惟一的資料元素xl , ∈ h,且存在dl 上的關係hl < h;若dr ≠ φ,則dr 中存在惟一的資料元素xr , ∈ h,且存在dr 上的關係hr < h;
(4) (dl,)是一棵符合本定義的二叉樹,稱為根root的左子樹;
(dr,)是一棵符合本定義的二叉樹,稱為根root的右子樹。
基本操作p:
initbitree(&t);
操作結果:構造空二叉樹。
createbitree(&t);
初始條件:二叉樹存在。
操作結果:按輸入格式構造二叉樹。
destroybitree(&t);
初始條件:二叉樹存在。
操作結果:銷毀二叉樹t。
clearbitree(&t);
初始條件:二叉樹存在。
操作結果:將二叉樹t清為空樹。
bitreeempty(t);
初始條件:二叉樹存在。
操作結果:若t為空二叉樹,則返回ture,否則false。
bitreedepth(t);
初始條件:二叉樹存在。
操作結果:返回t的深度。
root(t);
初始條件:二叉樹存在。
操作結果:返回t的根。
value(t, e);
初始條件:二叉樹存在,e是t中某個結點。
操作結果:返回結點e的值。
assign(&t, &e, value);
初始條件:二叉樹存在,e是t中某個結點。
操作結果:結點e賦值為value 。
parent(t, e);
初始條件:二叉樹存在,e是t中某個結點。
操作結果:若e是t的非根結點,則返回它的雙親,否則返回「空」。
leftchild(t, e);
初始條件:二叉樹存在,e是t中某個結點。
操作結果:返回e的左孩子。若e無左孩子,則返回「空」。
rightchild(t, e);
初始條件:二叉樹存在,e是t中某個結點。
操作結果:返回e的右孩子。若e無右孩子,則返回「空」。
preorder(t);
初始條件:二叉樹存在。
操作結果:先序遍歷t,按順序輸出每個結點。
inorder(t);
初始條件:二叉樹存在。
操作結果:中序遍歷t,按順序輸出每個結點。
postorder(t);
初始條件:二叉樹存在。
操作結果:後序遍歷t,按順序輸出每個結點。
levelorder(t);
初始條件:二叉樹存在。
操作結果:按層遍歷t,按順序輸出每個結點。
} adt bitree
二、儲存結構定義
公用標頭檔案
#include <>
#include <>
#include <>字串操作
#include <>數學
#include <>記憶體操作檔案
#include <>系統時間
#include <>佇列
using namespace std;
#define ture 1
#define false 0
#define ok 1
#define error 0
#define maxlen 30
#define elemtype char
#define status int
(1)順序儲存結構
#define max_size 100
typedef elemtype sqbitree[max_size];
(2)鏈式儲存結構
typedef struct bitnode
bitnode, * bitree;
三、演算法設計
(1)順序儲存結構
status initbitree(sqbitree &t)
//構造空二叉樹。
status createbitree(sqbitree &t)
//按輸入順序構造二叉樹。
status destroybitree(sqbitree &t)
//銷毀二叉樹t
else return error; //t不存在,返回error
}status clearbitree(sqbitree &t)
//將二叉樹t清為空樹。
else return error; //t不存在,返回error
}status bitreeempty(sqbitree t)
//若t為空二叉樹,則返回ture,否則false。
int bitreedepth(sqbitree t)
//返回t的深度。
return i;
}elemtype * root(sqbitree t)
//返回t的根。
elemtype value(sqbitree t, int e)
//返回結點e的值。
status assign(sqbitree &t, int &e, elemtype value)
//結點e賦值為value 。
else t[e] = value;
return ok
}elemtype * parent(sqbitree t, int e)
//若e是t的非根結點,則返回它的雙親,否則返回"空"。
elemtype * leftchild(sqbitree t, int e)
//返回e的左孩子。若e無左孩子,則返回"空"。
elemtype * rightchild(sqbitree t, int e)
//返回e的右孩子。若e無右孩子,則返回"空"。
(2)鏈式儲存結構
status initbitree(bitree &t)
//構造空二叉樹。
status createbitree(bitree &t, char *s,int &i)
//按輸入構造二叉樹。
{ //按照完全二叉樹輸入,'#'代表空樹
// (例如 "a(b(d(h,i),#),c(f,#))" )
char c;
c = s[i++];
if(cc == '\0') t = null;
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義,具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現,學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...
二叉樹遍歷技巧
二叉樹先根序 後根序 中根序遍歷的速演算法 解題技巧 經過研究我找出了一種不用畫圖,由先 後 根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差,用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...