程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言實現二叉樹的常用的算法(遞歸與非遞歸實現遍歷)

C語言實現二叉樹的常用的算法(遞歸與非遞歸實現遍歷)

編輯：關於C

[cpp]
隊列頭文件：
#include <stdio.h>

#include "BinaryTree.h"

//
// 隊列頭文件：Queue.h

#ifndef QUEUE_H
#define QUEUE_H

//
// 隊列最大元素個數
#define MAX_QUEUE_SIZE 10

typedef BTree QueueElemType;

//
// 隊列結構體
typedef struct tagQueue
{
    BTree *base;
    int front;      // 頭指針指示器，若隊列不空，則指向隊列中隊頭元素
    int rear;       // 尾指針指示呂，若隊列不空，則指向隊列隊尾的下一個位置
}Queue;

//
// 構造一個空的隊列
int InitializeQueue(Queue *pQueue);

//
// 判斷隊列是否為空
int IsQueueEmpty(Queue queue);

//
// 判斷隊列是否為滿
int IsQueueFull(Queue queue);

//
// 入隊
int EnQueue(Queue *pQueue, QueueElemType e);

//
// 退隊
int DeQueue(Queue *pQueue, QueueElemType *e);
#endif

隊列頭文件：
#include <stdio.h>

#include "BinaryTree.h"

//
// 隊列頭文件：Queue.h

#ifndef QUEUE_H
#define QUEUE_H

//
// 隊列最大元素個數
#define MAX_QUEUE_SIZE 10

typedef BTree QueueElemType;

//
// 隊列結構體
typedef struct tagQueue
{
BTree *base;
int front; // 頭指針指示器，若隊列不空，則指向隊列中隊頭元素
int rear; // 尾指針指示呂，若隊列不空，則指向隊列隊尾的下一個位置
}Queue;

//
// 構造一個空的隊列
int InitializeQueue(Queue *pQueue);

//
// 判斷隊列是否為空
int IsQueueEmpty(Queue queue);

//
// 判斷隊列是否為滿
int IsQueueFull(Queue queue);

//
// 入隊
int EnQueue(Queue *pQueue, QueueElemType e);

//
// 退隊
int DeQueue(Queue *pQueue, QueueElemType *e);
#endif[cpp] view plaincopyprint?
隊列實現文件:

#include <stdio.h>
#include <stdlib.h>

#include "Queue.h"
#include "BinaryTree.h"

//
// 循環隊列的實現文件：Queue.c

//
// 構造一個空的隊列
int InitializeQueue(Queue *pQueue)
{
    pQueue->base = (QueueElemType *)malloc(sizeof(QueueElemType) * MAX_QUEUE_SIZE);

    // 申請空間失敗，則退出程序
    if (pQueue->base == NULL)
    {
        exit(OVERFLOW);
    }

    pQueue->front = pQueue->rear = 0;

    return OK;
}

//
// 判斷隊列是否為空
// 返回0表示非空，返回非0，表示空
int IsQueueEmpty(Queue queue)
{
    return !(queue.front - queue.rear);
}

//
// 判斷隊列是否為滿
// 返回0表示示滿，返回非0，表示已滿
int IsQueueFull(Queue queue)
{
    return (queue.rear + 1) % MAX_QUEUE_SIZE == queue.front ;
}

//
// 入隊
int EnQueue(Queue *pQueue, QueueElemType e)
{
    if (IsQueueFull(*pQueue))
    {
        printf("隊列已經滿，不能入隊！\n");

        return ERROR;
    }
    else
    {
        pQueue->base[pQueue->rear] = e;
        pQueue->rear = (pQueue->rear + 1) % MAX_QUEUE_SIZE;

        return OK;
    }
}

//
// 退隊
int DeQueue(Queue *pQueue, QueueElemType *e)
{
    if (IsQueueEmpty(*pQueue))
    {
        printf("隊列為空，不能執行退隊操作\n");

        return ERROR;
    }
    else
    {
        *e = pQueue->base[pQueue->front];
        pQueue->front = (pQueue->front + 1) % MAX_QUEUE_SIZE;

        return OK;
    }
}

隊列實現文件:

#include <stdio.h>
#include <stdlib.h>

#include "Queue.h"
#include "BinaryTree.h"

//
// 循環隊列的實現文件：Queue.c

//
// 構造一個空的隊列
int InitializeQueue(Queue *pQueue)
{
pQueue->base = (QueueElemType *)malloc(sizeof(QueueElemType) * MAX_QUEUE_SIZE);

// 申請空間失敗，則退出程序
if (pQueue->base == NULL)
{
exit(OVERFLOW);
}

pQueue->front = pQueue->rear = 0;

return OK;
}

//
// 判斷隊列是否為空
// 返回0表示非空，返回非0，表示空
int IsQueueEmpty(Queue queue)
{
return !(queue.front - queue.rear);
}

//
// 判斷隊列是否為滿
// 返回0表示示滿，返回非0，表示已滿
int IsQueueFull(Queue queue)
{
return (queue.rear + 1) % MAX_QUEUE_SIZE == queue.front ;
}

