樹和二叉樹1——鍊式二叉樹基礎

本文代碼基于【資料結構】【嚴蔚敏】【清華大學】

包含了大多數二叉樹的基本操作

1.準備部分的代碼：

用c++其實就是用了個max()函數

#include <stdio.h>
#include <stdlib.h>//malloc和exit函數所需頭檔案 
#include <iostream>
using namespace std;
#define MaxSize 	100
typedef char ElemType;

當然也可以改成C，記得加上一個自定義max函數

#include <stdio.h>
#include <stdlib.h>//malloc和exit函數所需頭檔案 
#define MaxSize 	100
typedef char ElemType;

int max(int a,int b)
{
	return a>b?a:b;
 }

2.構造二叉樹結點

包括資料域和左右孩子指針

typedef struct BiTNode {
    ElemType    data;
    struct BiTNode	*lchild, *rchild; 	// 左右孩子指針
} BiTNode, *BiTree;

3.先序輸入二叉樹中結點的值

一些必要的注解：

①TheBinaryTree為結構體指針,指向結構體

BiTree TheBinaryTree=BiTNode *TheBinaryTree

②T為TheBinaryTree的引用，是結構體指針

BiTree &T= BiTNode *&T

③BT是結構指針TheBinaryTree的指針，BT指向結構體指針

BiTNode **BT=BiTree *BT

所有有兩種 CreateBiTree寫法：

void CreateBiTree(BiTNode* &T)//BiTree &T== BiTNode* &T
{
    //  按先序次序輸入二叉樹中結點的值
    //  構造二叉連結清單表示的二叉樹T。
    ElemType	ch;

    static	int	i = 0;
    char	pch[] = "ABC$$DE$G$$F$$$";				    // 欲産生的 先序序列。圖6.8（b）
    ch = pch[i++];

    if(ch == '$') 										// 空樹
        T = NULL;
    else {
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T)											// 檢測是否申請結點成功
            exit(-1);
        T->data = ch; 									// 生成根結點
        CreateBiTree(T->lchild); 						// 構造左子樹
        CreateBiTree(T->rchild); 						// 構造右子樹
    }
}

void CreateBiTree_Pointer(BiTNode **BT)//BiTree *BT BT此時為指針的指針， BiTNode* *BT==BiTree *BT 
{
    //  按先序次序輸入二叉樹中結點的值
    //  構造二叉連結清單表示的二叉樹BT。
    ElemType	ch;
    static	int	i = 0;
    char	pch[] = "AB D  C  ";								// 欲産生的二叉樹 先序序列
    ch = pch[i++];
    //scanf("%c",&ch);
    if(ch == ' ') 												// 空樹
        *BT = NULL;
    else {
        *BT = (BiTree)malloc(sizeof(BiTNode));
        if(!*BT)												// 檢測是否申請結點成功
            exit(-1);
        (*BT)->data = ch; 										// 生成根結點
        CreateBiTree_Pointer(&(*BT)->lchild); 						// 構造左子樹
        CreateBiTree_Pointer(&(*BT)->rchild); 						// 構造右子樹
    }
}

4.三種周遊（遞歸）

// 中序周遊
void InOrderTraversal(BiTree BT)
{
    if(BT) {
        InOrderTraversal(BT->lchild);
        printf("%c ", BT->data);
        InOrderTraversal(BT->rchild);
    }
}

//先序周遊
void PreOrderTraversal(BiTree BT)
{
    if(BT) {
        printf("%c ", BT->data);
        PreOrderTraversal(BT->lchild);
        PreOrderTraversal(BT->rchild);
    }
}

// 後序周遊
void PostOrderTraversal(BiTree BT)
{
    if(BT) {
        PostOrderTraversal(BT->lchild);
        PostOrderTraversal(BT->rchild);
        printf("%c ", BT->data);
    }
}

5.中序周遊非遞歸周遊算法（關于其他周遊算法之後還會寫文章提到）

// 中序周遊非遞歸周遊算法
//利用壓棧 
void InOrderTraversal_NoRecursion(BiTNode *T)
{
    BiTNode	*Stack[MaxSize];//BiTree Stack[MaxSize]
    int	top = -1;

    while(T || (top != -1)) {
        while(T) {												// 一直向左并将沿途結點壓入堆棧
            Stack[++top] = T;
            T = T->lchild;
        }

        if(top != -1) {
            T = Stack[top--]; 						// 結點彈出堆棧
            printf("%c ", T->data); 				//（通路）列印結點
            T = T->rchild; 							// 轉向右子樹
        }
    }
}

6.輸出葉子結點值

// 輸出二叉樹中的葉子結點。
void PreOrderPrintLeaves(BiTree BT)
{
    if(BT) {
        if(BT->lchild == NULL && BT->rchild == NULL)
            printf("%c ", BT->data);
        PreOrderPrintLeaves(BT->lchild);
        PreOrderPrintLeaves(BT->rchild);
    }
}

