上海商城网站建设,南京本地网站建站,哔哩哔哩网站,快速网站推广工具前言 二叉树是一种特殊的树#xff0c;它最大的度为2#xff0c;每个节点至多只有两个子树。它是一种基础的数据结构#xff0c;后面很多重要的数据结构都是依靠它来进行实现的。了解并且掌握它是很重要的。
目录
1.二叉树的介绍 1.1概念 1.2现实中的二叉树 1.3特殊的二叉…前言 二叉树是一种特殊的树它最大的度为2每个节点至多只有两个子树。它是一种基础的数据结构后面很多重要的数据结构都是依靠它来进行实现的。了解并且掌握它是很重要的。
目录
1.二叉树的介绍 1.1概念 1.2现实中的二叉树 1.3特殊的二叉树 1.4二叉树的性 1.5二叉树的存储结构
2.二叉树链式结构的实现 2.1创建一颗伪二叉树 2.2二叉树的遍历 2.2.1前序中序和后序遍历 2.2.2层序遍历 2.3二叉树的节点个数及高度等 2.4二叉树的创建及销毁 2.5全部代码 1.二叉树的介绍 1.1概念 一颗二叉树是节点的一个有限集合该集合 1.或者为空 2.由根节点外加两颗别称为左子树和右子树的二叉树组成 1.2现实中的二叉树 1.3特殊的二叉树 满二叉树一个二叉树如果每一层的节点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且节点的总数是二的K次方-1则它就是满二叉树。 完全二叉树 完全二叉树是一种效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有N个节点的二叉树当且仅当每个节点都与深度为K的满二叉树中编号从1到N的节点一一对应时称为完全二叉树。 1.4二叉树的性 1.若规定根节点的层数为1则一颗非空二叉树的第i层最多有2的i-1次方个节点。 2.若规定根节点的层数为1则深度为h的二叉树最大的节点数为2的h次方减1。 3.对于任意一颗二叉树如果度为零其叶子结点的个数为n0度为2的分支节点个数为n2则有n0 n2 1 4.若规定根节点的层数为1其n个节点的满二叉树的深度h log2n1.(log2(n 1)是以2为底n1为对数) 5.对于具有n个节点的完全二叉树如果按照从上至下从左至右的数组顺序对所有的节点从0开始编号则对于序号为i的节点有 1.若i大于0i位置双亲节点的序号i - 1/2; i 0,i为根节点编号无双亲节点 2.若2i1n,左孩子的序号2i12i1n则无左孩子。 3.若2i2n,右孩子序号2i2,2i2n,则无右孩子。 1.5二叉树的存储结构 二叉树一般有两种结构的存储方式一种是顺序结构一种是链式结构。 1.顺序存储 顺序存储使用的数组一般数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费而现实中只有堆 才使用数组来存储。二叉树的顺序存储在物理上是数组在逻辑上是一颗二叉树。 2.链式存储 二叉树的链式存储结构是指用链表来表示一颗二叉树即用链表来指示元素之间的逻辑关系。通常的方法是每个节点由左右指针域和数据域组成。左右指针分别用来给出该节点左孩子和右孩子所在节点的地址。链式存储结构又分为二叉链和三叉链。现在我们使用的是二叉链。 2.二叉树链式结构的实现 2.1创建一颗伪二叉树 这里需要快速创建一颗二叉树为了降低理解的难度先创建一颗伪二叉树来进行学习便于理解。 //BTree.h
#includestdio.h
#includestdlib.h
#includestring.h
typedef char BTDataType;
typedef struct BTreeNode
{BTDataType _data;struct BTreeNode* _left;struct BTreeNode* _right;
}BTreeNode;
BTreeNode* BuyBTreeNode(BTreeNode* node, BTDataType c);//申请一棵树的节点BTreeNode* CreatBinaryTree(BTreeNode* root);//创建一棵树 //BTree.c
BTreeNode* BuyBTreeNode(BTreeNode* node,BTDataType c)
{BTreeNode*cur (BTreeNode*)malloc(sizeof(BTreeNode));cur-_data c;cur-_left cur-_right NULL;
}
BTreeNode* CreatBinaryTree(BTreeNode* root)//创建一棵树
{root BuyBTreeNode(root, A);BTreeNode* B BuyBTreeNode(root, B);BTreeNode* C BuyBTreeNode(root, C);BTreeNode* D BuyBTreeNode(root, D);BTreeNode* E BuyBTreeNode(root, E);BTreeNode* F BuyBTreeNode(root, F);root-_left B;root-_right C;B-_left D;C-_left E;C-_right F;return root;
} 2.2二叉树的遍历 2.2.1前序中序和后序遍历 学习二叉树结构最简单的方式就是遍历。所谓二叉树的遍历就是按照某种特定的规则依次对二叉树的节点进行相应的操作并且每个节点只操作一次。访问节点的操作依赖于具体的问题遍历是二叉树上最重要的运算之一也是二叉树进行其他运算的基础。 按照规则二叉树的遍历有前序中序和后序的递归结构遍历 1.前序遍历(Preorder Traversal 亦称为先序遍历访问根节点的操作发生在访问左右子树之前。 2.中序遍历Inorder Traversal)--访问根节点的操作发生在访问左右子树之间。 3.后序遍历Post Traversal--访问根节点的操作发生在左右子树之后。 由于被访问的节点必是某树的根所以NNode LLeft subtree和RRight subtree又可以解释为根节点根的左子树和根的右子树。NLR,LNR,LRN分别称为先根遍历中根遍历和后根遍历。 前序遍历的代码
// 二叉树前序遍历
void PreOrder(BTreeNode* root)
{if (root NULL){printf(NULL );return;}printf(%c ,root-_data);PreOrder(root-_left);//左子树PreOrder(root-_right);//右子树
} 前序遍历的递归图解 中序遍历和后序遍历的代码 // 二叉树中序遍历
void InOrder(BTreeNode* root)
{if (root NULL){printf(NULL );return;}PreOrder(root-_left);//左子树printf(%c , root-_data);//根PreOrder(root-_right);//右子树
}
// 二叉树后序遍历
void PostOrder(BTreeNode* root)
{if (root NULL){printf(NULL );return;}PreOrder(root-_left);//左子树PreOrder(root-_right);//右子树printf(%c , root-_data);//根} 中序和后序遍历的展开图解和前序遍历的类似有兴趣的友友可以自己画画看。 2.2.2层序遍历 二叉树的层序遍历是通过借助队列来实现的将一颗树的根入队出队时如果根的左右节点不为空就将根的左右节点依次入队当队列为空时结束循环这样就完成了二叉树的层序遍历。
void LevelOrder(BTreeNode* root)//层序遍历
{//创建队列Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q))//队列不为空出队头的元素同时取节点判断左右子树是否为空{BTreeNode* cur QueueFront(q);QueuePop(q);printf(%c , cur-_data);if (cur-_left)//左子树存在{QueuePush(q, cur-_left);//将当前节点的左子树入队}if (cur-_right)//右子树存在{QueuePush(q, cur-_right);//将当前节点的右子树入队}}
} 2.3二叉树的节点个数及高度等 递归求二叉树的高度是在当前节点求出左右子树的高度再将左右子树中高度大的那个加一就是当前树的高度。
int BinarTreelen(BTreeNode* root)//求树的高度
{if (root NULL)return 0;int leftsize BinarTreelen(root-_left);int rightsize BinarTreelen(root-_right);return leftsize rightsize ? leftsize 1 : rightsize 1;//高度等于下一层左右节点高的那个加1
} 二叉树叶子结点的个数通过递归求解首先叶子节点肯定满足左右子树都为空所以如果左右子树都为空的话就直接返回1说明当前节点就是叶子节点否则继续递归去找叶子节点。
int BinaryTreeLeafSize(BTreeNode* root)
{if (root NULL)//节点为空直接返回return 0;if (root-_left NULL root-_right NULL)//左右节点都为空return 1;//说明当前节点为叶子节点return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);//递归去求左右子树
} 求二叉树的节点个数如果当前节点不为空就1然后递归求左右子树中的节点数。如果当前节点为NULL则返回0.
// 二叉树节点个数
int BinaryTreeSize(BTreeNode* root)
{if (root NULL)//当前节点为NULLreturn 0;return 1 BinaryTreeSize(root-_left) BinaryTreeSize(root-_right);//前序遍历的方式求树的节点个数
} 二叉树查找值为x的节点通过前序遍历二叉树如果二叉树当前节点的值等于x就返回当前节点。
BTreeNode* BinaryTreeFind(BTreeNode* root, BTDataType x)
{if (root NULL)//如果节点为NULLreturn NULL;//返回NULLif (root-_data x)return root;//找到值为x的节点返回BTreeNode*cur BinaryTreeFind(root-_left, x);if (cur)//找到了就返回节点的地址return cur;cur BinaryTreeFind(root-_right, x);if (cur)//找到了就返回节点的地址return cur;return NULL;//如果这棵树没有找到就返回NULL
} 求二叉树的第K层的节点个数采用分治的思想一颗树第K层的节点等于左子树K-1层的节点右子树K-1层的节点。 结束条件是如果当K等于1时返回1当当前节点为NULL时返回0。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTreeNode* root, int _k)
{if (root NULL)return 0;if (_k 1 root)//如果K等于1直接返回return 1;return BinaryTreeLevelKSize(root-_left, _k - 1) BinaryTreeLevelKSize(root-_right, _k - 1);//递归到左右子树K-1层中去找节点数
} 判断一颗二叉树是不是完全二叉树借助 队列采用层序遍历的方式但是这里不判断当前树的左右子树是否为空取队头的数据时直接将该节点的左右子树入队。当取到的队头的数据为空时结束循环。如果是完全二叉树那么剩余在队列中的所有的NULL应该是连续的。再将队列中所有的元素都出队如果全部为空就满足完全二叉树如果不是就不满足完全二叉树。 bool BinaryTreeComplete(BTreeNode* root)//判断一棵树是不是完全二叉树
{if (root NULL)return true;//创建队列Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q))//队列不为空出队头的元素同时判断取出来的节点是否为空{BTreeNode* cur QueueFront(q);QueuePop(q);if (cur NULL)break;//当前节点为空直接结束循环QueuePush(q, cur-_left);QueuePush(q, cur-_right);}while (!QueueEmpty(q)){//判断队列中剩下的元素是否有不为空的BTreeNode* cur QueueFront(q);QueuePop(q);if (cur)return false;}//如果走到这里还没有返回说明是完全二叉树return true;
} 2.4二叉树的创建及销毁 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树。 思路通过递归去构建二叉树因为给出的是前序遍历的数组而数组中的#表示NULL因此需要参数来记录数组的位置也需要将字符数组传递给构建函数如果遇到#就返回NULL如果不是就申请空间初始化data域并且将申请的空间进行返回然后去递归构建左右子树。
#include stdio.h
#includestdlib.htypedef struct BTreeNode
{char _data;struct BTNode* _left;struct BTNode* _right;}BTreeNode;void InOrder(BTreeNode* root){if (root NULL)return;//左子树InOrder(root-_left);//根printf(%c , root-_data);//右子树InOrder(root-_right);
}BTreeNode* BinaryTreeCreate(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTreeNode* node (BTreeNode*)malloc(sizeof(BTreeNode));//申请节点node-_data a[*pi];(*pi);//递归构建左右子树node-_left BinaryTreeCreate(a, pi);node-_right BinaryTreeCreate(a, pi);return node;
}
int main()
{char s[50] { 0 };scanf(%s, s);int i 0;//使用前序遍历构建树BTreeNode* root BinaryTreeCreate(s, i);//使用中序遍历打印树的节点的值InOrder(root);return 0;
} 二叉树的销毁如果采用前序遍历的方式进行销毁就需要保存当前节点所以建议采用后序遍历的方式进行销毁。
// 二叉树销毁
void BinaryTreeDestory(BTreeNode* root)//这里为了保持接口的一致性采用一级指针
{if (root NULL)return;BinaryTreeDestory(root-_left);BinaryTreeDestory(root-_right);free(root);
}2.5全部代码 //BTree.h
#pragma once
#includestdio.h
#includestdlib.h
#includestring.h
#includestdbool.h
typedef char BTDataType;
typedef struct BTreeNode
{BTDataType _data;struct BTreeNode* _left;struct BTreeNode* _right;
}BTreeNode;
BTreeNode* BuyBTreeNode(BTreeNode* node, BTDataType c);//申请一棵树的节点BTreeNode* CreatBinaryTree(BTreeNode* root);//创建一棵树// 二叉树前序遍历
void PreOrder(BTreeNode* root);
// 二叉树中序遍历
void InOrder(BTreeNode* root);
// 二叉树后序遍历
void PostOrder(BTreeNode* root);// 二叉树节点个数
int BinaryTreeSize(BTreeNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTreeNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTreeNode* root, int _k);int BinarTreelen(BTreeNode* root);//求树的高度
// 二叉树查找值为x的节点
BTreeNode* BinaryTreeFind(BTreeNode* root, BTDataType x);void LevelOrder(BTreeNode* root);//层序遍历// 二叉树销毁
void BinaryTreeDestory(BTreeNode* root);
bool BinaryTreeComplete(BTreeNode* root);//判断一棵树是不是完全二叉树//BTree.c
#includeBTree.h
#includeQueue.h
BTreeNode* BuyBTreeNode(BTreeNode* node,BTDataType c)
{BTreeNode*cur (BTreeNode*)malloc(sizeof(BTreeNode));cur-_data c;cur-_left cur-_right NULL;return cur;
}
BTreeNode* CreatBinaryTree(BTreeNode* root)//创建一棵树
{root BuyBTreeNode(root, A);BTreeNode* B BuyBTreeNode(root, B);BTreeNode* C BuyBTreeNode(root, C);BTreeNode* D BuyBTreeNode(root, D);BTreeNode* E BuyBTreeNode(root, E);BTreeNode* F BuyBTreeNode(root, F);root-_left B;root-_right C;B-_left D;C-_left E;C-_right F;return root;
}
// 二叉树前序遍历
void PreOrder(BTreeNode* root){if (root NULL){ return;}printf(%c ,root-_data);PreOrder(root-_left);//左子树PreOrder(root-_right);//右子树
}
// 二叉树中序遍历
void InOrder(BTreeNode* root)
{if (root NULL){printf(NULL );return;}PreOrder(root-_left);//左子树printf(%c , root-_data);//根PreOrder(root-_right);//右子树
}
// 二叉树后序遍历
void PostOrder(BTreeNode* root)
{if (root NULL){printf(NULL );return;}PreOrder(root-_left);//左子树PreOrder(root-_right);//右子树printf(%c , root-_data);//根}// 二叉树节点个数
int BinaryTreeSize(BTreeNode* root)
{if (root NULL)//当前节点为NULLreturn 0;return 1 BinaryTreeSize(root-_left) BinaryTreeSize(root-_right);//前序遍历的方式求树的节点个数
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTreeNode* 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(BTreeNode* root, int _k)
{if (root NULL)return 0;if (_k 1 root)//如果K等于1直接返回return 1;return BinaryTreeLevelKSize(root-_left, _k - 1) BinaryTreeLevelKSize(root-_right, _k - 1);//递归到左右子树K-1层中去找节点数
}
int BinarTreelen(BTreeNode* root)//求树的高度
{if (root NULL)return 0;int leftsize BinarTreelen(root-_left);int rightsize BinarTreelen(root-_right);return leftsize rightsize ? leftsize 1 : rightsize 1;//高度等于下一层左右节点高的那个加1
}
// 二叉树查找值为x的节点BTreeNode* BinaryTreeFind(BTreeNode* root, BTDataType x)
{if (root NULL)//如果节点为NULLreturn NULL;//返回NULLif (root-_data x)return root;//找到值为x的节点返回BTreeNode*cur BinaryTreeFind(root-_left, x);if (cur)//找到了就返回节点的地址return cur;cur BinaryTreeFind(root-_right, x);if (cur)//找到了就返回节点的地址return cur;return NULL;//如果这棵树没有找到就返回NULL
}void LevelOrder(BTreeNode* root)//层序遍历
{//创建队列Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q))//队列不为空出队头的元素同时取节点判断左右子树是否为空{BTreeNode* cur QueueFront(q);QueuePop(q);printf(%c , cur-_data);if (cur-_left)//左子树存在{QueuePush(q, cur-_left);}if (cur-_right)//右子树存在{QueuePush(q, cur-_right);}}
}// 二叉树销毁
void BinaryTreeDestory(BTreeNode* root)//这里为了保持接口的一致性采用一级指针
{if (root NULL)return;BinaryTreeDestory(root-_left);BinaryTreeDestory(root-_right);free(root);
}
bool BinaryTreeComplete(BTreeNode* root)//判断一棵树是不是完全二叉树
{if (root NULL)return true;//创建队列Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q))//队列不为空出队头的元素同时判断取出来的节点是否为空{BTreeNode* cur QueueFront(q);QueuePop(q);if (cur NULL)break;//当前节点为空直接结束循环QueuePush(q, cur-_left);QueuePush(q, cur-_right);}while (!QueueEmpty(q)){//判断队列中剩下的元素是否有不为空的BTreeNode* cur QueueFront(q);QueuePop(q);if (cur)return false;}//如果走到这里还没有返回说明是完全二叉树return true;
}#include stdio.h
#includestdlib.htypedef struct BTreeNode
{char _data;struct BTNode* _left;struct BTNode* _right;}BTreeNode;void InOrder(BTreeNode* root){if (root NULL)return;//左子树InOrder(root-_left);//根printf(%c , root-_data);//右子树InOrder(root-_right);
}BTreeNode* BinaryTreeCreate(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTreeNode* node (BTreeNode*)malloc(sizeof(BTreeNode));//申请节点node-_data a[*pi];(*pi);//递归构建左右子树node-_left BinaryTreeCreate(a, pi);node-_right BinaryTreeCreate(a, pi);return node;
}//Queue.h
#pragma once
#includestdlib.h
#includeassert.h
#includestdio.h
#includestdbool.h
typedef struct BTreeNode BTreeNode;
typedef BTreeNode* QDataType;//树节点的声明typedef struct QueueNode
{struct QueueNode* _next;QDataType _data;
}QueueNode;
typedef struct Queue//队列的结构
{QueueNode* _head;//头指针QueueNode* _tail;//尾指针
}Queue;void QueueInit(Queue* qu);//初始化栈void QueueDestory(Queue* qu);//摧毁栈void QueuePush(Queue* qu,QDataType data);//入队void QueuePop(Queue* qu);//出队QDataType QueueFront(Queue* qu);//返回队头元素
QDataType QueueBack(Queue* qu);//返回队尾元素size_t QueueSize(Queue* qu);//队列长度bool QueueEmpty(Queue* qu);//判断队列是否为空 //Queue.c
#includeQueue.h
void QueueInit(Queue* qu)//初始化栈
{qu-_head qu-_tail NULL;
}
void QueueDestory(Queue* qu)//摧毁栈
{//确保指针有效assert(qu);QueueNode* cur qu-_head;while (cur){QueueNode* next cur-_next;free(cur);}
}
void QueuePush(Queue* qu,QDataType data)//入队
{if (qu-_head NULL){qu-_head (QueueNode*)malloc(sizeof(QueueNode));qu-_tail qu-_head;qu-_head-_next NULL;qu-_head-_data data;}else{//尾部入数据QueueNode* cur qu-_tail;QueueNode* newNode (QueueNode*)malloc(sizeof(QueueNode));cur-_next newNode;newNode-_next NULL;qu-_tail newNode;newNode-_data data;}
}
void QueuePop(Queue* qu)//出队
{//队头出数据QueueNode* head qu-_head;qu-_head head-_next;free(head);
}
QDataType QueueFront(Queue* qu)//返回队头元素
{return qu-_head-_data;
}
QDataType QueueBack(Queue* qu)//返回队尾元素
{return qu-_tail-_data;
}
size_t QueueSize(Queue* qu)//队列长度
{assert(qu);//确保指针存在QueueNode* cur qu-_head;size_t size 0;while (cur){size;cur cur-_next;}return size;
}
bool QueueEmpty(Queue* qu)//判断队列是否为空
{return !qu-_head;
} //Test.c
#includeBTree.h
void TestBTreeNode()
{BTreeNode* root NULL;root CreatBinaryTree(root);/*PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);*///printf(%d\n, BinaryTreeSize(root));printf(%d\n, BinaryTreeLeafSize(root));printf(%d\n, BinarTreelen(root));//LevelOrder(root);printf(%d\n, BinaryTreeComplete(root));printf(%d\n, BinaryTreeLevelKSize(root, 3));BinaryTreeDestory(root);root NULL;//根节点置空防止野指针的问题
}
int main()
{TestBTreeNode();}
