實驗四 二叉樹操作實現(xiàn)

1、實驗四 二叉樹操作實現(xiàn)實驗日期： 2017 年 4 月 20 日 實驗?zāi)康募耙?. 熟練掌握樹的基本概念、二叉樹的基本操作及在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實現(xiàn)；2. 重點掌握二叉樹的創(chuàng)建、遍歷及求深度等算法；3. 掌握運用遞歸方式描述算法及編寫遞歸C程序的方法，提高算法分析和程序設(shè)計能力。實驗內(nèi)容鍵盤輸入一個字符串，利用二叉樹前序遍歷的結(jié)果建成一棵二叉樹，并用三種遍歷方法打印，比較是否與自己預(yù)先想象的相一致。再求樹的深度、1度結(jié)點數(shù)、2度節(jié)點數(shù)，交換二叉樹的左右子樹并輸出交換后的中序遍歷結(jié)果驗證交換的正確性。找到二叉樹中序遍歷最后一個結(jié)點并輸出結(jié)點值。二叉樹結(jié)點類型定義：typedef char dat

2、atype; typedef struct tnode datatype data; struct tnode *lchild,*rchild; BiTNode,*BiTree; 任務(wù)1題目要求創(chuàng)建一個程序文件sy4.cpp，自定義相應(yīng)函數(shù)完成以下操作：（1）void visit(BiTree p) /*輸出p指針指向的結(jié)點*/（2）void Preorder(BiTree T) /*前序遍歷*/（3）void Inorder(BiTree T) /*中序遍歷*/（4）void Postorder(BiTree T) /*后序遍歷*/（5）BiTree CreateTree( ) /*以前序遍

3、歷的順序建立二叉樹*/（6）int deep(BiTree T) /*求二叉樹深度*/（7）int leaf(BiTree T) /*求葉子結(jié)點數(shù)*/（8）int OneChild(BiTree T) /*求1度結(jié)點數(shù)*/（9）int TwoChild(BiTree T) /*求2度結(jié)點數(shù)*/（10）void Exchange(BiTree T) /*二叉樹左右子樹交換*/（11）BiTree InorderLastNode(BiTree T); /*找二叉樹中序遍歷最后一個結(jié)點*/2請回答下列問題（1）在n個結(jié)點二叉樹的二叉鏈表存儲中，其指針域的總數(shù)為 2n 個，其中 n-1 個用于鏈接孩子

4、結(jié)點， n+1 個空閑著。（2）在二叉鏈表存儲中，數(shù)據(jù)域值為data，左右子樹的指針分別為left和right，則判斷：指針p所指結(jié)點為0度結(jié)點的條件是 p->left=NULL&&p->right=NULL ；指針p所指結(jié)點為1度結(jié)點的條件是 (p->left=NULL&&p->right!=NULL)|(p->left!=NULL&&p->right=NULL) ；指針p所指結(jié)點為2度結(jié)點的條件是 p->left!=NULL&&p->right!=NULL 。（3）T為二叉樹的根

5、的地址，該樹是空二叉樹滿足條件： T=NULL 。3sy14.cpp源程序清單（含必要的注釋）#include<stdio.h>#include<stdlib.h>typedef char datatype;typedef struct tnode datatype data;struct tnode *lchild, *rchild; BiTNode, *BiTree;void visit(BiTree p); /*輸出p指針指向的結(jié)點*/void Preorder(BiTree T); /*前序遍歷*/void Inorder(BiTree T); /*中序遍歷*/

6、void Postorder(BiTree T); /*后序遍歷*/BiTree CreateTree(); /*以前序遍歷的順序建立二叉樹*/int deep(BiTree T); /*求二叉樹深度*/int leaf(BiTree T); /*求葉子結(jié)點數(shù)*/int OneChild(BiTree T); /*求1度結(jié)點數(shù)*/int TwoChild(BiTree T); /*求2度結(jié)點數(shù)*/void Exchange(BiTree T); /*二叉樹左右子樹交換*/BiTree InorderLastNode(BiTree T); /*找二叉樹中序遍歷最后一個結(jié)點*/void visit

7、(BiTree p) /*輸出p指針指向的結(jié)點*/if (p->data != '#') printf("%c ", p->data);void Preorder(BiTree T) /*前序遍歷*/if (T != NULL) visit(T); /訪問根節(jié)點Preorder(T->lchild); /訪問左子節(jié)點Preorder(T->rchild); /訪問右子節(jié)點void Inorder(BiTree T) /*中序遍歷*/if (T != NULL) Inorder(T->lchild); /訪問左子節(jié)點visit(T

8、); /訪問根節(jié)點Inorder(T->rchild); /訪問右子節(jié)點void Postorder(BiTree T) /*后序遍歷*/if (T != NULL) Postorder(T->lchild); /訪問左子節(jié)點Postorder(T->rchild); /訪問右子節(jié)點visit(T); /訪問根節(jié)點BiTree CreateTree() /*以前序遍歷的順序建立二叉樹*/char ch;BiTree T;if (ch = getchar() = '#') /*#表示空樹*/return NULL;else T = (BiTree)malloc(

9、sizeof(BiTNode); /生成根節(jié)點T->data = ch;T->lchild = CreateTree(); /構(gòu)造左子樹T->rchild = CreateTree(); /構(gòu)造右子樹return T;int deep(BiTree T) /*求二叉樹深度*/int lh, rh;if (T = NULL) return 0;else lh = deep(T->lchild);rh = deep(T->rchild);return (lh > rh ? lh : rh) + 1;int leaf(BiTree T) /*求葉子結(jié)點數(shù)*/int

10、 m, n;if (!T) /*空樹沒有葉子*/return 0;else if (!T->lchild && !T->rchild) /*葉子結(jié)點*/return 1;else /*左子樹的結(jié)點數(shù)加上右子樹的結(jié)點數(shù)*/m = leaf(T->lchild);n = leaf(T->rchild);return m + n;int OneChild(BiTree T) /*求1度結(jié)點數(shù)*/int n = 0;if (T = NULL) return 0;else if (T->lchild = NULL&&T->rchild

11、!= NULL) | (T->lchild != NULL&&T->rchild = NULL) n = 1;return OneChild(T->lchild) + OneChild(T->rchild) + n;int TwoChild(BiTree T) /*求2度結(jié)點數(shù)*/int n = 0;if (T = NULL) return 0;else if (T->lchild != NULL&&T->rchild != NULL)n = 1;return TwoChild(T->lchild) + TwoChild

12、(T->rchild) + n;void Exchange(BiTree T) /*二叉樹左右子樹交換*/BiTree temp;if (T) temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;Exchange(T->lchild);Exchange(T->rchild);BiTree InorderLastNode(BiTree T) /*找二叉樹中序遍歷最后一個結(jié)點*/if(T)while (T->rchild)T = T->rchild;return T;int main(

13、) BiTree T;printf("以前序遍歷的二叉樹:");T = CreateTree();printf("n先序遍歷:");Preorder(T);printf("n");printf("n中序遍歷:");Inorder(T);printf("n");printf("n后序遍歷:");Postorder(T);printf("n");printf("n樹的深度=%dn", deep(T);printf("葉子結(jié)點數(shù)=%

14、dn", leaf(T);printf("1度結(jié)點數(shù)=%dn", OneChild(T);printf("2度結(jié)點數(shù)=%dn", TwoChild(T);printf("n二叉樹中序遍歷最后一個結(jié)點為:%c", InorderLastNode(T)->data);printf("n");printf("n交換后的二叉樹先序遍歷為:");Exchange(T); Preorder(T);printf("n交換后的二叉樹中序遍歷為:");Inorder(T);pr

15、intf("n交換后的二叉樹后序遍歷為:");Postorder(T);printf("n");printf("n交換后的二叉樹中序遍歷最后一個結(jié)點為:%c", InorderLastNode(T)->data);printf("n");return 0;4程序執(zhí)行后屏幕上的輸入輸出內(nèi)容       A      /     B    /