//
// 入隊
int EnQueue(Queue *pQueue, QueueElemType e)
{
if (IsQueueFull(*pQueue))
{
printf("隊列已經滿，不能入隊！\n");

  return ERROR;
}
else
{
  pQueue->base[pQueue->rear] = e;
  pQueue->rear = (pQueue->rear + 1) % MAX_QUEUE_SIZE;

return OK;
}
}

//
// 退隊
int DeQueue(Queue *pQueue, QueueElemType *e)
{
if (IsQueueEmpty(*pQueue))
{
printf("隊列為空，不能執行退隊操作\n");

  return ERROR;
}
else
{
  *e = pQueue->base[pQueue->front];
  pQueue->front = (pQueue->front + 1) % MAX_QUEUE_SIZE;

return OK;
}
}

[cpp]
棧頭文件：

#ifndef STACK_H
#define STACK_H

#include <stdio.h>

#include "BinaryTree.h"
//
// 棧的頭文件聲明部分：Stack.h

// 棧初始容量
#define STACK_INIT_SIZE 20

// 棧容量不夠用時，棧的增量
#define STACK_SIZE_INCREMENT 10

typedef BTree StackElemType;

//
// 順序棧結構體
typedef struct tagStack
{
    StackElemType *base; // 指向棧底
    StackElemType *top; // 指向棧頂
    int stackSize;       // 棧的大小
}Stack;

//
// 初始化棧
int InitStack(Stack *s);

//
// 銷毀棧
void DestroyStack(Stack *s);

//
// 入棧
void Push(Stack *s, StackElemType e);

//
// 出棧
void Pop(Stack *s, StackElemType *e);

//
// 判斷棧是否為空
int IsStackEmpty(Stack s);

//
// 取棧頂元素
int GetTop(Stack s, StackElemType *e);

#endif

棧頭文件：

#ifndef STACK_H
#define STACK_H

#include <stdio.h>

#include "BinaryTree.h"
//
// 棧的頭文件聲明部分：Stack.h

// 棧初始容量
#define STACK_INIT_SIZE 20

// 棧容量不夠用時，棧的增量
#define STACK_SIZE_INCREMENT 10

typedef BTree StackElemType;

//
// 順序棧結構體
typedef struct tagStack
{
StackElemType *base; // 指向棧底
StackElemType *top; // 指向棧頂
int stackSize; // 棧的大小
}Stack;

//
// 初始化棧
int InitStack(Stack *s);

//
// 銷毀棧
void DestroyStack(Stack *s);

//
// 入棧
void Push(Stack *s, StackElemType e);

//
// 出棧
void Pop(Stack *s, StackElemType *e);

//
// 判斷棧是否為空
int IsStackEmpty(Stack s);

//
// 取棧頂元素
int GetTop(Stack s, StackElemType *e);

#endif
[cpp]
棧實現文件：

//
// 順序棧的實現文件：Stack.c

#include <stdio.h>
#include <stdlib.h>

#include "Stack.h"

//
// 初始化棧
int InitStack(Stack *s)
{
    s->base = (StackElemType *)malloc(sizeof(StackElemType) * STACK_INIT_SIZE);

    if (!s->base) // 申請棧內存失敗
    {
        exit(OVERFLOW);
    }

    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;

    return OK;
}

//
// 銷毀棧
void DestroyStack(Stack *s)
{
    if (s != NULL)
    {
        free(s->base);

        s->top = NULL;
        s->base = NULL;

        s->stackSize = 0;
    }
}

//
// 入棧
void Push(Stack *s, StackElemType e)
{
    StackElemType *tmp;
    if (s->top - s->base >= s->stackSize) // 棧已經滿
    {
        tmp = (StackElemType *)realloc(s->base, (STACK_SIZE_INCREMENT + s->stackSize)
                                                 * sizeof(StackElemType));
        if (!tmp)
        {
            exit(OVERFLOW); // 重新分配失敗則退出
        }

        s->base = tmp;
        s->top = s->base + s->stackSize;
        s->stackSize += STACK_SIZE_INCREMENT;
    }

    *(s->top) = e;
    s->top++;
}

//
// 出棧
void Pop(Stack *s, StackElemType *e)
{
    if (s->top == s->base) // 如果棧為空棧
    {
        return;
    }

    *e = *(--s->top);
}

//
// 判斷棧是否為空
// 返回非0表示空
int IsStackEmpty(Stack s)
{
    return !(s.top - s.base);
}

//
// 取棧頂元素
int GetTop(Stack s, StackElemType *e)
{
    if (!IsStackEmpty(s))
    {
        *e = *(s.top - 1); // 此處出錯，原因？

        return OK;
    }
    else
    {
        return ERROR;
    }
}

棧實現文件：

//
// 順序棧的實現文件：Stack.c

#include <stdio.h>
#include <stdlib.h>

#include "Stack.h"

//
// 初始化棧
int InitStack(Stack *s)
{
s->base = (StackElemType *)malloc(sizeof(StackElemType) * STACK_INIT_SIZE);

if (!s->base) // 申請棧內存失敗
{
exit(OVERFLOW);
}

s->top = s->base;
s->stackSize = STACK_INIT_SIZE;

return OK;
}

