?鏈?zhǔn)綐?/p> typedef struct BTNode {char data; //數(shù)據(jù)域struct BTNode *lchild;// 左指針域struct BTNode *rchild;// 右指針域 };

二叉排序樹

typedef struct BTNode1 {int key; //關(guān)鍵字struct BTNode1 *lchild;// 左指針域struct BTNode1 *rchild;// 右指針域 };

線索樹

typedef struct TBTNode {char data; //數(shù)據(jù)域int ltag, rtag;//線索標(biāo)記，=0時則表示對應(yīng)指針域?yàn)橹羔?#xff0c; =1表示對應(yīng)指針域?yàn)榫€索，指向該結(jié)點(diǎn)的直接前驅(qū)（后繼）struct TBTNode *lchild;// 左指針域struct TBTNode *rchild;// 右指針域 };

二叉樹三種遍歷

void Visit(BTNode *p) {//某種操作，例如輸出等等， } void preorder(BTNode *p) { //先序遍歷if (p != NULL) {Visit(p); // 某種操作preorder(p->lchild);preorder(p->rchild);} } void inorder(BTNode *p) { //中序遍歷if (p != NULL) {inorder(p->lchild);Visit(p);inorder(p->rchild);} } void postorder(BTNode *p) { //后序遍歷if (p != NULL) {postorder(p->lchild);postorder(p->rchild);Visit(p);} }

求表達(dá)式(a-(b+c)*(d/e))存儲在二叉鏈表為存儲結(jié)構(gòu)的二叉樹中，求出該表達(dá)式的值

int op(int a, int b, char Op) { //運(yùn)算函數(shù) 完成 a Op b 的運(yùn)算if (Op == '+')return a + b;if (Op == '-')return a - b;if (Op == '*')return a * b;if (Op == '/') {if (b == 0) { ? ?//被除數(shù)不能為0return 0;}else {return a / b;}} } int comp(BTNode *p) { ?//僅使用于這一種算式int A, B;if (p != NULL) {if (p->lchild != NULL && p->rchild != NULL) { //左右子樹都不為空/*后序遍歷求其值*/A = comp(p->lchild);B = comp(p->rchild);return op(A, B, p->data);}else {return p->data - '0'; // 如果左右子樹都為空，則為數(shù)值，直接返回對應(yīng)數(shù)字 （因?yàn)槎x時是char）}}return 0; ?//空樹，返回0; }

計算二叉樹的深度

int getDepth(BTNode *p) {int LD, RD;if (p == NULL) {return 0;}else {LD = getDepth(p->lchild);RD = getDepth(p->rchild);return (LD > RD ? LD : RD) + 1;} }

查找二叉樹中 值等于key的節(jié)點(diǎn)是否存在，若存在將p指向該節(jié)點(diǎn)，否則將q賦值為NULL，data為int型

typedef struct BTNode2 {int data; //數(shù)據(jù)域struct BTNode2 *lchild;// 左指針域struct BTNode2 *rchild;// 右指針域 }; /*假設(shè)二叉樹已經(jīng)存在，且p指向其根節(jié)點(diǎn)*/ void search(BTNode2 *p, BTNode2 *&q, int key) {if (p != NULL) {if (p->data == key) {q = p;}else {search(p->lchild, q, key);search(p->rchild, q, key);}} }

假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)存儲，編寫一個程序輸出先序（中序，后序）序列中第k個結(jié)點(diǎn)的值。

int n = 0; //全局變量 int trave(BTNode *p, int k) { //先序if (p != NULL) {++n;if (k == n) {cout << p->data << endl;return 0;}trave(p->lchild,k);trave(p->rchild,k);} } int trave(BTNode *p, int k) { ?//中序if (p != NULL) {trave(p->lchild, k);++n;if (k == n) {cout << p->data << endl;return 0;}trave(p->rchild, k);} } int trave(BTNode *p, int k) { ?//后序if (p != NULL) {trave(p->lchild, k);trave(p->rchild, k);++n;if (k == n) {cout << p->data << endl;return 0;}} }

層次遍歷

void level(BTNode *p) {int front, rear;?BTNode *que[maxSize]; ?//定義一個循環(huán)隊列，記錄要訪問的層次上的節(jié)點(diǎn)front = rear = 0;BTNode *q;?if (q != NULL) {rear = (rear + 1) % maxSize;que[rear] = p; ?//根節(jié)點(diǎn)入隊while (front != rear) {front = (front + 1) % maxSize;q = que[front]; ? ?//隊頭節(jié)點(diǎn) 出隊Visit(p);if (q->lchild != NULL) {rear = (rear + 1) % maxSize;que[rear] = q->lchild;}if (q->rchild != NULL) {rear = (rear + 1) % maxSize;que[rear] = q->lchild;}}} }

計算二叉樹寬度

typedef struct St {BTNode *p;int lno; ? //節(jié)點(diǎn)所在層號 }; int maxNode(BTNode *b) {St que[maxSize]; ? ?//定義順序隊列int front = 0, rear = 0;?int Lno,n,max;BTNode *q;if (b != NULL) {++rear;que[rear].p = b; ?//樹根入隊?que[rear].lno = 1; //層數(shù)為1while (front != rear) {++front;q = que[front].p;Lno = que[front].lno; ? //取當(dāng)前節(jié)點(diǎn) 層號if (q->lchild != NULL) {++rear;que[rear].p = q->lchild;que[rear].lno = Lno + 1;}if (q->rchild != NULL) {++rear;que[rear].p = q->rchild;que[rear].lno = Lno + 1;}} //循環(huán)結(jié)束時，Lno 中保存的時這顆二叉樹的最大層數(shù)（高度）max = 0;for (int i = 0; i < Lno; ++i) {n = 0;for (int j = 1; j <= rear; ++j) {if (que[j].lno == i) {++n;}if (max < n) {max = n;}}}return max;}elsereturn 0; }

二叉樹遍歷的非遞歸算法（先，中，后）

void preorderNonrecursion(BTNode *bt) { ?//先序遍歷if (bt != NULL) {BTNode *Stack[maxSize];?int top = -1;BTNode *p;Stack[++top] = bt;while (top != -1) {p = Stack[top--];Visit(p);if (p->rchild != NULL) {Stack[++top] = p->rchild;}if (p->lchild != NULL) {Stack[++top] = p->lchild;}}} } void inorderNonrecursion(BTNode *bt) { //中序遍歷if (bt != NULL) {BTNode *Stack[maxSize];int top = -1;BTNode *p;p = bt;while (top != -1||p != NULL) {while (p != NULL) {Stack[++top] = p;p->lchild;}if (top != -1) {p = Stack[top--];Visit(p);?p = p->rchild;}}} } void postorderNonrecursion(BTNode *bt) { //后序遍歷if (bt != NULL) {BTNode *Stack1[maxSize];int top1 = -1;BTNode *Stack2[maxSize];int top2 = -1;BTNode *p = NULL;Stack1[++top1] = bt;while (top1 != -1) {p = Stack1[top1--];Stack2[++top2] = p;if (p->lchild != NULL) {Stack1[++top1] = p->lchild;}if (p->rchild != NULL) {Stack2[++top1] = p->rchild;}}while (top2 != -1) {p = Stack2[top2--];Visit(p);?}} }

根據(jù)先序和中序遍歷構(gòu)造出二叉樹?

BTNode *CreateBT(char pre[], char in[], int l1, int r1, int l2, int r2) {BTNode *s;int i;if (l1 > r1) { ??return NULL;?}BTNode *s = new BTNode;s->lchild = s->rchild = NULL;for (int i = l2; i < r2; i++) { ?//查找等于當(dāng)前子樹根的節(jié)點(diǎn)再中序的位置if (in[i] == pre[l1]) {break;}}s->data = in[i];?s->lchild = CreateBT(pre, in, l1 + 1, l1 + i - 12, 12, i - 1);s->rchild = CreateBT(pre, in, l1 + i - 12 + 1, r1, i + 1, r2);return s; }

計算二叉樹所有的節(jié)點(diǎn)數(shù)

int n = 0; ? ?//非遞歸 void count(BTNode *p) {if (p != NULL) {++n;count(p->lchild);count(p->rchild);} } int count2(BTNode *p) { //遞歸int n1, n2;if (p == NULL) {return 0;}else {n1 = count2(p->lchild);n2 = count2(p->rchild);return n1 + n2 + 1;} }

計算二叉樹的所有葉子節(jié)點(diǎn)數(shù)

int n = 0; ? ?//非遞歸 void count3(BTNode *p) {if (p != NULL) {if (p->lchild == NULL && p->rchild == NULL) {++n;}count3(p->lchild);count3(p->rchild);} } int count4(BTNode *p) { //遞歸int n1, n2;if (p == NULL) {return 0;}else if (p->lchild == NULL && p->rchild == NULL) {return 1;}else {n1 = count4(p->lchild);n2 = count4(p->rchild);return n1 + n2;} }

利用節(jié)點(diǎn)的右孩子指針rchild 將一棵二叉樹的葉子節(jié)點(diǎn)從左往右的順序串成一個單鏈表（在題目中定義兩個指針，head和tail，其中hear 指向第一個葉子節(jié)點(diǎn)，head初值為NUll,tail指向最后一個葉子節(jié)點(diǎn)）

void link(BTNode*p, BTNode*head, BTNode*&tail) {if (p != NULL) {if (p->lchild == NULL && p->rchild == NULL) { ?//葉子節(jié)點(diǎn)if (head == NULL) { ? //第一個節(jié)點(diǎn)，head = p;tail = p;}else { ? //非第一個節(jié)點(diǎn)tail->rchild = p;tail = p;}}link(p->lchild, head, tail);link(p->rchild, head, tail);} }

在二叉樹的二叉鏈表存儲結(jié)構(gòu)中，增加一個指向雙親結(jié)點(diǎn)的parent指針，設(shè)計一個算法給這個指針賦值，并且輸出所有節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑。

typedef struct BTNode3 {char data;struct BTNode3*parent;struct BTNode3*lchild;struct BTNode3*rchild;? }; void triBtree(BTNode3*p, BTNode3 *q) { ?//給parent賦值 ?p為根節(jié)點(diǎn)的時候，q應(yīng)為NULLif (p != NULL) {p->parent = q; //當(dāng)前所訪問的節(jié)點(diǎn)的parent 指向q；q = p;?triBtree(p->lchild, q);triBtree(p->rchild, q);} } void printPath(BTNode3 *p) { //打印路徑while (p != NULL) {cout << p->data << " " << endl;p->parent;} } void allPath(BTNode3 *p) { //打印所有路徑if (p != NULL) {printPath(p);allPath(p->lchild);allPath(p->rchild);} }

假設(shè)先序遍歷序列儲存在數(shù)組中，將其轉(zhuǎn)變?yōu)楹笮虮闅v

void change(char pre[], int L1, int R1, char post[], int L2, int R2) {if (L1 <= R1) {post[R2] = pre[L1]; ? //將 pre的第一個元素放在post的末尾change(pre, L1 + 1, (L1 + 1 + R1) / 2, post, L2, (L2 + R2 - 1) / 2);change(pre, (L1 + 1 + R1) / 2 + 1, R1, post, (L2 + R2 - 1) / 2 + 1, R2 - 1);} }

求二叉樹中 值為x的節(jié)點(diǎn)的層號（高度）

int L = 1; //全局變量 void leno(BTNode *p, char x) {if (p != NULL) {if (p->data == x) {cout << L << endl;}++L; ?//去往下層?leno(p->lchild, x);leno(p->rchild, x);--L; ?//回到上層} }

雙序遍歷 （中左中右）

void Double_order(BTNode *t) {if (t != NULL) {Visit(t);Double_order(t->lchild);Visit(t);Double_order(t->rchild);} }

輸出根節(jié)點(diǎn)到所有結(jié)點(diǎn)的路徑
?

int i; int top = 0; char pathstack[maxSize]; void allPath(BTNode *p) {if (p != NULL) {pathstack[top] = p->data;++top;if (p->lchild == NULL && p->rchild == NULL) { ?//葉子節(jié)點(diǎn)for (i = 0; i < top; ++i) {cout << pathstack[i]; ? //打印路徑}}allPath(p->lchild);allPath(p->rchild);--top;} }

?

總結(jié)

以上是生活随笔為你收集整理的天勤数据结构代码——树基本操作的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。