石家庄 做网站,竞价开户推广,绞铜机 东莞网站建设,门户网站代码本篇将较为详细的介绍二叉树的相关知识#xff0c;以及二叉树的实现。对于二叉树的相关知识#xff0c;本篇介绍了其概念、特殊的二叉树、性质还有存储结构。 接着对于实现二叉树的每个函数都有其思路讲解#xff0c;主要的函数分为#xff1a;遍历#xff1a;前中后序遍历… 本篇将较为详细的介绍二叉树的相关知识以及二叉树的实现。对于二叉树的相关知识本篇介绍了其概念、特殊的二叉树、性质还有存储结构。 接着对于实现二叉树的每个函数都有其思路讲解主要的函数分为遍历前中后序遍历结点个数二叉树总结点个数、叶子结点个数、第k层结点个数、二叉树的高度建立销毁二叉树前序遍历建立二叉树与销毁二叉树层序遍历与判断是否为完全二叉树在二叉树中查找值为x的结点。 然后测试了所有的代码其中使用到的队列代码本篇就没有讲解若详细查看队列代码可去主页查找对应的文章。 目录如下 目录 1. 二叉树的概念及结构 1.1 概念 1.2 特殊的二叉树 1.3 二叉树的性质 1.4 二叉树的存储结构 2. 二叉树的实现 2.1 二叉树的遍历 2.2 计算结点个数 2.3 通过前序遍历建立二叉树、销毁二叉树 2.4 层序遍历与判断二叉树是否为完全二叉树 2.5 二叉树查找值为x的结点。 3. 所有代码 3.1 All.h 3.2 Queue.c 3.3 BinaryTree.c 3.4 test.c 3.5 测试结果 1. 二叉树的概念及结构
1.1 概念 一颗二叉树是结点的一个有限集合该集合或者为空空二叉树、或一个根节点加上两颗别称为左子树和右子树的二叉树组成。 从上图中可以看出 1.二叉树中不存在度大于2的结点 2.二叉树的子树存在左右之分次序不能颠倒因此二叉树是有序树。 注意对于任意的二叉树都是由以下几种情况复合而成 1.2 特殊的二叉树 特殊的二叉树包括两种满二叉树、完全二叉树。 满二叉树一个二叉树若每一层的节点数都达到最大值则这个二叉树就为满二叉树。也就是说若一个二叉树的层数为 k 且结点总数为 2^k - 1 则它就是满二叉树。 完全二叉树对于深度为 k 的有 n 个结点的二叉树当且仅当其中每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应时称之为完全二叉树。满二叉树是一种特殊的完全二叉树完全二叉树是一种效率很高的数据结构完全二叉树是由满二叉树引出来的。 1.3 二叉树的性质 1.若规定根节点的层数为1则一颗非空二叉树的第 i 层上最多有2^( i - 1 )个结点。 2.若规定根节点的层数为1则深度为 h 的二叉树的最大节点数为 2^h - 1。 3.对任意一棵二叉树若度为0的叶子节点个数为n0度为2的分支结点个数为n2则有n0 n2 1。 4.若规定根节点的层数为1若具有n个结点的满二叉树的深度。 5.对于具有n个结点的完全二叉树若按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点 a.若 i 0, i 位置结点的双亲结点序号( i - 1 ) / 2i 0时表示为根节点编号无双亲结点。 b.若 2 * i 1 n, 左孩子序号2 * i 1若2 * i 1 n 表示无左孩子。 c.若 2 * i 2 n, 右孩子序号2 * i 2若2 * i 2 n 表示无右孩子。 1.4 二叉树的存储结构 二叉树一般可以使用两种结构存储一种顺序存储一种链式存储。本篇主讲链式存储。 1.顺序存储顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2.链式存储二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们所介绍的主要为二叉链。 2. 二叉树的实现 接下来将实现二叉树其中主要实现的为链式二叉树其中包括几个部分 1.二叉树的遍历二叉树的前序、中序、后序遍历 2.计算结点个数计算二叉树结点个数、叶子结点个数、第k层结点的个数和二叉树的高度 3.通过前序遍历构建二叉树、二叉树的销毁 4.层序遍历二叉树、判断二叉树是否为完全二叉树 5.二叉树查找值为x的结点。 主要就为以上几个部分其中需要使用到的其他数据结构为队列。 2.1 二叉树的遍历 对于二叉树的前序、中序和后序遍历本文使用递归遍历对于层序遍历就使用非递归遍历首先介绍的为前序、中序和后序遍历 对于递归遍历主要思路为递归分治将问题分为当前问题和子问题以及递归结束的调节。 以前序遍历为主前序遍历的主要关键为若当前结点不为NULL我们就将其遍历然后接着遍历左子树、右子树。若当前结点为NULL我们就返回当前函数此次递归结束。中序就为先遍历左子树然后遍历根节点、最后遍历右子树后序为先遍历左子树然后遍历右子树最后遍历根节点。代码如下 // 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root) {if (root) {printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);}
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {if (root) {BinaryTreeInOrder(root-left);printf(%c , root-data);BinaryTreeInOrder(root-right);}
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {if (root) {BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%c , root-data);}
} 2.2 计算结点个数 接下来将用递归分别计算二叉树的结点个数、叶子结点个数、第k层结点的个数以及计算二叉树的高度先以计算二叉树的个数为例我们要计算二叉树的结点个数可以将其分为左子树结点个数右子树结点个数1根节点个数其中的核心思想就为此若遇到空结点则返回0代码具体实现如下 // 二叉树节点个数
int BinaryTreeSize(BTNode* root) {return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
} 计算叶子结点个数我们首先需要找到叶子结点的特点左右子树为NULL所以我们可以将此递归分为遇到叶子结点返回1、左子树叶子结点右子树叶子结点当访问到空结点时即返回0具体代码实现如下 // 二叉树叶子节点个数
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);
} 计算第k层的结点个数既然需要计算第k层的结点个数那么我们肯定需要锁定到第k层所以我们需要在每一次递归时都将k减一然后在k1时返回1。所以我们可以将这个递归分为当k1时返回1递归返回左子树第k个结点右子树第k个结点。具体实现代码如下 // 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 0);if (k 1)return 1;if (root NULL)return 0;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
} 计算二叉树的高度对于计算二叉树的高度我们首先需要知道的是左子树更高还是右子树更高计算出子树的最高高度然后加上根节点所以可以将其递归分为比较左右子树的高度然后返回最高的高度1加根节点若递归到空节点返回0具体实现如下 // 二叉树的高度
int BinaryTreeHeight(BTNode* root) {if (root NULL)return 0;int leftHeight BinaryTreeHeight(root-left);int rightHeight BinaryTreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
} 2.3 通过前序遍历建立二叉树、销毁二叉树 对于用此方法构建二叉树我们只需要输入二叉树的前序序列然后根据此建立出对应的二叉树。其中输入的前序序列需要包含空结点空结点用”#“表示。 此函数传入的参数为字符串前序序列、记录当前递归处理到了前序序列字符串的哪一个位置的整数的地址。函数返回根节点。 对于此函数的实现主要还是依靠递归将这个递归分为若当前字符为#返回NULL若不为#malloc一个新节点新节点的数据为当前字符然后将整数1然后递归新节点的左右孩子结点最后返回新节点具体代码实现如下 BTNode* CreatBTNode(BTDataType x) {BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL) {perror(newnode malloc:\n);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {if (a[*pi] #) {(*pi);return NULL;}BTNode* newNode CreatBTNode(a[*pi]);(*pi);newNode-left BinaryTreeCreate(a, pi);newNode-right BinaryTreeCreate(a, pi);return newNode;
} 二叉树的销毁二叉树的销毁仍然使用递归进行销毁处理其主要思想和后序遍历基本一致主要为递归删除左子树递归删除右子树删除根节点主要实现代码如下 // 二叉树销毁
void BinaryTreeDestory(BTNode** root) {// 递归销毁先销毁左子树后销毁右子树if (*root NULL)return;BTNode* tmp *root;BinaryTreeDestory(tmp-left);BinaryTreeDestory(tmp-right);free(tmp);tmp NULL;
}2.4 层序遍历与判断二叉树是否为完全二叉树 层序遍历对于层序遍历的主要思想就是将二叉树按层次遍历先遍历第一层根节点然后遍历下一层从左到右直至遍历结束。对于此方法我们不使用递归我们使用队列来辅助我们遍历。 我们首先将根节点放入队列然后开始进行遍历循环只要队列不为空我们就一直入循环。在循环中我们得到排在队列的第一个元素将其访问然后若第一个元素的左子树不为空则将其入队列右子树不为空将其入队列孩子结点不为空就入队列接着将第一个元素出队列循环往复就可以将二叉树进行层序遍历因为是将结点一层一层的加入队列然后又出队列的。具体实现代码如下 // 层序遍历
void BinaryTreeLevelOrder(BTNode* root) {if (root NULL)return;Queue pQ;QueueInit(pQ);QueuePush(pQ, *root);while (!QueueEmpty(pQ)) {BTNode new QueueFront(pQ);printf(%c , new.data);if(new.left)QueuePush(pQ, *(new.left));if(new.right)QueuePush(pQ, *(new.right));QueuePop(pQ);}QueueDestory(pQ);
} 判断二叉树是否为完全二叉树对于完全二叉树的判断主要就是判断一个结点是否存在不存在左孩子存在右孩子的情况当出现这种情况时就可以判断出该二叉树不为完全二叉树。所以我们只需将所有的结点进行判断若所有结点都判断通过则返回true若发现其中一个结点存在没有左孩子存在右孩子则返回false。 对于每个孩子的判断其实我们就可以使用以上的层序遍历在遍历每个结点时对结点进行判断具体实现代码如下 // 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root) {if (root NULL)return true;Queue pQ;QueueInit(pQ);QueuePush(pQ, *root);while (!QueueEmpty(pQ)) {BTNode new QueueFront(pQ);if (new.left NULL new.right)return false;if (new.left)QueuePush(pQ, *(new.left));if (new.right)QueuePush(pQ, *(new.right));QueuePop(pQ);}QueueDestory(pQ);return true;
} 2.5 二叉树查找值为x的结点。 对于二叉树的查找我们同样使用递归对二叉树进行遍历查找其主要思想为若当前结点为NULL则返回NULL若当前结点的值等于 x 则返回当前结点然后依次遍历查找左子树和右子树但是在左子树和右子树的查找返回中我们一个函数只能返回一次不能同时递归返回左右子树所有需要在对左子树的递归返回时加上一个判断若左子树不为NULL则先查找递归返回左子树当左子树递归结束都还没找到时自然递归返回右子树。具体实现代码如下 // 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL)return NULL;if (root-data x)return root;BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind)return leftFind;return BinaryTreeFind(root-right, x);
}3. 所有代码
3.1 All.h 以下为头文件All.h的代码 #define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
#include math.htypedef char BTDataType;typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;typedef BTNode QDataType;typedef struct Node {QDataType val;struct Node* next;
}QNode;typedef struct Queue {int size;QNode* phead;QNode* ptail;
}Queue;//队列的初始化/销毁
void QueueInit(Queue* pQ);
void QueueDestory(Queue* pQ);//队列的入队/出队
void QueuePush(Queue* pQ, QDataType x);
void QueuePop(Queue* pQ);//返回队首元素/队尾元素
QDataType QueueFront(Queue* pQ);
QDataType QueueBack(Queue* pQ);//判断队列是否为NULL/返回队列的大小
bool QueueEmpty(Queue* pQ);
int QueueSize(Queue* pQ);// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树的高度
int BinaryTreeHeight(BTNode* root); 3.2 Queue.c 以下为队列部分的代码 #define _CRT_SECURE_NO_WARNINGS 1
#include All.hvoid QueueInit(Queue* pQ) {assert(pQ);pQ-phead pQ-ptail NULL;pQ-size 0;
}void QueueDestory(Queue* pQ) {assert(pQ);QNode* cur pQ-phead;while (cur) {QNode* next cur-next;free(cur);cur next;}pQ-phead pQ-ptail NULL;pQ-size 0;
}void QueuePush(Queue* pQ, QDataType x) {assert(pQ);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL) {perror(malloc:);exit(1);}newnode-val x;newnode-next NULL;if (pQ-phead NULL) {pQ-phead pQ-ptail newnode;}else {pQ-ptail-next newnode;pQ-ptail newnode;}pQ-size;
}void QueuePop(Queue* pQ) {assert(pQ);assert(pQ-phead);QNode* cur pQ-phead;pQ-phead pQ-phead-next;free(cur);cur NULL;pQ-size--;
}QDataType QueueFront(Queue* pQ) {assert(pQ);assert(pQ-phead);return pQ-phead-val;
}QDataType QueueBack(Queue* pQ) {assert(pQ);assert(pQ-phead);return pQ-ptail-val;
}bool QueueEmpty(Queue* pQ) {assert(pQ);return pQ-phead NULL;
}int QueueSize(Queue* pQ) {assert(pQ);return pQ-size;
} 3.3 BinaryTree.c 以下为实现二叉树的代码 #define _CRT_SECURE_NO_WARNINGS 1
#include All.h// 二叉树节点个数
int BinaryTreeSize(BTNode* root) {return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}// 二叉树叶子节点个数
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);
}// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 0);if (k 1)return 1;if (root NULL)return 0;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL)return NULL;if (root-data x)return root;BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind)return leftFind;return BinaryTreeFind(root-right, x);
}// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root) {if (root) {printf(%c , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);}
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {if (root) {BinaryTreePrevOrder(root-left);printf(%c , root-data);BinaryTreePrevOrder(root-right);}
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {if (root) {BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);printf(%c , root-data);}
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root) {if (root NULL)return;Queue pQ;QueueInit(pQ);QueuePush(pQ, *root);while (!QueueEmpty(pQ)) {BTNode new QueueFront(pQ);printf(%c , new.data);if(new.left)QueuePush(pQ, *(new.left));if(new.right)QueuePush(pQ, *(new.right));QueuePop(pQ);}QueueDestory(pQ);
}// 二叉树的高度
int BinaryTreeHeight(BTNode* root) {if (root NULL)return 0;int leftHeight BinaryTreeHeight(root-left);int rightHeight BinaryTreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}BTNode* CreatBTNode(BTDataType x) {BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL) {perror(newnode malloc:\n);exit(1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {if (a[*pi] #) {(*pi);return NULL;}BTNode* newNode CreatBTNode(a[*pi]);(*pi);newNode-left BinaryTreeCreate(a, pi);newNode-right BinaryTreeCreate(a, pi);return newNode;
}// 二叉树销毁
void BinaryTreeDestory(BTNode** root) {// 递归销毁先销毁左子树后销毁右子树if (*root NULL)return;BTNode* tmp *root;BinaryTreeDestory(tmp-left);BinaryTreeDestory(tmp-right);free(tmp);tmp NULL;
}// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root) {if (root NULL)return true;Queue pQ;QueueInit(pQ);QueuePush(pQ, *root);while (!QueueEmpty(pQ)) {BTNode new QueueFront(pQ);printf(%c , new.data);if (new.left NULL new.right)return false;if (new.left)QueuePush(pQ, *(new.left));if (new.right)QueuePush(pQ, *(new.right));QueuePop(pQ);}QueueDestory(pQ);return true;
} 3.4 test.c 以下为测试的所有代码 #define _CRT_SECURE_NO_WARNINGS 1
#include All.hint main() {char ch[] ABD##E#H##CF##G##;int i 0;BTNode* root BinaryTreeCreate(ch, i);printf(BinaryTreePrevOrder: );BinaryTreePrevOrder(root);printf(\n);printf(BinaryTreeInOrder: );BinaryTreeInOrder(root);printf(\n);printf(BinaryTreePostOrder: );BinaryTreePostOrder(root);printf(\n);if (BinaryTreeComplete(root))printf(BinaryTree is Complete: true\n);elseprintf(BinaryTree is Complete: false\n);printf(BinaryTreeLevelKSize: %d\n, BinaryTreeLevelKSize(root, 3));printf(BinaryTreeLeafSize: %d\n,BinaryTreeLeafSize(root));printf(BinaryTreeSize: %d\n, BinaryTreeSize(root));printf(BinaryTreeHeight: %d\n, BinaryTreeHeight(root));BTNode* Find BinaryTreeFind(root, A);if (Find)Find-data Y;printf(BinaryTreePrevOrder: );BinaryTreePrevOrder(root);printf(\n);printf(BinaryTreeLevelOrder: );BinaryTreeLevelOrder(root);BinaryTreeDestory(root);return 0;
} 3.5 测试结果 对于字符串ABD##E#H##CF##G##建立的树如下 代码实现如下