//
// 銷毀棧
void DestroyStack(Stack *s)
{
    if (s != NULL)
    {
  free(s->base);

s->top = NULL;
s->base = NULL;

s->stackSize = 0;
}
}

//
// 入棧
void Push(Stack *s, StackElemType e)
{
StackElemType *tmp;
if (s->top - s->base >= s->stackSize) // 棧已經滿
{
  tmp = (StackElemType *)realloc(s->base, (STACK_SIZE_INCREMENT + s->stackSize)
                                        * sizeof(StackElemType));
  if (!tmp)
  {
   exit(OVERFLOW); // 重新分配失敗則退出
  }

  s->base = tmp;
  s->top = s->base + s->stackSize;
  s->stackSize += STACK_SIZE_INCREMENT;
}

*(s->top) = e;
s->top++;
}

//
// 出棧
void Pop(Stack *s, StackElemType *e)
{
if (s->top == s->base) // 如果棧為空棧
{
return;
}

*e = *(--s->top);
}

//
// 判斷棧是否為空
// 返回非0表示空
int IsStackEmpty(Stack s)
{
return !(s.top - s.base);
}

//
// 取棧頂元素
int GetTop(Stack s, StackElemType *e)
{
if (!IsStackEmpty(s))
{
*e = *(s.top - 1); // 此處出錯，原因？

  return OK;
}
else
{
  return ERROR;
}
}
[cpp]
二叉樹頭文件：
#include <stdio.h>

//
// 二叉樹的頭文件：BinaryTree.h

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#define OK 1
#define ERROR 0
#define OVERFLOW -1

//
// 結點的數據的類型
typedef char ElemType;

//
// 二叉樹結構體
typedef struct tagBinaryTree
{
    ElemType data;                 // 數據
    struct tagBinaryTree *lchild;     // 指向左孩子
    struct tagBinaryTree *rchild;     // 指向右孩子
}BTree;

#endif

二叉樹頭文件：
#include <stdio.h>

//
// 二叉樹的頭文件：BinaryTree.h

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#define OK 1
#define ERROR 0
#define OVERFLOW -1

//
// 結點的數據的類型
typedef char ElemType;

//
// 二叉樹結構體
typedef struct tagBinaryTree
{
ElemType data;                 // 數據
struct tagBinaryTree *lchild;     // 指向左孩子
struct tagBinaryTree *rchild;     // 指向右孩子
}BTree;

#endif
[cpp]
二叉樹實現文件及測試：
#include <stdio.h>
#include <stdlib.h>

#include "BinaryTree.h"
#include "Queue.h"
#include "Stack.h"

/*****************************************************************************
* 方法名：CreateBinaryTree
* 描述：遞歸創建一棵二叉樹,按先序輸入二叉樹中結點的元素的值，“#”號表示空樹
* 參數： pBTree--指向BTree結構體的指針的指針
* 返回值：返回OK--表示創建成功
*         返回ERROR--表示創建失敗
******************************************************************************/
int CreateBinaryTree(BTree **pBTree)
{
    ElemType data;

    scanf("%c", &data);

    if (data == '#')
    {
        *pBTree = NULL;

        return OK;
    }
    else
    {
        if (((*pBTree) = (BTree *)malloc(sizeof(BTree))) == NULL)
        {
            exit(OVERFLOW);
        }

        (*pBTree)->data = data;
        CreateBinaryTree(&(*pBTree)->lchild); // 創建左子樹
        CreateBinaryTree(&(*pBTree)->rchild); // 創建右子樹
    }

    return OK;
}

/*****************************************************************************
* 方法名：PreOrderTraverse
* 描述：先序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void PreOrderTraverse(BTree *pBTree)
{
    if (pBTree)
    {
        printf("%c", pBTree->data);       // 先序訪問根結點

        PreOrderTraverse(pBTree->lchild); // 先序遍歷左子樹
        PreOrderTraverse(pBTree->rchild); // 先序遍歷右子樹
    }
}

/*****************************************************************************
* 方法名：InOrderTraverse
* 描述：中序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void InOrderTraverse(BTree *pBTree)
{
    if (pBTree)
    {
        InOrderTraverse(pBTree->lchild); // 中序遍歷左子樹
        printf("%c", pBTree->data);       // 中序訪問根結點
        InOrderTraverse(pBTree->rchild); // 中序遍歷右子樹
    }
}

/*****************************************************************************
* 方法名：PostOrderTraverse
* 描述：後序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void PostOrderTraverse(BTree *pBTree)
{
    if (pBTree)
    {
        PostOrderTraverse(pBTree->lchild);   // 後序遍歷左子樹
        PostOrderTraverse(pBTree->rchild);   // 後序遍歷右子樹
                printf("%c", pBTree->data); // 後序訪問根結點
    }
}

/*****************************************************************************
* 方法名：LevelOrderTraverse
* 描述：層序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void LevelOrderTraverse(BTree *pBTree)
{
    Queue queue;         // 隊列變量
    QueueElemType e;     // 隊列元素指針變量

    InitializeQueue(&queue); // 初始化隊列

    if (pBTree != NULL)
    {
        EnQueue(&queue, *pBTree); // 將根結點指針入隊
    }

    while (!IsQueueEmpty(queue))
    {
        DeQueue(&queue, &e);

        printf("%c", e.data);

        if (e.lchild != NULL)   // 若存在左孩子，則左孩子入隊
        {
            EnQueue(&queue, *e.lchild);
        }

        if (e.rchild != NULL)   // 若存在右孩子，則右孩子入隊
        {
            EnQueue(&queue, *e.rchild);
        }
    }
}

/*****************************************************************************
* 方法名：GetDepth
* 描述：獲取樹的深度
* 參數： pBTree--指向BTree結構體的指針
* 返回值：樹的深度
******************************************************************************/
int GetDepth(BTree *pBTree)
{
    int depth = 0;
    int leftDepth = 0;
    int rightDepth = 0;

    if (pBTree)
    {
        leftDepth = GetDepth(pBTree->lchild); // 獲取左子樹的深度
        rightDepth = GetDepth(pBTree->rchild); // 獲取右子樹的深度

        depth = leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
    }

    return depth;
}

