二叉樹
(有關二叉樹的基本定義與存儲結構已在這裡簡要說明--->https://blog.csdn.net/qq_38193883/article/details/98869738)
下面是二叉樹的基本操作：
- 定義存儲結構：
typedef char Elemtype;
//定義
typedef struct Tnode{
Elemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*Tree;
- 建立二叉樹：
CreateTree(Tree &root){
//僞代碼，不可直接用
if(ch=='空指針'){
root=NULL;
}
else{
root->data=ch;
CreateTree(root->lchild);//遞歸周遊建立左子樹
CreateTree(root->rchild);//遞歸周遊建立右子樹
}
}
- 二叉樹的周遊：
a. 遞歸周遊：
void DLR(Tree root){
if(!root){
return;
}
printf("%c ",root->data);//先（中）（後）序就放最前（中間）（後）面
DLR(root->lchild);
DLR(root->rchild);
}
b.非遞歸（堆棧）周遊
/* 非遞歸中序周遊（堆棧:為了偷懶直接用庫函數了，沒人有意見吧，很明顯。沒有！）
1.遇到一個節點，就把他限壓入棧，然後周遊它的左子樹
2.當左子樹周遊結束後 ，從棧頂彈出并通路列印資料
3.然後周遊右子樹
*/
void LDRstack(Tree root){
Tree T;
stack<Tree> S;
while(T || !S.empty()) {
//以下while循環相當于遞歸中的 LDR(root->lchild);
while(T){
S.push(T);
T->lchild;//一直周遊左孩子并入棧
}
if(!S.empty())
{// 若棧不空
T=S.top();
S.pop();//出棧
//中就中在這
printf("%c ",T->data);
//再用同樣的方式去處理右子樹
T=T->rchild;
}
}
}
/* 層次周遊（這裡星星要用采用隊列）
1. 起初：根結點入隊
2.從隊列中取出一個元素
3.通路該節點，該節點帶左右孩子入隊
4. 重複 2.->3.->2.->3.->....->直到隊列為空
*/
void Leveltravel(Tree root){
queue<Tree> Q; Tree T;
if(root==NULL){
return ;
}
Q.push(T);
while(!Q.empty()){
T=Q.front();
Q.pop();
printf("%c ",T->data);
if(T->lchild){
Q.push(T->lchild);
}
if(T->rchild){
Q.push(T->rchild);
}
}
}
- 基于周遊的新功能：
- 統計葉子節點的個數
- 查找資料為‘X’的節點
- 複制二叉樹
測試執行個體（AC）：（i含魅力注釋i）
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<queue>// 隊列
#include<stack>//棧
using namespace std;
typedef char Elemtype;
//定義
typedef struct Tnode{
Elemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*Tree;
//設定全局變量
int count=0;//計數器（統計葉子）
int index=0;//字元數組下标
//測試案例： char str[]="ABDH###E##CF##G##";（由于建立方法采用先序，是以輸入時用先序序列）
char str[100];
//建立一棵二叉樹
int CreateTree(Tree &root){
char ch;
ch=str[index++];
if(ch=='#'){
root=NULL;
}
else{
root=(Tree)malloc(sizeof(Tnode));
if(!root){
return -1;
}
root->data=ch;
CreateTree(root->lchild);
CreateTree(root->rchild);
}
return 0;
}
//用遞歸進行的周遊算法（3種：先序周遊，中序周遊，後序周遊）
void DLR(Tree root){
if(!root){
return;
}
printf("%c ",root->data);//先序就放最前面
DLR(root->lchild);
DLR(root->rchild);
}
void LDR(Tree root){
if(!root){
return ;
}
LDR(root->lchild);
printf("%c ",root->data);//中序就放中間
LDR(root->rchild);
}
void LRD(Tree root){
if(!root){
return;
}
LRD(root->lchild);
printf("%c ",root->data);//後序就放後面
LRD(root->rchild);
}
//在周遊算法基礎上拓展的功能：
/*1. 查詢二叉樹中某個值為n的結點*/
Tree Survey(Tree root,Elemtype n,Tree p){
if(root){
if(root->data==n){
p=root;
return p;
}
else{
if(Survey(root->lchild,n,p)){
return Survey(root->lchild,n,p);
}
else{
return Survey(root->rchild,n,p);
}
}
}
else{
return NULL;
}
}
/*2.統計二叉樹中葉子結點的個數(兩種方法)
a. 使用全局變量Count計數
b. 利用函數傳回值，Count = Leftcount + Rightcount
*/
int Count1(Tree root){
if(!root){
return 0;
}
if((!root->lchild)&&(!root->rchild)){
count++;
}
Count1(root->lchild);
Count1(root->rchild);
}
int Count2(Tree root){
if(!root){
return 0;
}
if((!root->lchild)&&(!root->rchild)){
return 1;
}
int l=Count2(root->lchild);
int r=Count2(root->rchild);
return l+r;
}
//3. 求二叉樹的深度(後序周遊):求得左、右子樹深度的最大值，然後加 1
int Heigh(Tree root){
int hl,hr;
if(!root) return 0;
else{
hl=Heigh(root->lchild);
hr=Heigh(root->rchild);
return hl>hr?hl+1:hr+1;
}
}
//4. 複制二叉樹(後序周遊)
Tree Copy(Tree root)//複制二叉樹t
{ Tree newtree;
if (root==NULL) newtree=NULL;
else{
newtree=(Tree)malloc(sizeof(Tnode));
newtree->data=root->data;
newtree->lchild=Copy(root->lchild);
newtree->rchild=Copy(root->rchild);
}
return newtree;
}//結束Copy
int main(){
Tree T=NULL,p;
printf("請輸入你要建立的二叉 '檸檬樹' 序列：\n");
scanf("%s",str);
CreateTree(T);
printf("先序周遊周星星的檸檬樹：\n");
DLR(T);
printf("\n中序周遊周星星的檸檬樹：\n");
LDR(T);
printf("\n後序周遊周星星的檸檬樹：\n");
LRD(T);
p=Survey(T,'B',p);
printf("\n%c\n",p->data);
Count1(T);
printf("葉子節點共有%d個\n",count);
printf("葉子節點共有%d個\n",Count2(T));
printf("————此檸檬樹共有%d層————\n",Heigh(T));
return 0;
}
-
運作結果：
-
正經緻謝：(左圖是享受二叉樹的過程，别問我什麼感受，看右圖（酸爽）)