7.輸出深度

// 求二叉樹的深度
int Binary_tree_Deepness(BiTNode *T)
{
    if(T == NULL)
        return 0;
    else
        if(T->lchild == NULL && T->rchild == NULL)
            return 1;
        else
            return 1 + max(Binary_tree_Deepness(T->lchild), Binary_tree_Deepness(T->rchild));
}
//表示形式2
int Binary_tree_Deepness_Post(BiTNode *T)
{
    int h1, h2;
    if(T == NULL)
        return 0;
    h1 = Binary_tree_Deepness_Post(T->lchild);
    h2 = Binary_tree_Deepness_Post(T->rchild);
    if(T->lchild == NULL && T->rchild == NULL)
        return 1;
    else
        return 1 + max(h1, h2);
}

8.求度為 2 的結點數

//求二叉樹的度為 2 的結點數算法
int BT_CountDegree2(BiTNode *T)
{
    int n1, n2; 
    if (T == NULL)
        return 0;
    else {
        n1 = BT_CountDegree2(T->lchild);
        n2 = BT_CountDegree2(T->rchild);
        if (T->lchild != NULL && T->rchild != NULL)
            return 1 + n1 + n2;
        else
            return n1 + n2;
    }
}

9.構造和銷毀

PS：完整代碼中沒用到構造和銷毀，Init某種意義上可有可無，destroy最好還是加一下

Status InitBiTree(BiTree &T)
{
    // 操作結果: 構造空二叉樹T
    T = NULL;
    return OK;
}


void DestroyBiTree(BiTree &T)
{
    // 初始條件: 二叉樹T存在。操作結果: 銷毀二叉樹T
    if(T) {	// 非空樹
        if(T->lchild) 							// 有左孩子
            DestroyBiTree(T->lchild); 			// 銷毀左孩子子樹
        if(T->rchild) 							// 有右孩子
            DestroyBiTree(T->rchild); 			// 銷毀右孩子子樹
        free(T); 								// 釋放根結點
        T = NULL; 								// 空指針賦0
    }
}

10.主函數

int	main()
{
    BiTree	TheBinaryTree;//BiTNode *TheBinaryTree

    printf("\n建立二叉樹，請輸入結點值系列：\n");
    CreateBiTree(TheBinaryTree);//TheBinaryTree為結構體指針 

    printf("\n先序周遊序列：\n");
    PreOrderTraversal(TheBinaryTree);

    printf("\n中序周遊序列：\n");
    InOrderTraversal(TheBinaryTree);
    printf("\n中序周遊序列 - 中序周遊非遞歸算法：\n");
    InOrderTraversal_NoRecursion(TheBinaryTree);

    printf("\n後序周遊序列：\n");
    PostOrderTraversal(TheBinaryTree);

    printf("\n二叉樹的深度為：\n");
    //printf("%d",Binary_tree_Deepness_Post(TheBinaryTree));
    printf("%d", Binary_tree_Deepness(TheBinaryTree));

    printf("\n葉子結點為：\n");
    PreOrderPrintLeaves(TheBinaryTree);
    
    printf("\n度為2的結點個數為：\n");
    printf("%d", BT_CountDegree2(TheBinaryTree));

    return 1;
}

便于複制完整源代碼如下：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

#define MaxSize 	100
typedef char ElemType;

typedef struct BiTNode {
    ElemType    data;
    struct BiTNode	*lchild, *rchild; 				// 左右孩子指針
} BiTNode, *BiTree;

//TheBinaryTree為結構體指針,指向結構體
//BiTree  TheBinaryTree==BiTNode *TheBinaryTree
//BiTree &T== BiTNode* &T    T為TheBinaryTree的引用，是結構體指針
//BiTNode **BT==BiTree *BT    BT是結構指針TheBinaryTree的指針， BT指向結構體指針 
void CreateBiTree(BiTNode* &T)//BiTree &T== BiTNode* &T
{
    //  按先序次序輸入二叉樹中結點的值
    //  構造二叉連結清單表示的二叉樹T。
    ElemType	ch;

    static	int	i = 0;
    char	pch[] = "ABC$$DE$G$$F$$$";				// 欲産生的 先序序列。圖6.8（b）
    ch = pch[i++];

    if(ch == '$') 										// 空樹
        T = NULL;
    else {
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T)											// 檢測是否申請結點成功
            exit(-1);
        T->data = ch; 									// 生成根結點
        CreateBiTree(T->lchild); 						// 構造左子樹
        CreateBiTree(T->rchild); 						// 構造右子樹
    }
}