/*****************************************************************************
* 方法名：IsLeaf
* 描述：判斷該結點是否為葉子結點
* 參數： node--結點
* 返回值：1--表示葉子結點，0--表示非葉子結點
******************************************************************************/
int IsLeaf(BTree node)
{
    if (node.lchild == NULL && node.rchild == NULL)
    {
        return 1;
    }

    return 0;
}

/*****************************************************************************
* 方法名：TraverseLeafNodes
* 描述：遍歷所有的葉子結點
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void TraverseLeafNodes(BTree *pBTree)
{
    if (pBTree != NULL)
    {
        if (1 == IsLeaf(*pBTree))
        {
            printf("%c", pBTree->data);
        }
        else
        {
            TraverseLeafNodes(pBTree->lchild);
            TraverseLeafNodes(pBTree->rchild);
        }
    }
}

//
// 判斷一棵二叉樹是否為平衡二叉樹
// 平衡二叉樹的定義: 如果任意節點的左右子樹的深度相差不超過1，那這棵樹就是平衡二叉樹
// 算法思路：遞歸判斷每個節點的左右子樹的深度是否相差大於1，如果大於1，說明該二叉樹不
//           是平衡二叉樹，否則繼續遞歸判斷
int IsBalanceBinaryTree(BTree *pBTree)
{
    int leftDepth = 0;
    int rightDepth = 0;
    int distance = 0;

    if (pBTree != NULL)
    {
        leftDepth = GetDepth(pBTree->lchild); // 獲取左子樹的深度
        rightDepth = GetDepth(pBTree->rchild); // 獲取右子樹的深度
        distance = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth;

        return distance > 1 ? 0 : IsBalanceBinaryTree(pBTree->lchild) && IsBalanceBinaryTree(pBTree->rchild);
    }
}

//
// 獲取葉子結點的個數
int GetLeafCount(BTree *pBTree)
{
    int count = 0;

    if (pBTree != NULL)
    {
        if (IsLeaf(*pBTree))
        {
            count++;
        }
        else
        {
            count = GetLeafCount(pBTree->lchild) + GetLeafCount(pBTree->rchild);
        }
    }

    return count;
}

//
// 獲取度為1的結點的個數
int GetCountOfOneDegree(BTree *pBTree)
{
    int count = 0;

    if (pBTree != NULL)
    {
        if ((pBTree->lchild != NULL && pBTree->rchild == NULL) || (pBTree->lchild == NULL && pBTree->rchild != NULL))
        {
            count++;
        }

        count += GetCountOfOneDegree(pBTree->lchild) + GetCountOfOneDegree(pBTree->rchild);
    }

    return count;
}

//
// 獲取度為2的結點的個數
int GetCountOfTwoDegree(BTree *pBTree)
{
    int count = 0;

    if (pBTree != NULL)
    {
        if (pBTree->lchild != NULL && pBTree->rchild != NULL)
        {
            count++;
        }

        count += GetCountOfTwoDegree(pBTree->lchild) + GetCountOfTwoDegree(pBTree->rchild);
    }

    return count;
}
//
// 獲取二叉樹的結點的總數
int GetNodesCount(BTree *pBTree)
{
    int count = 0;

    if (pBTree != NULL)
    {
        count++;

        count += GetNodesCount(pBTree->lchild) + GetNodesCount(pBTree->rchild);
    }

    return count;
}

//
// 交換左右子樹
void SwapLeftRightSubtree(BTree **pBTree)
{
    BTree *tmp = NULL;

    if (*pBTree != NULL)
    {
        // 交換當前結點的左右子樹
        tmp = (*pBTree)->lchild;
        (*pBTree)->lchild = (*pBTree)->rchild;
        (*pBTree)->rchild = tmp;

        SwapLeftRightSubtree(&(*pBTree)->lchild);
        SwapLeftRightSubtree(&(*pBTree)->rchild);
    }
}

//
// 判斷值e是否為二叉樹中某個結點的值，返回其所在的層數，返回0表示不在樹中
int GetLevelByValue(BTree *pBTree, ElemType e)
{
    int leftDepth = 0;
    int rightDepth = 0;
    int level = 0;

    if (pBTree->data == e)//這裡的1是相對於以pBTree為根節點的層數值。
    {
        return 1;
    }

    if (pBTree->lchild != NULL)//leftDepth所代表的層數是相對以pBTree的左節點為根的樹的層數
    {
        leftDepth = GetLevelByValue(pBTree->lchild, e);
    }

    if (pBTree->rchild != NULL)
    {
        // rightDepth所代表的層數是相對以pBTree的右節點為根的樹的層數
        rightDepth = GetLevelByValue(pBTree->rchild, e);
    }

    //
    // 查找結果要麼在左子樹找到，要麼在右子樹中找到，要麼找不到
    if (leftDepth > 0 && rightDepth == 0) // 在左子樹中找到
    {
        level = leftDepth;
    }
    else if (leftDepth == 0 && rightDepth > 0) // 在右子樹中找到
    {
        level = rightDepth;
    }

    if (leftDepth != 0 || rightDepth != 0) // 判斷是否找到該結點
    {
        level++;
    }

    return level;
}

//
// 非遞歸中序遍歷
void NoneRecursionInOrder(BTree tree)
{
    Stack s;
    StackElemType *p = NULL, *q;

    q = (StackElemType *)malloc(sizeof(StackElemType)); // 用於指向退棧元素的地址
    InitStack(&s);
    p = &tree;

    while (p || !IsStackEmpty(s))
    {
        if (p)
        {
            Push(&s, *p);
            p = p->lchild;
        }
        else
        {
            Pop(&s, q);
            printf("%c", q->data);
            p = q->rchild;
        }
    }

    free(q);
}

//
// 非遞歸前序遍歷
void NoneRecursionPreOrder(BTree tree)
{
    Stack s;
    StackElemType *p = NULL, *q;

    q = (StackElemType *)malloc(sizeof(StackElemType)); // 用於指向退棧元素的地址
    InitStack(&s);
    p = &tree;

    while (p || !IsStackEmpty(s))
    {
        while (p)
        {
            printf("%c", p->data); // 訪問根結點
            Push(&s, *p);           // 根結點指針入棧
            p = p->lchild;          // 一直向左走到底
        }

        Pop(&s, q);
        p = q->rchild;   // 向右走一步
    }

    free(q);
}

//
// 非遞歸後序遍歷
void NoneRecursionPostOrder(BTree tree)
{
    StackElemType *stack[STACK_INIT_SIZE], *p;
    int tag[STACK_INIT_SIZE], // 值只有0和1，其中0表示該結點的左子樹已經訪問
                              // 值為1表示該結點的右子樹已經訪問
        top = 0; // 棧頂指示器

    p = &tree;

    while (p || top != 0)// 樹未遍歷完畢或者棧不空
    {
        while (p)
        {
            top++;
            stack[top] = p;
            tag[top] = 0;
            p = p->lchild; // 從根開始向左走到底
        }

        if (top > 0) // 棧不空
        {
            if (tag[top] == 1)// 表示已經訪問該結點的右子樹，並返回
            {
                p = stack[top--]; // 退棧
                printf("%c", p->data);

                p = NULL; // 下次進入循環時，就不會再遍歷左子樹
            }
            else // 表示剛從該結點的左子樹返回，現在開始遍歷右子樹
            {
                p = stack[top]; // 取棧頂元素
                if (top > 0) // 棧不空
                {
                    p = p->rchild;
                    tag[top] = 1; // 標識該結點的右子樹已經訪問
                }
            }
        }
    }
}

int main()
{
    BTree *tree = NULL;

    printf("按先序輸入二叉樹結點元素的值，輸入#表示空樹：\n");

    freopen("test.txt", "r", stdin);

    if (CreateBinaryTree(&tree) == OK) // 創建二叉樹
    {
        printf("二叉樹創建成功！\n");
    }

    printf("先序遍歷(#表示空子樹)：\n");
    PreOrderTraverse(tree);

    printf("\n中序遍歷(#表示空子樹)：\n");
    InOrderTraverse(tree);

    printf("\n後序遍歷(#表示空子樹)：\n");
    PostOrderTraverse(tree);

    printf("\n樹的深度為：%d\n", GetDepth(tree));

    printf("\n層序遍歷：\n");
    LevelOrderTraverse(tree);

    printf("\n遍歷葉子結點:\n");
    TraverseLeafNodes(tree);

    printf("\n葉子結點的個數：%d\n", GetLeafCount(tree));
    printf("度為1的結點的個數：%d\n", GetCountOfOneDegree(tree));
    printf("度為2的結點的個數：%d\n", GetCountOfTwoDegree(tree));
    printf("\n二叉樹的結點總數為：%d\n", GetNodesCount(tree));

    printf("\n該二叉樹是否為平衡二叉樹？\n");
    if (IsBalanceBinaryTree(tree))
    {
        printf("Yes!\n");
    }
    else
    {
        printf("No!\n");
    }

    printf("\n結點值為A的結點在第%d層\n", GetLevelByValue(tree, 'A'));
    printf("\n結點值為B的結點在第%d層\n", GetLevelByValue(tree, 'B'));
    printf("\n結點值為C的結點在第%d層\n", GetLevelByValue(tree, 'C'));
    printf("\n結點值為D的結點在第%d層\n", GetLevelByValue(tree, 'D'));
    printf("\n結點值為E的結點在第%d層\n", GetLevelByValue(tree, 'E'));
    printf("\n結點值為F的結點在第%d層\n", GetLevelByValue(tree, 'F'));
    printf("\n結點值為G的結點在第%d層\n", GetLevelByValue(tree, 'G'));
    printf("\n結點值為M的結點在第%d層\n", GetLevelByValue(tree, 'M'));

    printf("\n非遞歸中序遍歷：\n");
    NoneRecursionInOrder(*tree);

    printf("\n非遞歸前序遍歷：\n");
    NoneRecursionPreOrder(*tree);

    printf("\n非遞歸後序遍歷：\n");
    NoneRecursionPostOrder(*tree);

    printf("\n=======================================================\n");

    printf("下面執行交換左右子樹操作：\n");
    SwapLeftRightSubtree(&tree);

    printf("先序遍歷(#表示空子樹)：\n");
    PreOrderTraverse(tree);

    printf("\n中序遍歷(#表示空子樹)：\n");
    InOrderTraverse(tree);

    printf("\n後序遍歷(#表示空子樹)：\n");
    PostOrderTraverse(tree);

    printf("\n樹的深度為：%d\n", GetDepth(tree));

    printf("\n層序遍歷：\n");
    LevelOrderTraverse(tree);

    printf("\n遍歷葉子結點:\n");
    TraverseLeafNodes(tree);



    fclose(stdin);

    printf("\n");
    return 0;
}

二叉樹實現文件及測試：
#include <stdio.h>
#include <stdlib.h>

#include "BinaryTree.h"
#include "Queue.h"
#include "Stack.h"

/*****************************************************************************
* 方法名：CreateBinaryTree
* 描述：遞歸創建一棵二叉樹,按先序輸入二叉樹中結點的元素的值，“#”號表示空樹
* 參數： pBTree--指向BTree結構體的指針的指針
* 返回值：返回OK--表示創建成功
* 返回ERROR--表示創建失敗
******************************************************************************/
int CreateBinaryTree(BTree **pBTree)
{
ElemType data;

scanf("%c", &data);

if (data == '#')
{
*pBTree = NULL;

  return OK;
}
else
{
  if (((*pBTree) = (BTree *)malloc(sizeof(BTree))) == NULL)
  {
   exit(OVERFLOW);
  }

  (*pBTree)->data = data;
  CreateBinaryTree(&(*pBTree)->lchild); // 創建左子樹
  CreateBinaryTree(&(*pBTree)->rchild); // 創建右子樹
}

return OK;
}

