网站结构及内容建设策略,站长 网站对比,开发网站五个阶段,响应式网站企业二叉树 1.树1.1定义1.2基本术语1.3树形结构和线性结构1.4树的存储结构1.4.1双亲表示法1.4.2孩子兄弟表示法 2.二叉树2.1定义2.2特殊二叉树2.3性质2.4存储结构2.4.1顺序存储2.4.2链式存储结构 3.二叉树的基本操作3.1前序遍历#xff08;先序遍历#xff09;3.2中序遍历3.3后序… 二叉树 1.树1.1定义1.2基本术语1.3树形结构和线性结构1.4树的存储结构1.4.1双亲表示法1.4.2孩子兄弟表示法 2.二叉树2.1定义2.2特殊二叉树2.3性质2.4存储结构2.4.1顺序存储2.4.2链式存储结构 3.二叉树的基本操作3.1前序遍历先序遍历3.2中序遍历3.3后序遍历3.4层序遍历 4.二叉树练习5.二叉树的创建和销毁5.1二叉树的创建5.2二叉树的销毁 1.树
学习二叉树首先得了解树从树的基本概念出发。
1.1定义
树是n个节点的的有限集合是一种非线性结构。当n0时称为空树对于非空树T1只有一个根结点root2除根节点外的其余结点可分为m个互不相交的有限集T1T2……Tm其中每个集合本身又是一棵树称为根的子树。
1.2基本术语
结点树的一个独立单元包含一个数据元素或者指向其子树的分支。如图中的ABC等。结点的度结点拥有的子树数称为结点的度也可以理解为这个结点有多少个孩子。如A的度是2B的度是3D的度是0。树的度树的各个结点的度的最大值。如图中的树的度为3。叶子结点或者终端结点度为0的结点。如图中的DEFG。非终端结点度不为0的结点。除根结点外非终端结点也称为内部结点。如图中BC。孩子结点或者子节点一个结点的子树的根结点称为该结点的孩子结点。如图中B和C是A的子结点。双亲结点或者父结点一个结点有一个子结点该结点称为其子结点的父结点。如图中A是B和C的双亲结点。兄弟结点同一双亲的孩子之间互称兄弟。如图中B和C是兄弟结点。祖先从根结点到该结点所经分支上的所有结点。如D的祖先是A和B。子孙以某结点为根的子树的任一结点都称为该结点的子孙。如DEF是B的子孙。层次从根结点开始根结点为第一层根的孩子为第二层以此类推直到最后一层。如A是第一层B是第二层D是第三层。深度树中结点的最大层次。如A这棵树的深度是3。森林由m棵互不相交的树构成的集合。如去掉A结点B和C这两棵子树就是森林。
这么多概念但常用的只有结点的度、双亲结点、叶子结点、树的层次、树的高度、结点的祖先和子孙。 1.3树形结构和线性结构
树形结构线性结构树的根结点没有双亲结点线性表的第一个元素没有前驱树的叶子结点没有子结点线性表的最后一个元素没有后继树的内部结点有一个前驱和多个后继线性表的其余元素只有一个前驱和一个后继
1.4树的存储结构
树有多种存储结构双亲表示法、孩子链表表示法、孩子兄弟表示法等。由于今天的猪脚是二叉树所以在这里简单介绍下双亲表示法和孩子兄弟表示法。
1.4.1双亲表示法
//结点
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{ElemType x;//结点的数据int parent;//结点的双亲结点的下标
}PTNode;
typedef struct
{PTNode a[MAXSIZE];//结点数组int size;//结点个数
}PTree;1.4.2孩子兄弟表示法
//结点
typedef int ElemType;
typedef struct CBTreeNode
{ElemType x;//数据struct CBTreeNode* firstchild;//指向结点的左孩子也就是第一个孩子struct CBTreeNode* Nextbrother;//指向同一父结点的兄弟
}CBTNode;2.二叉树
2.1定义
二叉树是nn0个结点的有限集合。当n0时为空树当n不为0时二叉树有以下特点1.每个结点的度不超过2可以理解为二孩政策下的结点最多只能有两个孩子 2.每个结点的左子树和右子树顺序不能颠倒所以二叉树是有序树。
2.2特殊二叉树
满二叉树每一层结点数都达到最大那么它就是满二叉树。如第1层最多有2 ^0个结点第2层最多有 2 ^1个结点则第k层最多有2 ^(k-1)个结点假设这棵满二叉树有k层那么它总共有2 ^02 ^1……2 ^(k-1) 2 ^k-1个结点。完全二叉树深度为k有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。简介版完全二叉树的前k-1层是满二叉树最后一层从左到右依次连续 2.3性质
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1。对任何一棵二叉树T如果其终端结点数为n0度为2的结点数为n2则n0n21。 证明 若规定根节点的层数为1具有n个结点的满二叉树的深度h log (n1)(ps:log是以2 为底n1为对数)。 证明 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 1. 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点 2. 若2i1n左孩子序号2i12i1n否则无左孩子 3.若2i2n右孩子序号2i22i2n否则无右孩子
2.4存储结构
2.4.1顺序存储
二叉树的顺序存储是用数组存储的其中结点之间的关系用下标来表示。即二叉树的逻辑结构是树但是其物理结构是数组。 但这种存储结构会造成空间浪费适用于完全二叉树和满二叉树。 但这个结构却可以来实现一个很牛逼的排序堆排序。
2.4.2链式存储结构
链式存储结构可以解决顺序存储结构浪费空间的问题二叉树的链式存储表示有二叉链表、三叉链表、双亲链表、线索链表等。这里重点讲二叉链表。
//二叉树的节点
typedef int DataType;
typedef struct BinaryTreeNode
{DataType val;struct BinaryTreeNode* left;//指向左孩子的指针struct BinaryTreeNode* right;//指向右孩子的指针
}BTNode;下面讲二叉树的基本操作。
3.二叉树的基本操作
遍历是指每个结点被访问一次且仅被访问一次。二叉树有一个前驱和两个后继这注定其遍历不同于线性结构的遍历。二叉树的遍历有前序遍历、中序遍历后序遍历层序遍历。
3.1前序遍历先序遍历
概念 前序遍历先访问根节点再访问左子树和右子树。
由图可知树的前序遍历是递归的所以可以用递归来实现。
代码实现
//先手动创建一个二叉树
BTNode* BuyNode(DataType x)//申请一个结点
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc failed);return NULL;}newnode-left newnode-right NULL;newnode-val x;return newnode;
}
BTNode* CreateBT()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;//返回根结点
}
//前序遍历
void PreOrder(BTNode* root)
{//思路先访问根结点再访问左子树和右子树if (rootNULL){printf(NULL );return;}//先访问根结点printf(%d , root-val);//再访问左右子树PreOrder(root-left);PreOrder(root-right);
}
int main()
{BTNode* root CreateBT();PreOrder(root);return 0;
}答案
3.2中序遍历
概念 中序遍历先访问左子树再访问根节点最后访问右子树。 同样可以用递归实现代码实现
// 二叉树中序遍历
void InOrder(BTNode* root)
{//思路先访问左子树再访问根节点最后访问右子树if (root NULL){printf(NULL );return;}//先访问左子树InOrder(root-left);//再访问根节点printf(%d , root-val);//最后访问右子树InOrder(root-right);
}答案
3.3后序遍历
概念 后序遍历先访问左子树再访问右子树最后访问根节点。 代码实现
//后序遍历
void PostOrder(BTNode* root)
{//思路先访问左子树再访问右子树最后访问根结点if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}答案
3.4层序遍历
概念 层序遍历从上到下从左到右依次访问。 代码实现
// 层序遍历
void LevelOrder(BTNode* root)
{//思路用队列实现出队一层入队下一层Queue q;QInit(q);//如果非空就直接入队if (root){QPush(q, root);}//队列中只入队非空元素while (!QEmpty(q)){//先出队BTNode* tmp QPop(q);printf(%d , tmp-val );//再判断左右子树是否为空if (tmp-left){QPush(q, tmp-left);}if (tmp-right){QPush(q, tmp-right);}}QDestroy(q);
}答案
4.二叉树练习
样例
求二叉树的节点个数
// 二叉树节点个数//法一
int size 0;//也可以使用静态变量
void TreeSize(BTNode* root)
{//思路只要节点不为空就记录一次if (root NULL){return 0;}size;TreeSize(root-left);TreeSize(root-right);
}//法二
int BinaryTreeSize(BTNode* root)
{//思路二叉树的节点个数 左子树的节点个数 右子树的节点个数if (root NULL){return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1 ;
}注意 但是法一有个弊端size是全局或静态变量每次调用都得初始化一次。 答案
求二叉树的叶子节点个数
// 二叉树叶子节点个数
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 TreeHeight(BTNode* root)
{// 思路二叉树的高度 左子树的高度和右子树的高度的最大值 1if (root NULL){return 0;}int left TreeHeight(root-left);int right TreeHeight(root-right);return left right ? left 1 : right 1;
}答案
求第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{//思路//对于第一层是求第k层节点个数k//对于第二层是求第k-1层节点个数k-1//……//对于第k层是求这一层节点个数1//第k层节点个数 左子树第k层节点个数 右子树第k层节点个数if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}答案
判断是否是单值二叉树LeetCode965OJ链接 单值二叉树二叉树的每个节点都有相同的值
// 判断是否是单值二叉树
bool isUnivalTree(BTNode* root)
{//思路比较根节点与左右子树是否相等不相等就返回false相等就判断左右子树是否是单值二叉树if (root NULL){return true;}if (root-left root-left-val ! root-val){return false;}if (root-right root-right-val ! root-val){return false;}return isUnivalTree(root-left) isUnivalTree(root-right);
}答案
查找一个值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{//思路先判断根的值是否与x相等相等就返回根//不等就判断是否与左子树相等相等就返回//不等就判断是否与右子树相等相等就返回不等就返回NULLif (root NULL){return NULL;}if (root-val x){return root;}BTNode*tmp BinaryTreeFind(root-left, x);if (tmp ! NULL){return tmp;}tmp BinaryTreeFind(root-right, x);if (tmp ! NULL){return tmp;}return NULL;
}判断两棵二叉树是否相等LeetCode100OJ链接
// 判断两棵二叉树是否相等
bool isSameTree(BTNode* p, BTNode* q)
{//思路先判断根结点是否相等再判断左子树是否相等最后判断右子树是否相等if (p NULL q NULL){return true;}if (p NULL || q NULL){return false;}if (p-val ! q-val){return false;}return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}答案
判断是否是对称二叉树LeetCode101OJ链接
bool isLefRig(BTNode* p1, BTNode* p2)//功能类似于判断两棵二叉树是否相等
{if (p1 NULL p2 NULL){return true;}if (p1 NULL || p2 NULL){return false;}if (p1-val ! p2-val){return false;}return isLefRig(p1-left, p2-right) isLefRig(p1-right, p2-left);
}
bool isSymmetric(BTNode* root)
{
· //思路写一个辅助函数功能与判断二叉树是否相等类似if (root NULL){return true;}return isLefRig(root-left, root-right);
}答案
二叉树的前序遍历LeetCode144OJ链接
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
void PreOrder(struct TreeNode* root, int* a, int* i)
{if (root NULL){return;}//先对根结点进行操作再对左右子树进行操作a[(*i)] root-val;PreOrder(root-left, a, i);PreOrder(root-right, a, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){//我们需要知道这棵树的大小再来动态申请int size TreeSize(root);*returnSize size;int* ret (int*)malloc(sizeof(int) * size);//写一个函数来实现遍历不要在这个函数遍历因为遍历需要递归所以TreeSize会重复调用int i 0;//用来记录数组的下标方便存储数据PreOrder(root, ret, i);//为什么要传下标的地址因为要对下标进行修改return ret;
}答案
二叉树的中序遍历LeetCode94OJ链接
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
void InOrder(struct TreeNode* root, int* a, int* i)
{if (root NULL){return;}InOrder(root-left, a, i);a[(*i)] root-val;InOrder(root-right, a, i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){//我们需要知道这棵树的大小再来动态申请int size TreeSize(root);*returnSize size;int* ret (int*)malloc(sizeof(int) * size);//写一个函数来实现遍历不要在这个函数遍历因为遍历需要递归所以TreeSize会重复调用int i 0;//用来记录数组的下标方便存储数据InOrder(root, ret, i);//为什么要传下标的地址因为要对下标进行修改return ret;
}结果
二叉树的后序遍历LeetCode145OJ链接
int BinaryTreeSize(struct TreeNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}
void PostOrder(struct TreeNode* root, int* ret, int* pi)
{if (root NULL){return 0;}PostOrder(root-left, ret, pi);PostOrder(root-right, ret, pi);ret[(*pi)] root-val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){int size BinaryTreeSize(root);*returnSize size;int* ret (int*)malloc(sizeof(int) * size);//用来存放前序序列int i 0;PostOrder(root, ret, i);return ret;
}结果
判断一棵树是否是另一棵树的子树
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{//思路用当前节点所在树与sub进行比较相等返回真不相等用当前根结点的左子树比较再不相等用右子树比较if (root NULL){return false;}if (isSameTree(root, subRoot)){return true;}return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}结果
判断是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{//思路利用层序遍历将完全二叉树的所有节点全部入队//当出队时节点为NULL如果为完全二叉树则队列中的其余节点都是NULL//所以最后判断队列中的节点是否不为NULL即可判断Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode*tmp QueueFront(q);QueuePop(q);if (tmp NULL){break;//当遇到NULL就跳出循环}else{QueuePush(q, tmp-left);//如果为NULL也入队QueuePush(q, tmp-right);}}while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);if (tmp){QueueDestroy(q);//注意销毁队列防止内存泄漏return false;}}QueueDestroy(q);//等下学习怎么销毁先记住它有销毁的功能return true;
}
int main()
{char arr[100] { 0 };scanf(%s, arr);int i 0;int size strlen(arr);BTNode* root CreateBT(arr, i,size);InOrder(root);
}5.二叉树的创建和销毁
前面的二叉树是我们手动创建的现在学习了前序、中序、后序遍历就可以利用它们来创建和销毁二叉树。
5.1二叉树的创建
二叉树遍历OJ链接
BTNode* BuyNode(DataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc failed);return NULL;}newnode-left NULL;newnode-right NULL;newnode-val x;return newnode;
}
BTNode* CreateBT(char* arr, int* pi,int size)
{ //ABC##DE#G##F###if (*pi size)//递归的停止条件{return NULL;}if (arr[*pi] #){(*pi);//遇到#,不要忘记跳过return NULL;}BTNode* root BuyNode(arr[(*pi)]);root-left CreateBT(arr, pi,size);root-right CreateBT(arr, pi,size);return root;
}
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%c , root-val);InOrder(root-right);
}
int main()
{char arr[100] { 0 };scanf(%s, arr);int i 0;int size strlen(arr);BTNode* root CreateBT(arr, i,size);InOrder(root);
}结果
5.2二叉树的销毁
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{//如果用前序或者中序遍历销毁二叉树会导致内存泄漏找不到左右子树//所以用后序遍历销毁二叉树if (root NULL){return;}BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root);root NULL;
}
