1.链式二叉树
⽤链表来表⽰⼀棵⼆叉树,即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组 成,数据域和左右指针域,左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址, 其结构如下:
typedef int BTDataType;// ⼆叉链
typedef struct BinaryTreeNode{struct BinTreeNode* left; // 指向当前结点左孩⼦struct BinTreeNode* right; // 指向当前结点右孩⼦BTDataType val; // 当前结点值域}BTNode;
⼆叉树的创建⽅式⽐较复杂,为了讲述⼆叉树内容中,我们先⼿动创建⼀棵链式⼆叉树
BTNode* buynode(BTDataType x)
{BTNode*node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->left = node->right = NULL;return node;
}
BTNode* CreatBinaryTree()
{BTNode* NodeA = buynode('A');BTNode* NodeB = buynode('B');BTNode* NodeC = buynode('C');BTNode* NodeD = buynode('D');BTNode* NodeE = buynode('E');BTNode* NodeF = buynode('F');NodeA->left = NodeB;NodeA->right = NodeC;NodeB->left = NodeD;NodeC->left = NodeE;NodeC->right = NodeF;return NodeA;
}
⼆叉树分为空树和⾮空⼆叉树,⾮空⼆叉树由根结点、根结点的左⼦树、根结点 的右⼦树组成的,根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的,因此⼆叉树定义是递归式的,后序链式⼆叉树的操作中基本都是按照该概念实现的。
2.各种函数的实现
这里还是一样,先建立三个文件,Tree.h,Tree.c,tect.c,分别为头文件,函数实现文件,和测试文件,注意这里后面树的层序遍历,和判断是否为完全二叉树,这两个函数会用到队列的数据结构,所以还要用到之前写的Queue.c,Queue.h。
Tree.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;void PrevOrder(BTNode*root);
void InOrder(BTNode*root);
void PostOrder(BTNode*root);int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLevelKSize(BTNode* root, int k);
int BinaryTreeDepth(BTNode* root);BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
void BinaryTreeLevelOrder(BTNode* root);
bool BinaryTreeComplete(BTNode* root);
2.1 前中后序遍历
2.1.1前序遍历void PrevOrder(BTNode*root)
void PrevOrder(BTNode*root)
{if (root == NULL){printf("NULL ");return ;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
这里利用递归,直到到空结点,就回退,首先打印根节点,然后找left结点,left节点再去找接下来的left结点直到left的空节点,每向下一次就打印一次,到空节点回退到上一层,再看right结点,到空节点回退到上一层,左右都回退后再返回上一层,重复到根节点为止。
结果:
2.1.2中序遍历void InOrder(BTNode* root)
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
这里和前序遍历逻辑一样,只是printf打印的时候,在left结点回退回来后,再打印。
结果:
2.1.3后序遍历void PostOrder(BTNode* root)
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}
这里和前序遍历逻辑一样,只是printf打印的时候,在left结点和right结点都回退回来后,再打印。
结果:
2.2树节点的个数int BinaryTreeSize(BTNode* root)
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
这里计算结点个数,也是利用递归,return中的1是表示每次递归根节点,然后去寻找左右节点,直到空节点返回0,当左右结点的都为NULL,return返回1+0+0,也就是表示一个结点,再向上递归,直到回退到根节点那个函数里。
2.3叶子结点个数int BinaryTreeLeafSize(BTNode* root)
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
这里统计叶子结点的个数,(度为0的结点是叶子结点),根据这个性质,去寻找左右结点为空节点的结点,就是叶子结点,从根节点开始递归直到到空节点。
2.4第K层结点个数int BinaryTreeLevelKSize(BTNode* root, int k)
int BinaryTreeLevelKSize(BTNode* root, int k)
{if(root==NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k - 1) + BinaryTreeLevelKSize(root->right,k - 1);
}
找第K层,每向下一层就K-1,直到找到K==1,也就是找到了第K层,然后找到任意一个左右节点且K==1就返回1直到回退到根节点。
2.5寻找结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftleaf=BinaryTreeFind(root->left, x);if (leftleaf){return leftleaf;}BTNode*rightleaf=BinaryTreeFind(root->right, x);if (rightleaf){return rightleaf;}return NULL;
}
这里寻找,数据为x的节点,找到直接返回root,为空就返回NULL,注意这里返回的要用一个BTNode*leftleaf保存是否在根节点左边是否找到,BTNode*rightleaf保存是否在根节点右边是否找到,然后递归回退到根节点的那个函数,判断保存的是否为空,有一个就说明找到了,直接返回,反之,返回空。
2.6树的深度int BinaryTreeDepth(BTNode* root)
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int maxleft =BinaryTreeDepth(root->left);int maxright =BinaryTreeDepth(root->right);return 1 +( maxleft > maxright ? maxleft : maxright);
}
这里也要记录左右结点的个数,返回更大的为深度,这里return中的1为是根节点的那一层,向下直到空结点,然后回退到根节点,比较左右深度大小,找到更大的为深度。
2.6层序遍历void BinaryTreeLevelOrder(BTNode* root)
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);if (top->left){QueuePush(&q, top->left);}if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);
}
这里要使用到队列这个数据结构,首先建一个队列,先将根节点放进队列中,然后判断队列是否为空,不为空,就出队,如果入队结点的左右结点,不为空就入队,直到队列为空,就完成了层序遍历。
结果:A B C D E F
2.7判断是否为完全二叉树bool BinaryTreeComplete(BTNode* root)
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}QueuePush(&q, top->left);QueuePush(&q, top->right);}while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
(完全二叉树:最后一个节点的上面所有层的结点的度都为2)这里和层序遍历相同,要用到队列,先建一个队,将根节点入队,以队列为空作为停止循环的条件,出队,如果判断该节点为空,直接跳出循环,不为空,将左右节点入队,这里不需要判断是否为空,空也直接入队,因为这里出队到空会直接跳出循环,跳出循环后,继续出队,如果找到为不为空,说明在空节点,后面还有数据结点,就不是完全二叉树,如果直到出队完,未找到数据结点,说明wield完全二叉树。
3.整体代码
注意:这里之前队列实现,用的数据类型为int,这里要改成BTNode类型,还要注意前置声明因为队列中要使用到定义的树的结构体,所以要用到前置声明。
Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//typedef int DataType;
typedef struct BinaryTreeNode* DataType;typedef struct QueueNode
{DataType data;struct QueueNode* next;
}QueueNode;typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;void QueueInit(Queue*pq);
// 销毁队列
void QueueDestroy(Queue * pq);//入队列--队尾
void QueuePush(Queue* pq, DataType x);
//出队列--队头
void QueuePop(Queue* pq);//取队头数据
DataType QueueFront(Queue* pq);
//取队尾数据
DataType QueueBack(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}QueueNode* BuyNode(DataType x)
{QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void QueuePush(Queue* pq, DataType x)
{assert(pq);QueueNode*newnode= BuyNode(x);if (pq->phead ==NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next; }pq->size--;
}DataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}DataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead==NULL;
}int QueueSize(Queue* pq)
{return pq->size;
}void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
Tree.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include"Queue.h"typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;void PrevOrder(BTNode*root);
void InOrder(BTNode*root);
void PostOrder(BTNode*root);int BinaryTreeSize(BTNode* root);
int BinaryTreeLeafSize(BTNode* root);
int BinaryTreeLevelKSize(BTNode* root, int k);
int BinaryTreeDepth(BTNode* root);BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
void BinaryTreeLevelOrder(BTNode* root);
bool BinaryTreeComplete(BTNode* root);
Tree.c
#include"Tree.h"void PrevOrder(BTNode*root)
{if (root == NULL){printf("NULL ");return ;}printf("%c ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}int BinaryTreeLevelKSize(BTNode* root, int k)
{if(root==NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left,k - 1) + BinaryTreeLevelKSize(root->right,k - 1);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode*leftleaf=BinaryTreeFind(root->left, x);if (leftleaf){return leftleaf;}BTNode*rightleaf=BinaryTreeFind(root->right, x);if (rightleaf){return rightleaf;}return NULL;
}int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int maxleft =BinaryTreeDepth(root->left);int maxright =BinaryTreeDepth(root->right);return 1 +( maxleft > maxright ? maxleft : maxright);
}void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);printf("%c ", top->data);if (top->left){QueuePush(&q, top->left);}if (top->right){QueuePush(&q, top->right);}}QueueDestroy(&q);
}bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}QueuePush(&q, top->left);QueuePush(&q, top->right);}while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
tect.c
#include"Tree.h"
BTNode* buynode(BTDataType x)
{BTNode*node= (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->left = node->right = NULL;return node;
}
BTNode* CreatBinaryTree()
{BTNode* NodeA = buynode('A');BTNode* NodeB = buynode('B');BTNode* NodeC = buynode('C');BTNode* NodeD = buynode('D');BTNode* NodeE = buynode('E');BTNode* NodeF = buynode('F');NodeA->left = NodeB;NodeA->right = NodeC;NodeB->left = NodeD;NodeC->left = NodeE;NodeC->right = NodeF;return NodeA;
}void test()
{BTNode*root=CreatBinaryTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");int size = BinaryTreeSize(root);printf("size=%d\n", size);int leafsize=BinaryTreeLeafSize(root);printf("leafsize=%d\n",leafsize);int lk= BinaryTreeLevelKSize(root, 2);printf("第2层结点为:%d\n", lk);BTNode*ret=BinaryTreeFind(root, 'G');if (ret == NULL){printf("未找到\n");}else{printf("找到了\n");}int depth = BinaryTreeDepth(root);printf("depth=%d\n", depth);BinaryTreeLevelOrder(root);printf("\n");if (!BinaryTreeComplete(root)){printf("非完全二叉树");}else{printf("完全二叉树");}
}int main()
{test();return 0;
}