/*****************************************************************************
* 方法名：PreOrderTraverse
* 描述：先序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void PreOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
printf("%c", pBTree->data); // 先序訪問根結點

PreOrderTraverse(pBTree->lchild); // 先序遍歷左子樹
PreOrderTraverse(pBTree->rchild); // 先序遍歷右子樹
}
}

/*****************************************************************************
* 方法名：InOrderTraverse
* 描述：中序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void InOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
  InOrderTraverse(pBTree->lchild); // 中序遍歷左子樹
  printf("%c", pBTree->data);       // 中序訪問根結點
  InOrderTraverse(pBTree->rchild); // 中序遍歷右子樹
}
}

/*****************************************************************************
* 方法名：PostOrderTraverse
* 描述：後序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void PostOrderTraverse(BTree *pBTree)
{
if (pBTree)
{
  PostOrderTraverse(pBTree->lchild);   // 後序遍歷左子樹
  PostOrderTraverse(pBTree->rchild);   // 後序遍歷右子樹
    printf("%c", pBTree->data); // 後序訪問根結點
}
}

/*****************************************************************************
* 方法名：LevelOrderTraverse
* 描述：層序遍歷二叉樹
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void LevelOrderTraverse(BTree *pBTree)
{
Queue queue; // 隊列變量
QueueElemType e; // 隊列元素指針變量

InitializeQueue(&queue); // 初始化隊列

if (pBTree != NULL)
{
EnQueue(&queue, *pBTree); // 將根結點指針入隊
}

while (!IsQueueEmpty(queue))
{
DeQueue(&queue, &e);

printf("%c", e.data);

  if (e.lchild != NULL)   // 若存在左孩子，則左孩子入隊
  {
   EnQueue(&queue, *e.lchild);
  }

  if (e.rchild != NULL)   // 若存在右孩子，則右孩子入隊
  {
   EnQueue(&queue, *e.rchild);
  }
}
}

/*****************************************************************************
* 方法名：GetDepth
* 描述：獲取樹的深度
* 參數： pBTree--指向BTree結構體的指針
* 返回值：樹的深度
******************************************************************************/
int GetDepth(BTree *pBTree)
{
int depth = 0;
int leftDepth = 0;
int rightDepth = 0;

if (pBTree)
{
leftDepth = GetDepth(pBTree->lchild); // 獲取左子樹的深度
rightDepth = GetDepth(pBTree->rchild); // 獲取右子樹的深度

depth = leftDepth > rightDepth ? leftDepth + 1: rightDepth + 1;
}

return depth;
}

