程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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);

 printf("\n");
 return 0;
}
[cpp] 
text.txt的內容: 
ABC##DE#G##F### 

text.txt的內容:
ABC##DE#G##F###

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved