长春专业做网站公司哪家好,温州网站推广外包,宁波江北区网站推广联系方式,太原电商网站设计目录
一.二叉树链式结构的概念
二.二叉树链式结构的功能实现
2.1.链式二叉树的定义
2.2.链式二叉树的构建
2.3.链式二叉树的遍历
2.3.1.先序遍历
2.3.2.中序遍历
2.3.3.后序遍历
2.3.4.层序遍历
2.4.链式二叉树的求二叉树的结点数量
法一#xff1a;计数法
法二计数法
法二分治法
2.5.链式二叉树的求二叉树的叶子结点数量
2.6.链式二叉树的求二叉树第k层结点的数量
2.7.链式二叉树的求二叉树的高度
2.8.链式二叉树的查找二叉树中值为x的结点
2.9.链式二叉树的判断二叉树是否是完全二叉树
2.10.链式二叉树的二叉树的销毁
三.二叉树基础OJ练习
题一单值二叉树
题二相同的树
题三对称二叉树
题四另一棵树的子树
题五二叉树的前序遍历
题六二叉树遍历 前置说明
在学习二叉树的基本操作之前需要先创建一棵二叉树然后才能学习其相关的基本操作。由于现在对于二叉树的结构掌握还不够深为了降低大家的学习成本此处手动创建一棵简单的二叉树以便快速进入二叉树的操作学习。等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。
一.二叉树链式结构的概念
对于任意的二叉树来说每个结点只有一个双亲结点(根除外)最多有两个孩子。可以设计每个结点至少包括三个域数据域data左孩子域left和右孩子域right。其中left域指向该结点的左孩子data域记录该结点的信息right域指向该结点的右孩子。此结点结构形成的二叉树称为二叉链表。 二.二叉树链式结构的功能实现
若有n个结点则有2n个指针域而除了根结点每个结点头上都会连一个指针故n个结点的二叉链表共有n1个空链域。
2.1.链式二叉树的定义
typedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左孩子指针struct BinaryTreeNode* right;//右孩子指针BTDataType data;//数据域
}BTNode;
2.2.链式二叉树的构建
//创建结点
BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}//构造二叉树
BTNode* CreatBinaryTree()
{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;
}
调试分析 运行结果 注意
这种方式可以很简单地找到指定结点的左右孩子但是要找到指定结点的父结点就只能从根结点开始遍历寻找。
2.3.链式二叉树的遍历
二叉树的遍历是指按一定规律对二叉树中的每个结点进行访问且仅访问一次。二叉树是非线性数据结构通过遍历可以将二叉树中的结点访问一次且仅一次从而得到访问结点的顺序序列。从这个意义上说遍历操作就是将二叉树中结点按一定规律线性化的操作目的在于将非线性化结构变成线性化的访问序列。
用L,D,R分别表示遍历左子树访问根结点遍历右子树。如果规定按先左后右的顺序根据对根的访问先后顺序的不同可以将DLR称为先序遍历或先根遍历将LDR称为中序遍历将LRD称为后序遍历。
注意先序中序和后序遍历都是递归定义的即在其子树中亦按上述规律进行遍历。
案例分析 2.3.1.先序遍历
若二叉树为空则什么也不做否则依次执行如下三个操作
访问根结点先序遍历左子树先序遍历右子树。 实现
void PreOrder(BTNode* root)
{//若树为空则退出if (root NULL){printf(# );//若结点为空则用#表示return;}//先访问根结点printf(%d , root-data);//然后访问左子树PreOrder(root-left);//再访问右子树PreOrder(root-right);
}
运行结果 递归分析 2.3.2.中序遍历
若二叉树为空则什么也不做否则依次执行如下三个操作
中序遍历左子树访问根结点中序遍历右子树。
实现
void InOrder(BTNode* root)
{//若树为空则退出if (root NULL){printf(# );//若结点为空则用#表示return;}//先访问左子树InOrder(root-left);//然后访问根结点printf(%d ,root-data);//再访问右子树InOrder(root-right);
}
运行结果 递归分析 2.3.3.后序遍历
若二叉树为空则什么也不做否则依次执行如下三个操作
后序遍历左子树后续遍历右子树访问根结点。
实现
void PostOrder(BTNode* root)
{//若树为空则退出if (root NULL){printf(# );//若结点为空则用#表示return;}//先访问左子树PostOrder(root-left);//然后访问右子树PostOrder(root-right);//再访问根结点printf(%d , root-data);
}
运行结果 小结
递归算法的时间复杂度分析设二叉树有n个结点对每个结点都要进行一次入栈和出栈的操作即入栈和出栈各执行n次对结点的访问也是n次。这些二叉树递归遍历算法的时间复杂度为0(n)。
2.3.4.层序遍历
设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树的根结点然后从左到右访问第二层的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
实现方式采用辅助队列实现按层序遍历二叉树。 算法思想
初始化一个辅助队列根结点入队若队列非空则队头结点出队访问该结点并将其左右孩子插入队尾(如果有的话)重复第三步直至队列为空。
实现
void LevelOrder(BTNode* root)
{//创建队列并初始化Queue q;QueueInit(q);//若根结点不为空则先将根结点入队if (root){//入队QueuePush(q, root);}//若队列非空while (!QueueEmpty(q)){//取队头元素BTNode* front QueueFront(q);//访问队头结点printf(%d ,front-data);//出队QueuePop(q);//若左结点存在则左结点入队if (front-left){//入队QueuePush(q, front-left);}//若右节点存在则右结点入队if (front-right){//入队QueuePush(q, front-right);}}printf(\n);//销毁队列QueueDestory(q);
}
运行结果 2.4.链式二叉树的求二叉树的结点数量
法一计数法
在递归调用过程中局部变量和全局变量的传递方式可以类似的看成函数调用时的值传递和引用传递。
局部变量类似于值传递过程中的形参和实参可以看成是两个完全不同的值只是名字相同而已。每次递归调用时都会重新创建新的变量它并不会覆盖掉上次递归调用过程中创建的值。
全局变量类似于传地址过程中的形参和实参可以看成是同一个变量。每次递归调用时并不会重新创建新的变量在递归过程中对全局变量的修改会影响到下一次递归调用过程中的值。
所以我们在使用计数器进行结点个数统计是要定义全局变量而非局部变量。
当使用局部变量时
int TreeSize(BTNode* root)
{int count 0;//若树为空if (root NULL){return;}//统计根结点count;//统计左子树TreeSize(root-left);//统计右子树TreeSize(root-right);return count;
}
运行结果 当使用全局变量时
int count 0;//不能定义一个局部变量因为每次递归调用都会重新初始化为0void TreeSize(BTNode* root)
{//若树为空if (root NULL){return;}//统计根结点count;//统计左子树TreeSize(root-left);//统计右子树TreeSize(root-right);}运行结果 这里存在一个问题当我们多次打印输出结果时可以发现每次的输出结果并不相同。如下所示 为了避免该类问题的出现只需在每次调用之前要将count进行初始化防止下次调用时将前一次的调用结果进行累加。如下所示 法二分治法
使用计数法计算结点个数时存在较多需要注意的问题而使用分治法可以有效解决此类问题。
采用递归算法首先判断树是否为空树若为空树则返回0若不是空树则将根结点root的左孩子结点和右孩子结点作为参数传给函数TreeSize进行递归调用。
实现
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
递归分析 运行结果 2.5.链式二叉树的求二叉树的叶子结点数量
采用递归算法如果是空树返回0如果只有一个结点返回1否则为左右子树的叶子结点数之和。
实现
int TreeLeafSize(BTNode* root)
{//若树为空if (root NULL){return 0;}//若为单独的叶子即只含一个结点if (root-left NULL root-right NULL) {return 1;}//若树不为空也不为单独的叶子return TreeLeafSize(root-left) TreeLeafSize(root-right);
}
运行结果 2.6.链式二叉树的求二叉树第k层结点的数量
采用递归算法首先判断k的取值是否合法k的取值不能小于1然后判断树是否为空如果是空树则返回0如果树不为空且k的值为1则返回1否则为左右子树的第k-1层的结点数之和。
实现
int TreeKLevel(BTNode* root, int k)
{//检查k的范围assert(k 1);//若树为空if (root NULL){return 0;}//若树不为空且k等于1也就是根结点所在层次if (k 1){return 1;}//求左子树和右子树的第k-1层的结点数之和return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}递归分析 运行结果 2.7.链式二叉树的求二叉树的高度
采用递归算法首先判断树是否为空若为空则返回0若不为空则递归求左子树的高度和右子树的高度然后再求出左子树和右子树高度的较大值最后再将高度的最大值1即为所求二叉树的高度。
实现
int TreeDepth(BTNode* root)
{//若树为空if (root NULL){return 0;}//求左树的高度int leftDepth TreeDepth(root-left);//求右树的高度int rightDepth TreeDepth(root-right);//求两者中较大值return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
运行结果 2.8.链式二叉树的查找二叉树中值为x的结点
采用递归算法首先判断树是否为空若树为空则返回NULL。当树不为空且根结点为所要查找的结点时则返回根结点。否则递归遍历左子树和右子树。
实现
BTNode* TreeFind(BTNode* root, BTDataType x)
{//若树为空if (root NULL){return NULL;}//若根结点为所要查找的结点if (root-data x){return root;}//查找左子树BTNode* ret1 TreeFind(root-left, x);//若返回值不为空if (ret1){return ret1;}//查找右子树BTNode* ret2 TreeFind(root-right, x);//若返回值不为空if (ret2){return ret2;}return NULL;
}
递归分析 运行结果 2.9.链式二叉树的判断二叉树是否是完全二叉树
完全二叉树对于一棵深度为h的二叉树其前h-1层结点个数均达到最大值第h层结点个数可能没有达到最大值但从左到右是连续的。
算法思想
初始化一个辅助队列根结点入队若队列非空则队头结点出队访问该结点并将其左右孩子插入队尾(包含空结点)重复第三步直至遇到空结点并查看其后续是否有非空结点。若有则该二叉树不是完全二叉树若没有则该二叉树是完全二叉树。
实现
int TreeComplete(BTNode* root)
{//初始化队列Queue q;QueueInit(q);//先将根结点入队if (root){QueuePush(q, root);}while (!QueueEmpty(q)){//读取队头元素并出队BTNode* front QueueFront(q);QueuePop(q);//若队头结点非空if (front){//左结点入队包含空结点QueuePush(q, front-left);//右结点入队包含空结点QueuePush(q, front-right);}else{//遇到空则跳出层序遍历break;}}//1.如果空后面全是空结点则是完全二叉树//2.如果空后面还有非空结点则不是完全二叉树while (!QueueEmpty(q)){//读取队头元素并出队BTNode* front QueueFront(q);QueuePop(q);//front存放的是树的结点的指针if (front){QueueDestory(q);return false;}}//销毁QueueDestory(q);return true;
}
运行结果 2.10.链式二叉树的二叉树的销毁
采用递归算法首先判断树是否为空若为空则返回NULL。若树不为空则先递归销毁左子树然后再销毁右子树最后再释放根结点。
实现
void TreeDestroy(BTNode* root)
{//若树为空if (root NULL){return;}//销毁左子树TreeDestroy(root-left);//销毁右子树TreeDestroy(root-right);printf(%p:%d\n, root, root-data);//释放根结点free(root);
}运行结果 三.二叉树基础OJ练习
题一单值二叉树
题目描述
如果二叉树每个结点都具有相同的值那么该二叉树就是单值二叉树。只有给定的树是单值二叉树才返回true否则返回false。
法一标记法
设置标志位flag进行单值二叉树的判断。若树为空或者标志位flag为flase则直接返回若根结点的值不等于val则将标志位flag设为flase同时返回若上述两个条件均满足则递归遍历左子树和右子树。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};//法一设置标记位
bool flag true;
void PreOrderCompare(struct TreeNode* root, int val)
{//若树为空if (root NULL || flag false)//flagflase若左子树不满足条件则直接退出以免对右子树进行不必要的递归遍历{return;}//如果根结点的值不等于val则直接退出不用往下递归if (root-val ! val){flag false;return;}//比较左子树PreOrderCompare(root-left, val);//比较右子树PreOrderCompare(root-right,val);
}bool isUnivalTree(struct TreeNode* root)
{//若树为空if (root NULL){return true;}flag true;PreOrderCompare(root, root-val);return flag;
}
法二
首先判断根结点root是否为NULL若为空则直接返回true。然后判断根结点root的左孩子与右孩子是否为空且其值与root的值是否相同若不同则返回false若相同则直接递归遍历root的左子树和右子树判断其否为单值二叉树。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};bool isUnivalTree(struct TreeNode* root)
{//如果树为空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);//递归调用的返回都是返回到递归调用的上一层
}递归分析 题二相同的树
题目描述
给你两棵二叉树的根结点p和q编写一个函数来检验这两棵树是否相同。如果两棵树在结构上相同并且结点具有相同的值则认为它们是相同的。
分析
首先判断两棵树是否均为空若均为空则返回true若有一棵树为空则返回false。然后在两棵树均不为空的情况下判断其对应的根结点的值是否相等若不相等则返回false。最后再递归遍历两棵树对应的左子树和右子树判断其对应的结点值是否相等。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};bool isSameTree(struct TreeNode* p, struct TreeNode* 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);
}
题三对称二叉树
题目描述
给你一个二叉树的根结点root检查它是否轴对称。
分析
首先判断树是否为空若为空则返回true若不唯空则判断根结点root对应的左子树和右子树。然后转为对左子树和右子树的判断若两棵子树均为空咋返回true若有一棵子树为空则返回false若两棵子树均不为空且其对应的根结点的值不相等则返回false。最后再递归遍历判断左子树的左子树与右子树的右子树以及左子树的右子树与右子树的左子树是否相等。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};bool isSymmetricSubTree(struct TreeNode* root1, struct TreeNode* root2)
{//若两棵树均为空if (root1 NULL root2 NULL){return true;}//若有一棵树为空if (root1 NULL || root2 NULL){return false;}//若两棵树均不为空if (root1-val ! root2-val){return false;}return isSymmetricSubTree(root1-left, root2-right) isSymmetricSubTree(root1-right, root2-left);
}bool isSymmetric(struct TreeNode* root)
{//若树为空if (root NULL){return true;}//若树不为空return isSymmetricSubTree(root-left, root-right);
}
题四另一棵树的子树
题目描述
给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在返回true否则返回false。 二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看做它自身的一棵子树。
分析
遍历二叉树root中的每一个结点然后将每一个结点都作为根结点并与subRoot的根结点进行比较若对应的根结点值相同则调用函数isSameTree进行左右子树的比较。如果左右子树均相同则subRoot是root的子树否则继续将二叉树root的下一个结点与subRoot的根结点进行比较。重复上述操作直至找到一棵子树与二叉树subRoot相同或者二叉树root的所有子树均与subRoot不同并退出。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};bool isSameTree(struct TreeNode* p, struct TreeNode* 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);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{//若树为空if (root NULL)return false;//若树不为空if (isSameTree(root, subRoot)){return true;}//将原树中所有子树都找出来然后跟subRoot比较return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}
递归分析 题五二叉树的前序遍历
题目描述
给你二叉树的根结点root返回它结点值的前序遍历。
分析
实现函数TreeSize用以统计二叉树中的结点个数并返回给returnSize。同时开辟好returnSize个int 类型大小的数组空间用于存放遍历后的各个结点。最后再调用函数preorder进行先序遍历并返回数组首元素的地址。
实现
struct TreeNode
{int val;struct TreeNode* left;struct TreeNode* right;
};//求二叉树的结点个数
int TreeSize(struct TreeNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}//前序遍历并将遍历后的结点值存入数组中
void preorder(struct TreeNode* root, int* a, int* pi)//pi的值要加引用否则形参的修改不会影响实参
{//如果树为空if (root NULL){return;}//若树不为空a[(*pi)] root-val;//遍历左子树preorder(root-left, a, pi);//遍历右子树preorder(root-right, a, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//*returnSize用于接收二叉树的节点个数*returnSize TreeSize(root);//开辟*returnSize个int类型大小的空间用于存放遍历后的结点int* a (int*)malloc(*returnSize * sizeof(int));//进行前序遍历int i 0;preorder(root, a, i);return a;
}
题六二叉树遍历
题目描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。例如如下的先序遍历字符串ABC##DE#G##F###其中#表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。
分析
根据所给的先序遍历字符串采用前序遍历的方式进行二叉树的创建再将创建好的二叉树进行中序遍历即可。
实现
//二叉树的定义
typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;//左子树struct BinaryTreeNode* right;//右子树BTDataType data;
}BTNode;//创建结点
BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}//前序创建二叉树
BTNode* CreateTree(char* str, int* pi)
{//若结点为空也就是空树空树数组的下标也要且为它malloc空间进行存储if (str[*pi] #){(*pi);return NULL;}//前序构建二叉树BTNode* root BuyNode(str[(*pi)]);root-left CreateTree(str, pi);root-right CreateTree(str, pi);return root;
}//中序遍历二叉树
void InOrder(BTNode* root)
{//判断树是否为空if (root NULL){return;}InOrder(root-left);printf(%c ,root-data);InOrder(root-right);
}int main()
{char str[100];scanf(%s, str);int i 0;BTNode* root CreateTree(str, i);InOrder(root);return 0;
}
递归分析