/*****************************************************************************
* 方法名：IsLeaf
* 描述：判斷該結點是否為葉子結點
* 參數： node--結點
* 返回值：1--表示葉子結點，0--表示非葉子結點
******************************************************************************/
int IsLeaf(BTree node)
{
if (node.lchild == NULL && node.rchild == NULL)
{
return 1;
}

return 0;
}

/*****************************************************************************
* 方法名：TraverseLeafNodes
* 描述：遍歷所有的葉子結點
* 參數： pBTree--指向BTree結構體的指針
******************************************************************************/
void TraverseLeafNodes(BTree *pBTree)
{
if (pBTree != NULL)
{
  if (1 == IsLeaf(*pBTree))
  {
   printf("%c", pBTree->data);
  }
  else
  {
   TraverseLeafNodes(pBTree->lchild);
   TraverseLeafNodes(pBTree->rchild);
  }
}
}

//
// 判斷一棵二叉樹是否為平衡二叉樹
// 平衡二叉樹的定義: 如果任意節點的左右子樹的深度相差不超過1，那這棵樹就是平衡二叉樹
// 算法思路：遞歸判斷每個節點的左右子樹的深度是否相差大於1，如果大於1，說明該二叉樹不
// 是平衡二叉樹，否則繼續遞歸判斷
int IsBalanceBinaryTree(BTree *pBTree)
{
int leftDepth = 0;
int rightDepth = 0;
int distance = 0;

if (pBTree != NULL)
{
  leftDepth = GetDepth(pBTree->lchild); // 獲取左子樹的深度
  rightDepth = GetDepth(pBTree->rchild); // 獲取右子樹的深度
  distance = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth;

return distance > 1 ? 0 : IsBalanceBinaryTree(pBTree->lchild) && IsBalanceBinaryTree(pBTree->rchild);
}
}

