951
C語言實現二叉樹的常用的算法(遞歸與非遞歸實現遍曆)
隊列頭文件：
#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 <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;
}
}
棧頭文件：
#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
棧實現文件：
//
// 順序棧的實現文件：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;
}
}
二叉樹頭文件：
#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>
#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;
}
text.txt的內容： ABC##DE#G##F###
最後更新：2017-04-03 18:51:55