---

一，實驗目的

1. 深入理解樹與二叉樹的基本概念，包括節點、度、層次、深度等，清晰區分二叉樹與一般樹的結構特點，為后續學習和應用打下堅實基礎。
2. 熟練掌握用遞歸方法實現二叉樹的遍歷，通過遞歸算法的設計和實現，深刻體會遞歸思想在處理樹結構數據時的簡潔性和高效性，提高對遞歸算法的運用能力。
3. 掌握借助棧或隊列實現二叉樹遍歷的非遞歸迭代方法，理解棧和隊列在模擬遞歸過程中的作用，培養利用數據結構解決問題的能力，拓寬算法設計思路。
4. 熟練掌握構造Huffman樹、Huffman編碼等操作，理解Huffman樹的原理和應用場景，能夠根據給定的字符頻率構建最優的Huffman樹，并生成相應的Huffman編碼，提高對數據壓縮等實際問題的解決能力。
5. 通過對二叉樹相關知識的學習和編程實踐，加深對二叉樹的理解，逐步培養運用二叉樹結構解決實際問題的編程能力，提升算法設計、調試和分析的綜合素養。

二，問題描述

編程實現二叉樹的下列基本運算。
（1）創建一棵二叉樹；
（2）求二叉樹中結點的總數；
（3）統計二叉樹的葉結點個數；
（4）求二叉樹的深度；
（5）用按層次順序遍歷二叉樹的方法，統計樹中具有度為1的結點數目；
（6）交換二叉樹每個結點的左孩子和右孩子；
（7）輸出二叉樹。

三，基本要求

（1）采用二叉鏈表作為二叉樹結點的存儲結構；
（2）設計實現上述各種運算的算法；
（3）設計主函數以完成對上述算法的調用，并輸出結果；
（4）完善參考程序；
（5）設計測試數據，上機調試、測試完善后的參考程序，保存并打印測試結果，對算法性能進行分析。

四，實驗操作

1，雙擊Visual Studio程序快捷圖標，啟動程序。

2，之前創建過項目的話，直接打開即可，這里選擇【創建新項目】。

3，單擊選擇【空項目】——單擊【下一步】按鈕。

4，編輯好項目的名稱和存放路徑，然后單擊【創建】按鈕。

5，創建C++程序文件，右擊【源文件】——選擇【添加】——【新建項】。

6，輸入項目名稱，單擊【添加】按鈕。

7，編寫代碼，單擊運行按鈕，運行程序。

五，示例代碼

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>typedef struct BiTNode { 			// 定義二叉樹的結點結構char data;   					// 假定樹結點的元素類型為charstruct BiTNode* lchild; 			// 左指針struct BiTNode* rchild; 		// 右指針
} BiTNode, * BiTree;void CreateBiTree(BiTree& T)
{  // 先序遞歸遍歷方式創建一棵二叉樹char ch;scanf("\n%c", &ch);     								// 輸入根結點的值if (ch == '#') 											// 終止項T = NULL;else{T = (BiTree)malloc(sizeof(BiTNode)); 				// 創建根結點if (!T)exit(-1);T->data = ch;printf("\n請輸入%c結點的左子結點(#表無):", T->data); // 先序遍歷創建左子樹CreateBiTree(T->lchild);printf("\n請輸入%c結點的右子結點(#表無):", T->data); // 先序遍歷創建右子樹CreateBiTree(T->rchild);}
}//統計二叉樹的葉子結點個數。
int LeafNodeCount(BiTree T)
{if (T == NULL)return 0;                //如果是空樹，則葉子結點個數為0else if (T->lchild == NULL && T->rchild == NULL) // 判斷該結點是否是葉子結點(左孩子右孩子都為空),若是則返回1return 1;elsereturn LeafNodeCount(T->lchild) + LeafNodeCount(T->rchild);
}//交換二叉樹每個結點的左孩子和右孩子。
void ChangeLR(BiTree T)
{BiTree p;if (T == NULL || (T->lchild == NULL && T->rchild == NULL))return;else{p = T->lchild;T->lchild = T->rchild;T->rchild = p;}ChangeLR(T->lchild);ChangeLR(T->rchild); // 交換右子樹上結點的左右孩子
}
// 統計二叉樹中度為1的結點數
int D1_Nodes(BiTree T)
{int  num1, num2;if (T == NULL || (!T->lchild && !T->rchild))return 0;num1 = D1_Nodes(T->lchild);num2 = D1_Nodes(T->rchild);if (T->lchild && !T->rchild)	// 若結點T的左子樹非空，右子樹空，則返回左// 子樹上度為1的結點數加1（當前結點度為1）return num1 + 1;else if (!T->lchild && T->rchild)return num2 + 1;elsereturn num1 + num2;
}//求二叉樹結點數目
int Nodes(BiTree  T)
{int num1, num2;if (T == NULL)return 0;else {num1 = Nodes(T->lchild);				// 統計左子樹的結點數num2 = Nodes(T->rchild);				// 統計右子樹的結點數return num1 + num2 + 1; // 左右子樹結點總數加1（當前結點）}
}// 求二叉樹的深度
int BiTreeDepth(BiTree T)
{int leftdep, rightdep;if (T == NULL) // 終止項return 0;else{leftdep = BiTreeDepth(T->lchild);rightdep = BiTreeDepth(T->rchild);return (leftdep > rightdep) ? (leftdep + 1) : (rightdep + 1);}
}
//以括號表示格式輸出二叉樹
void OutputBiTree(BiTree T)
{		// 先序遞歸遍歷方式輸出括號表示的二叉樹if (T != NULL)									// 終止項{printf("%c", T->data);						// 訪問根結點if (T->lchild != NULL || T->rchild != NULL){printf("(");							// 根的孩子用圓括號對括OutputBiTree(T->lchild);				// 先序遍歷輸出左子樹if (T->rchild != NULL)printf("，");						// 根的左右孩子以“，”分隔OutputBiTree(T->rchild);				// 先序遍歷輸出右子樹printf(")");							// 根的孩子用圓括號對括}}
}void main()
{int n;BiTNode* proot; 						// 定義樹proot = NULL; 						// 初始化為空樹printf("請輸入根結點元素(#表無):");		// 創建二叉樹CreateBiTree(proot);printf("\n(1)二叉樹創建成功！其括號表示格式輸出：\n\t");OutputBiTree(proot);printf("\n");n = Nodes(proot);printf("(2)二叉樹結點總數是：%d\n", n);n = LeafNodeCount(proot);printf("(3)二叉樹的葉子結點數為：%d\n", n);n = BiTreeDepth(proot);printf("(4)二叉樹的深度是：%d\n", n);n = D1_Nodes(proot);printf("(5)二叉樹中度為1的結點數是：%d\n", n);ChangeLR(proot);printf("(6)交換所有結點的左右孩子后二叉樹括號表示法輸出：\n\t");OutputBiTree(proot);printf("\n");
}

六，運行效果

1，實驗測試效果。

2，編寫代碼運行后的效果。