//
// 獲取葉子結點的個數
int GetLeafCount(BTree *pBTree)
{
int count = 0;

if (pBTree != NULL)
{
  if (IsLeaf(*pBTree))
  {
   count++;
  }
  else
  {
   count = GetLeafCount(pBTree->lchild) + GetLeafCount(pBTree->rchild);
  }
}

return count;
}

//
// 獲取度為1的結點的個數
int GetCountOfOneDegree(BTree *pBTree)
{
int count = 0;

if (pBTree != NULL)
{
  if ((pBTree->lchild != NULL && pBTree->rchild == NULL) || (pBTree->lchild == NULL && pBTree->rchild != NULL))
  {
   count++;
  }

count += GetCountOfOneDegree(pBTree->lchild) + GetCountOfOneDegree(pBTree->rchild);
}

return count;
}

//
// 獲取度為2的結點的個數
int GetCountOfTwoDegree(BTree *pBTree)
{
int count = 0;

if (pBTree != NULL)
{
  if (pBTree->lchild != NULL && pBTree->rchild != NULL)
  {
   count++;
  }

count += GetCountOfTwoDegree(pBTree->lchild) + GetCountOfTwoDegree(pBTree->rchild);
}

return count;
}
//
// 獲取二叉樹的結點的總數
int GetNodesCount(BTree *pBTree)
{
int count = 0;

if (pBTree != NULL)
{
count++;

count += GetNodesCount(pBTree->lchild) + GetNodesCount(pBTree->rchild);
}

return count;
}

//
// 交換左右子樹
void SwapLeftRightSubtree(BTree **pBTree)
{
BTree *tmp = NULL;

if (*pBTree != NULL)
{
  // 交換當前結點的左右子樹
  tmp = (*pBTree)->lchild;
  (*pBTree)->lchild = (*pBTree)->rchild;
  (*pBTree)->rchild = tmp;

SwapLeftRightSubtree(&(*pBTree)->lchild);
SwapLeftRightSubtree(&(*pBTree)->rchild);
}
}

//
// 判斷值e是否為二叉樹中某個結點的值，返回其所在的層數，返回0表示不在樹中
int GetLevelByValue(BTree *pBTree, ElemType e)
{
int leftDepth = 0;
int rightDepth = 0;
int level = 0;

if (pBTree->data == e)//這裡的1是相對於以pBTree為根節點的層數值。
{
return 1;
}

if (pBTree->lchild != NULL)//leftDepth所代表的層數是相對以pBTree的左節點為根的樹的層數
{
leftDepth = GetLevelByValue(pBTree->lchild, e);
}

if (pBTree->rchild != NULL)
{
// rightDepth所代表的層數是相對以pBTree的右節點為根的樹的層數
rightDepth = GetLevelByValue(pBTree->rchild, e);
}

//
// 查找結果要麼在左子樹找到，要麼在右子樹中找到，要麼找不到
if (leftDepth > 0 && rightDepth == 0) // 在左子樹中找到
{
level = leftDepth;
}
else if (leftDepth == 0 && rightDepth > 0) // 在右子樹中找到
{
level = rightDepth;
}

if (leftDepth != 0 || rightDepth != 0) // 判斷是否找到該結點
{
level++;
}

return level;
}

//
// 非遞歸中序遍歷
void NoneRecursionInOrder(BTree tree)
{
Stack s;
StackElemType *p = NULL, *q;

q = (StackElemType *)malloc(sizeof(StackElemType)); // 用於指向退棧元素的地址
InitStack(&s);
p = &tree;

while (p || !IsStackEmpty(s))
{
  if (p)
  {
   Push(&s, *p);
   p = p->lchild;
  }
  else
  {
   Pop(&s, q);
   printf("%c", q->data);
   p = q->rchild;
  }
}

free(q);
}

