家用电脑做网站教程,新浪企业邮箱,网站员工风采,做一个小公司网站多少钱文章目录 前言二叉树的链式结构二叉树的遍历方式二叉树的深度优先遍历前序遍历(先根遍历)中序遍历(中根遍历)后序遍历(后根遍历) 二叉树的广度优先遍历层序遍历 二叉树链式结构接口实现二叉树结点个数二叉树叶子结点个数二叉树的深度#xff08;高度#xff09;二叉树第k层结… 文章目录 前言二叉树的链式结构二叉树的遍历方式二叉树的深度优先遍历前序遍历(先根遍历)中序遍历(中根遍历)后序遍历(后根遍历) 二叉树的广度优先遍历层序遍历 二叉树链式结构接口实现二叉树结点个数二叉树叶子结点个数二叉树的深度高度二叉树第k层结点个数二叉树查找x值的结点销毁二叉树二叉树的创建及遍历 衍生题判断二叉树是否为完全二叉树判断二叉树是否为单值二叉树判断两颗二叉树是否相同判断二叉树是否为对称二叉树判断一颗二叉树是否为另一颗二叉树的子树判断二叉树是否为平衡二叉树翻转二叉树 前言
二叉树的顺序结构就是用数组来存储而「数组」一般只适合表示「满二叉树」或「完全二叉树」因为不是完全二叉树会有「空间的浪费」。 普通二叉树的增删查改没有意义主要学习它的结构要加上搜索树的规则才有价值。
二叉树的链式结构
二叉树链式结构的实现 在学习二叉树的基本操作前需先要创建一棵二叉树这里手动快速创建一棵简单的二叉树
#includestdio.h // perror, printf
#includestdlib.h // malloctypedef char BTDataType;
// 定义二叉树的结点
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 动态申请一个新结点
BTNode* BuyNode(BTDataType x)
{// BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc);exit(-1);}newnode-data x;newnode-left newnode-right NULL;return newnode;
}// 二叉树的链式结构
BTNode* CreatBinaryTree()
{// 创建多个结点BTNode* node_A BuyNode(A);BTNode* node_B BuyNode(B);BTNode* node_C BuyNode(C);BTNode* node_D BuyNode(D);BTNode* node_E BuyNode(E);BTNode* node_F BuyNode(F);// 用链来指示结点间的逻辑关系node_A-left node_B;node_A-right node_C;node_B-left node_D;node_C-left node_E;node_C-right node_F;return node_A;
}
注意上述代码并不是创建二叉树的方式
二叉树的遍历方式
二叉树的深度优先遍历
由于被访问的结点必是「某子树的根」所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
前序遍历(先根遍历)
遍历顺序根-左子树-右子树
//前序遍历
void BinaryPrevOrder(BTNode* root)
{if (root NULL){return;}//根-左子树-右子树printf(%c , root-data);BinaryPrevOrder(root-left);BinaryPrevOrder(root-right);
}
这里的访问路径是A B D NULL NULL NULL C E NULL NULL F NULL NULL 接下来的两个遍历可以自己试试画一下递归图。
中序遍历(中根遍历)
遍历顺序左子树-根-右子树
void BinaryInOrder(BTNode* root)
{if (root NULL){return;}//左子树-根-右子树BinaryInOrder(root-left);printf(%c , root-data);BinaryInOrder(root-right);
}
这里的访问路径是NULL D NULL B NULL A NULL E NULL C NULL F NULL
后序遍历(后根遍历)
遍历顺序左子树-右子树-根
//后序遍历
void BinaryPostOrder(BTNode* root)
{if (root NULL){return;}//左子树-右子树-根BinaryPostOrder(root-left);BinaryPostOrder(root-right);printf(%c , root-data);
}
这里的访问路径是NULL NULL D NULL B NULL NULL E NULL NULL F C A
二叉树的广度优先遍历
层序遍历
层序遍历自上而下从左往右逐层访问树的结点的过程就是层序遍历。 我们借助队列来实现 先入根结点然后出队列再入他的两个孩子然后一样的出孩子再入孩子的孩子重复即可。NULL不入
//层序遍历
void BinaryLevelOrder(BTNode* root)
{Queue q;QueueInit(q);//初始化队列if (root ! NULL)QueuePush(q, root);int levelSize 1;while (!QueueEmpty(q))//当队列不为空时循环继续{//一层一层出while (levelSize--){BTNode* front QueueFront(q);//读取队头元素QueuePop(q);//删除队头元素printf(%c , front-data);//打印出队的元素if (front-left){QueuePush(q, front-left);//出队元素的左孩子入队列}if (front-right){QueuePush(q, front-right);//出队元素的右孩子入队列}}printf(\n);levelSize QueueSize(q);}printf(\n);QueueDestroy(q);//销毁队列
}二叉树链式结构接口实现
二叉树结点个数
子问题拆解 1.若为空则结点个数为0。 2.若不为空则结点个数 左子树结点个数 右子树结点个数 1自己。
//结点的个数
int BinaryTreeSize(BTNode* root)
{//结点个数 左子树的结点个数 右子树的结点个数 自己return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}二叉树叶子结点个数
子问题拆解 1.若为空则叶子结点个数为0。 2.若结点的左指针和右指针均为空则叶子结点个数为1。 3.除上述两种情况外说明该树存在子树其叶子结点个数 左子树的叶子结点个数 右子树的叶子结点个数。
//叶子结点的个数
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);
}二叉树的深度高度
子问题拆解
先判断当前树的根结点是否为空当前树的根结点不为空分别计算其左右子树的深度比较当前树左右子树的深度最大的那个1 就是当前树的深度
// 二叉树的深度(高度)
int BinaryTreeMaxDepth(BTNode* root)
{// 先判断当前树的根结点是否为空if (root NULL){return 0;}// 当前树的根结点不为空分别计算其左右子树的深度int leftDepth BinaryTreeMaxDepth(root-left);int rightDepth BinaryTreeMaxDepth(root-right);// 比较当前树左右子树的深度最大的那个1 就是当前树的深度return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}二叉树第k层结点个数
//第k层结点的个数O(N)
int BinaryTreeKLevelSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)//第一层结点个数return 1;//相对于父结点的第k层的结点个数 相对于两个孩子结点的第k-1层的结点个数之和return BinaryTreeKLevelSize(root-left, k - 1) BinaryTreeKLevelSize(root-right, k - 1);
}二叉树查找x值的结点
//查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)//空树return NULL;if (root-data x)//先判断根结点return root;BTNode* leftret BinaryTreeFind(root-left, x);//在左子树中找if (leftret)return leftret;BTNode* rightret BinaryTreeFind(root-right, x);//在右子树中找if (rightret)return rightret;return NULL;//根结点和左右子树中均没有找到
}销毁二叉树
这里要用后序遍历来销毁左子树-右子树-根
//销毁二叉树
void BinaryTreeDestroy(BTNode* root)
{if (root NULL)return;BinaryTreeDestroy(root-left);BinaryTreeDestroy(root-right);free(root);//没有用二级指针这里只是实参的拷贝需要用完主动置空再函数外置空}二叉树的创建及遍历
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。 依次读取字符拆分成子问题 1.如果不是#创建结点存值然后递归其左子树和右子树 2.如果是#说明不能构建结点了直接返回NULL
#include stdio.htypedef char BTDataType;
typedef struct BinaryTreeNode{BTDataType data;struct BinaryTreeNode*left;struct BinaryTreeNode*right;}BTNode;BTNode*BinaryTreeCreat(char*arr,int*pi)
{if(arr[*pi]#){(*pi);return NULL;}BTNode*node(BTNode*)malloc(sizeof(BTNode));node-dataarr[*pi];(*pi);node-leftNULL;node-rightNULL;
node-leftBinaryTreeCreat(arr,pi);//递归构建左子树
node-rightBinaryTreeCreat(arr,pi);//递归构建右子树
return node;
}//中序遍历
void BinaryInOrder(BTNode*root)
{if(rootNULL)return;BinaryInOrder(root-left);printf(%c ,root-data);BinaryInOrder(root-right);
}int main() {
char ret[100];
scanf(%s,ret );
int i0;
BTNode*root BinaryTreeCreat(ret,i);
BinaryInOrder(root);
printf(\n);return 0;
}衍生题
判断二叉树是否为完全二叉树
用一个队列来判断 将根从队尾入列然后从队头出数据出根的时候入它的左孩子和右孩子NULL也入列。重复次操作当出数据第一次遇到NULL时停止入队列并且检查队列中是否还有数据如果全部为NULL则此树时完全二叉树 如果队列中还有数据则不是完全二叉树。
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);//初始化队列if (root ! NULL)QueuePush(q, root);while (!QueueEmpty(q))//当队列不为空时循环继续{BTNode* front QueueFront(q);//读取队头元素QueuePop(q);//删除队头元素//遇到第一个NULL结点直接跳出循环if (front NULL)break;QueuePush(q, front-left);//出队元素的左孩子入队列NULL也入QueuePush(q, front-right);//出队元素的右孩子入队列NULL也入}//前面遇到空以后后面还有非空就不是完全二叉树while (!QueueEmpty(q))//当队列不为空时循环继续{BTNode* front QueueFront(q);//读取队头元素QueuePop(q);//删除队头元素if (front){QueueDestroy(q);//销毁队列return false;}}//没有遇到说明是完全二叉树QueueDestroy(q);//销毁队列return true;
}判断二叉树是否为单值二叉树
单值二叉树所有结点的值都相同的二叉树即为单值二叉树判断某一棵二叉树是否是单值二叉树的一般步骤如下 1.判断根的左孩子的值与根结点是否相同。 2.判断根的右孩子的值与根结点是否相同。 3.判断以根的左孩子为根的二叉树是否是单值二叉树。 4.判断以根的右孩子为根的二叉树是否是单值二叉树。 若满足以上情况则是单值二叉树。
bool isUnivalTree(struct TreeNode* root) {if(rootNULL)return true;if(root-leftroot-left-val!root-val) return false;if(root-rightroot-right-val!root-val)return false;return isUnivalTree(root-left)isUnivalTree(root-right);
}判断两颗二叉树是否相同
拆分成子问题 先判断根是否为空 再比较根的左子树是否相同 再比较跟根的右子树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if(pNULLqNULL)return true;if(pNULL||qNULL)return false;if(p-val!q-val)return false;return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}判断二叉树是否为对称二叉树
实际上就是要判断根节点的左右两个子树是否镜像对称。因此其解决方案为按照对称的方式遍历左右子树比较同时遍历的节点是否一致。而且在遍历过程中只有两个子树的根节点对称了继续比较左右子树是否对称才有意义因此我们使用中序遍历其实不是严格的中序遍历只是我们先比较根节点
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(pNULLqNULL)return true;if(pNULL||qNULL)return false;if(p-val!q-val)return false;return isSameTree(p-left,q-right)isSameTree(p-right,q-left);}bool isSymmetric(struct TreeNode* root) {if(rootNULL)return true;return isSameTree(root-left,root-right);}判断一颗二叉树是否为另一颗二叉树的子树
两个树都是空树返回true 如果两个树一个是空一个不是空不包含 两个树都是非空比较根节点的值是不是相等如果相等的话比较一下p和q是不是相同的树 递归的判定一下p是否被q的左子树包含 递归的判定一下p是否被q的右子树包含。
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(pNULLqNULL)return true;if(pNULL||qNULL)return false;if(p-val!q-val)return false;return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(rootNULL)return false;if(isSameTree(root-left,subRoot))return true;return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);}判断二叉树是否为平衡二叉树
如果某二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树。 子问题 求出左子树的深度。 求出右子树的深度。 若左子树与右子树的深度差的绝对值不超过1并且左右子树也是平衡二叉树则该树是平衡二叉树。
int max(int x, int y)
{return xy?x:y;
}
int height(struct TreeNode* root)
{if (root NULL) return 0;return max(height(root-left), height(root-right)) 1;
}bool isBalanced(struct TreeNode* root)
{if (root NULL) return true;//左右子树高度差的绝对值不超过1 其左子树是平衡二叉树 其右子树是平衡二叉树return fabs(height(root-left) - height(root-right)) 1 isBalanced(root-left) isBalanced(root-right);//fabs取绝对值要用要包含头文件#includemath.h
}翻转二叉树
子问题 翻转左子树。 翻转右子树。 交换左右子树的位置。
//翻转二叉树
struct TreeNode* invertTree(struct TreeNode* root)
{if (root NULL)//根为空直接返回return root;struct TreeNode* left invertTree(root-left);//翻转左子树struct TreeNode* right invertTree(root-right);//翻转右子树//左右子树位置交换root-left right;root-right left;return root;
}