void CreateBiTree_Pointer(BiTNode **BT)//BiTree *BT BT此時為指針的指針， BiTNode* *BT==BiTree *BT 
{
    //  按先序次序輸入二叉樹中結點的值
    //  構造二叉連結清單表示的二叉樹BT。
    ElemType	ch;
    static	int	i = 0;
    char	pch[] = "AB D  C  ";								// 欲産生的二叉樹 先序序列
    ch = pch[i++];
    //scanf("%c",&ch);
    if(ch == ' ') 												// 空樹
        *BT = NULL;
    else {
        *BT = (BiTree)malloc(sizeof(BiTNode));
        if(!*BT)												// 檢測是否申請結點成功
            exit(-1);
        (*BT)->data = ch; 										// 生成根結點
        CreateBiTree_Pointer(&(*BT)->lchild); 						// 構造左子樹
        CreateBiTree_Pointer(&(*BT)->rchild); 						// 構造右子樹
    }
}

// 中序周遊
void InOrderTraversal(BiTree BT)
{
    if(BT) {
        InOrderTraversal(BT->lchild);
        printf("%c ", BT->data);
        InOrderTraversal(BT->rchild);
    }
}

//先序周遊
void PreOrderTraversal(BiTree BT)
{
    if(BT) {
        printf("%c ", BT->data);
        PreOrderTraversal(BT->lchild);
        PreOrderTraversal(BT->rchild);
    }
}

// 後序周遊
void PostOrderTraversal(BiTree BT)
{
    if(BT) {
        PostOrderTraversal(BT->lchild);
        PostOrderTraversal(BT->rchild);
        printf("%c ", BT->data);
    }
}

// 中序周遊非遞歸周遊算法
//利用壓棧 
void InOrderTraversal_NoRecursion(BiTNode *T)
{
    BiTNode	*Stack[MaxSize];//BiTree Stack[MaxSize]
    int	top = -1;

    while(T || (top != -1)) {
        while(T) {												// 一直向左并将沿途結點壓入堆棧
            Stack[++top] = T;
            T = T->lchild;
        }

        if(top != -1) {
            T = Stack[top--]; 						// 結點彈出堆棧
            printf("%c ", T->data); 				//（通路）列印結點
            T = T->rchild; 							// 轉向右子樹
        }
    }
}

// 輸出二叉樹中的葉子結點。
void PreOrderPrintLeaves(BiTree BT)
{
    if(BT) {
        if(BT->lchild == NULL && BT->rchild == NULL)
            printf("%c ", BT->data);
        PreOrderPrintLeaves(BT->lchild);
        PreOrderPrintLeaves(BT->rchild);
    }
}

// 求二叉樹的深度
int Binary_tree_Deepness(BiTNode *T)
{
    if(T == NULL)
        return 0;
    else
        if(T->lchild == NULL && T->rchild == NULL)
            return 1;
        else
            return 1 + max(Binary_tree_Deepness(T->lchild), Binary_tree_Deepness(T->rchild));
}

int Binary_tree_Deepness_Post(BiTNode *T)
{
    int h1, h2;

    if(T == NULL)
        return 0;

    h1 = Binary_tree_Deepness_Post(T->lchild);
    h2 = Binary_tree_Deepness_Post(T->rchild);
    if(T->lchild == NULL && T->rchild == NULL)
        return 1;
    else
        return 1 + max(h1, h2);
}

//求二叉樹的度為 2 的結點數算法
int BT_CountDegree2(BiTNode *T)
{
    int n1, n2; 
    if (T == NULL)
        return 0;
    else {
        n1 = BT_CountDegree2(T->lchild);
        n2 = BT_CountDegree2(T->rchild);
        if (T->lchild != NULL && T->rchild != NULL)
            return 1 + n1 + n2;
        else
            return n1 + n2;
    }
}

int	main()
{
    BiTree	TheBinaryTree;//BiTNode *TheBinaryTree

    printf("\n建立二叉樹，請輸入結點值系列：\n");
    CreateBiTree(TheBinaryTree);//TheBinaryTree為結構體指針 

    printf("\n先序周遊序列：\n");
    PreOrderTraversal(TheBinaryTree);

    printf("\n中序周遊序列：\n");
    InOrderTraversal(TheBinaryTree);
    printf("\n中序周遊序列 - 中序周遊非遞歸算法：\n");
    InOrderTraversal_NoRecursion(TheBinaryTree);

    printf("\n後序周遊序列：\n");
    PostOrderTraversal(TheBinaryTree);

    printf("\n二叉樹的深度為：\n");
    //printf("%d",Binary_tree_Deepness_Post(TheBinaryTree));
    printf("%d", Binary_tree_Deepness(TheBinaryTree));

    printf("\n葉子結點為：\n");
    PreOrderPrintLeaves(TheBinaryTree);
    
    printf("\n度為2的結點個數為：\n");
    printf("%d", BT_CountDegree2(TheBinaryTree));

    return 1;
}

樹和二叉樹1——鍊式二叉樹基礎

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器