//
// 非遞歸前序遍歷
void NoneRecursionPreOrder(BTree tree)
{
Stack s;
StackElemType *p = NULL, *q;

q = (StackElemType *)malloc(sizeof(StackElemType)); // 用於指向退棧元素的地址
InitStack(&s);
p = &tree;

while (p || !IsStackEmpty(s))
{
  while (p)
  {
   printf("%c", p->data); // 訪問根結點
   Push(&s, *p);           // 根結點指針入棧
   p = p->lchild;          // 一直向左走到底
  }

Pop(&s, q);
p = q->rchild; // 向右走一步
}

free(q);
}

//
// 非遞歸後序遍歷
void NoneRecursionPostOrder(BTree tree)
{
StackElemType *stack[STACK_INIT_SIZE], *p;
int tag[STACK_INIT_SIZE], // 值只有0和1，其中0表示該結點的左子樹已經訪問
// 值為1表示該結點的右子樹已經訪問
top = 0; // 棧頂指示器

p = &tree;

while (p || top != 0)// 樹未遍歷完畢或者棧不空
{
  while (p)
  {
   top++;
   stack[top] = p;
   tag[top] = 0;
   p = p->lchild; // 從根開始向左走到底
  }

  if (top > 0) // 棧不空
  {
   if (tag[top] == 1)// 表示已經訪問該結點的右子樹，並返回
   {
    p = stack[top--]; // 退棧
    printf("%c", p->data);

    p = NULL; // 下次進入循環時，就不會再遍歷左子樹
   }
   else // 表示剛從該結點的左子樹返回，現在開始遍歷右子樹
   {
    p = stack[top]; // 取棧頂元素
    if (top > 0) // 棧不空
    {
     p = p->rchild;
     tag[top] = 1; // 標識該結點的右子樹已經訪問
    }
   }
  }
}
}

int main()
{
BTree *tree = NULL;

printf("按先序輸入二叉樹結點元素的值，輸入#表示空樹：\n");

freopen("test.txt", "r", stdin);

if (CreateBinaryTree(&tree) == OK) // 創建二叉樹
{
printf("二叉樹創建成功！\n");
}

printf("先序遍歷(#表示空子樹)：\n");
PreOrderTraverse(tree);

printf("\n中序遍歷(#表示空子樹)：\n");
InOrderTraverse(tree);

printf("\n後序遍歷(#表示空子樹)：\n");
PostOrderTraverse(tree);

printf("\n樹的深度為：%d\n", GetDepth(tree));

printf("\n層序遍歷：\n");
LevelOrderTraverse(tree);

printf("\n遍歷葉子結點:\n");
TraverseLeafNodes(tree);

printf("\n葉子結點的個數：%d\n", GetLeafCount(tree));
printf("度為1的結點的個數：%d\n", GetCountOfOneDegree(tree));
printf("度為2的結點的個數：%d\n", GetCountOfTwoDegree(tree));
printf("\n二叉樹的結點總數為：%d\n", GetNodesCount(tree));

printf("\n該二叉樹是否為平衡二叉樹？\n");
if (IsBalanceBinaryTree(tree))
{
printf("Yes!\n");
}
else
{
printf("No!\n");
}

printf("\n結點值為A的結點在第%d層\n", GetLevelByValue(tree, 'A'));
printf("\n結點值為B的結點在第%d層\n", GetLevelByValue(tree, 'B'));
printf("\n結點值為C的結點在第%d層\n", GetLevelByValue(tree, 'C'));
printf("\n結點值為D的結點在第%d層\n", GetLevelByValue(tree, 'D'));
printf("\n結點值為E的結點在第%d層\n", GetLevelByValue(tree, 'E'));
printf("\n結點值為F的結點在第%d層\n", GetLevelByValue(tree, 'F'));
printf("\n結點值為G的結點在第%d層\n", GetLevelByValue(tree, 'G'));
printf("\n結點值為M的結點在第%d層\n", GetLevelByValue(tree, 'M'));

printf("\n非遞歸中序遍歷：\n");
NoneRecursionInOrder(*tree);

printf("\n非遞歸前序遍歷：\n");
NoneRecursionPreOrder(*tree);

printf("\n非遞歸後序遍歷：\n");
NoneRecursionPostOrder(*tree);

printf("\n=======================================================\n");

printf("下面執行交換左右子樹操作：\n");
SwapLeftRightSubtree(&tree);

printf("先序遍歷(#表示空子樹)：\n");
PreOrderTraverse(tree);

printf("\n中序遍歷(#表示空子樹)：\n");
InOrderTraverse(tree);

printf("\n後序遍歷(#表示空子樹)：\n");
PostOrderTraverse(tree);

printf("\n樹的深度為：%d\n", GetDepth(tree));

printf("\n層序遍歷：\n");
LevelOrderTraverse(tree);

printf("\n遍歷葉子結點:\n");
TraverseLeafNodes(tree);

fclose(stdin);