赞
踩
目录
既然是链式二叉树必然就少不了每一个节点,这里我们以链式二叉树节点的定义,定义每一个结点,节点结构体内包含:数据域,左指针域和右指针域
- typedef int BTDataType;//重命名数据类型,方便以后更改需要储存的数据
- typedef struct BinaryTreeNode
- {
- BTDataType data;
- struct BinaryTreeNode* left;//指向左孩子
- struct BinaryTreeNode* right;//指向右孩子
- }BTNode;
随意给出一棵树如下图所示:
- //创造一个节点,值给为x,左右孩子置为NULL
- BTNode* BuyNode(BTDataType x)
- {
- BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
- if (tmp == NULL)
- {
- printf("malloc fail\n");
- exit(-1);
- }
- tmp->data = x;
- tmp->left = tmp->right = NULL;
- }
-
- 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;
- }
链式二叉树我们采用递推来定义的学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二树中的节点进行相应的操作,并且每个节点只操作一次。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
根据访问顺序的不同,遍历分为以下几种顺序:
①前序遍历:根->左子树->右子树
②中序遍历:左子树->根->右子树
③后续遍历:左子树->右子树->根
④层序遍历:从根节点开始,从上到下,从左到右依次遍历
访问根节点的操作发生在遍历其左右子树之前
动图演示
代码演示
- //前序遍历
- void PreOrder(BTNode* root)
- {
- if (root == NULL)
- return;
-
- printf("%d ", root->data);
- PreOrder(root->left);
- PreOrder(root->right);
- }
遍历结果:我们可以推出,跟随小白人的轨迹,从根节点开始,依次循环一周回到起点
得到:A B D H I E J C F K G
访问根节点的操作发生在遍历其左右子树之中
动图演示:
代码演示
- //中序遍历
- void InOrder(BTNode* root)
- {
- if (root == NULL)
- return;
-
- InOrder(root->left);
- printf("%d ", root->data);
- InOrder(root->right);
- }
遍历结果:我们可以推出二级结论,最后结果每个根节点的垂直落到地上最后一层,然后从左往右输出即可
得到:H D I B E J A F K C G
访问根节点的操作发生在遍历其左右子树之后
动图演示
代码演示
- //后序遍历
- void PostOrder(BTNode* root)
- {
- if (root == NULL)
- return;
-
- PostOrder(root->left);
- PostOrder(root->right);
- printf("%d ", root->data);
- }
遍历结果:我们同样可以推出二级结论:将所有的结点看做葡萄一样,然后遍历就像在剪葡萄一样,从下往上,从左往右,必须先把左子树上的葡萄剪完后,才能剪右子树上的葡萄
得到:H I D J E B K F G C A
层序遍历就是从根节点开始,从上往下,从左往右,一层一层的遍历即可
代码如下:
- //层序遍历 队列的类型是二叉树节点的指针
- void BinaryTreeLevelOrder(BTNode* root)
- {
- if (root == NULL)
- return;
- Queue q;
- QueueInit(&q);
- QueuePush(&q,root);
- while (!QueueEmpty(&q))
- {
- BTNode* front = QueueFront(&q);
- QueuePop(&q);
- printf("%d ",front->data);
-
- //带孩子进入队列
- if (front->left)
- {
- QueuePush(&q,front->left);
- }
- if (front->right)
- {
- QueuePush(&q, front->right);
- }
-
- }
- printf("\n");
- QueueDestroy(&q);
- }
层序遍历结果:1 2 4 3 5 6
这里我们是用队列实现的层序遍历,借助队列先进先出的性质,当前层数据出队列的时候带入下一层数据。
思路:1、先入根
2、当前节点出队列,把当前节点的左右孩子带入队列,遇到孩子为空(NULL)不管
3、当对列为空时,遍历结束
注意:队列中要存放该节点的指针(而不是值),才能带入下一层节点
由于链式二叉树是递归定义的,我们可以采用分治的思想:
①若为空,则结点总个数为0
②若不为空,则总结点数=左子树结点数+右子树结点数+1(自己)
代码如下
- //二叉树的节点个数
- int BinaryTreeSize(BTNode* root)
- {
- return root == NULL ? 0 :
- BinaryTreeSize(root->left)
- + BinaryTreeSize(root->right) + 1;//左+右+自己(+1)
- }
也是采用分治思想
①如果根为空,直接返回
②如果左右孩子都为空,意味着只有自己一个节点,返回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层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。
- //二叉树第k层节点数
- int BinaryTreeKLevelSize(BTNode* root, int k)
- {
- if (k < 1 || root == NULL)//空树或输入k值不合法
- return 0;
- if (k == 1)//第一层结点个数
- return 1;
- //相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和
- return BinaryTreeKLevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
- }
思路:
①先判断根结点是否是目标结点。
②再去左子树中寻找。
③最后去右子树中寻找。
- //二叉树中查找值为k的节点
- 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;//根结点和左右子树中均没有找到
- }
思路:
1.若为空树,则深度为0。
2.若不为空,则树的最大深度 = 左右子树中深度较大的树的高度 + 1。
采用分治思想
-
- // 二叉树深度/高度
- int BinaryTreeDepth(BTNode* root)
- {
- if (root == NULL)
- {
- return 0;
- }
-
- //return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? BinaryTreeDepth(root->left) + 1 : BinaryTreeDepth(root->right) + 1;
-
- int leftDepth = BinaryTreeDepth(root->left);
- int rightDepth = BinaryTreeDepth(root->right);
-
- return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
- }
这里和二叉树的层序遍历很像,但是有着些不同点:
代码如下:
- //判断二叉树是否是完全二叉树
- bool isCompleteTree(BTNode* root)
- {
- Queue q;
- QueueInit(&q);//初始化队列
- if (root != NULL)
- QueuePush(&q, root);
- while (!QueueEmpty(&q))//当队列不为空时,循环继续
- {
- BTNode* front = QueueFront(&q);//读取队头元素
- QueuePop(&q);//删除队头元素
- if (front == NULL)//当读取到空指针时,停止入队操作
- break;
- QueuePush(&q, front->left);//出队元素的左孩子入队列
- QueuePush(&q, front->right);//出队元素的右孩子入队列
- }
- while (!QueueEmpty(&q))//读取队列中剩余的数据
- {
- BTNode* front = QueueFront(&q);
- QueuePop(&q);
- if (front != NULL)//若队列中存在非空指针,则不是完全二叉树
- {
- QueueDestroy(&q);//销毁队列
- return false;
- }
- }
- QueueDestroy(&q);//销毁队列
- return true;//若队列中全是空指针,则是完全二叉树
- }
二叉树销毁时,也是一边遍历,一边销毁,但是二叉树销毁的顺序有一点不同,是采用后续遍历销毁的,就是:左子树->右子树->根,最后来销毁根。
- //二叉树的销毁
- void BinaryTreeDestroy(BTNode* root)
- {
- if (root == NULL)
- return;
- BinaryTreeDestroy(root->left);
- BinaryTreeDestroy(root->right);
- free(root);
- }
解题思想:单值二叉树要树的每个节点的值都要相同
同样采用分治思想:①根的左孩子和根的值比较
②根的右孩子和根的值比较
③分别以左右孩子再为根,再比较
④空树也是单值二叉树
代码如下:
- 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);
- }
解题思想:判断两棵树相同要树形相同而且节点的值要相同
同样采用分治思想:从根开始分为4种情况
①两树根都是为空
②两树中有一个为空
③都不为空
④根相同了,再分别比较左右子树的值
- 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 _isSymmetricTree(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 _isSymmetricTree(root1->left,root2->right)
- &&_isSymmetricTree(root1->right,root2->left);
-
- }
-
- bool isSymmetric(struct TreeNode* root)
- {
- if(root==NULL)
- return true;
- return _isSymmetricTree(root->left,root->right);
-
- }
解题思想:用root的每一个子树都和subRoot比较一下
代码如下:
- 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;
-
- return isSubtree(root->left,subRoot)
- ||isSubtree(root->right,subRoot);
- }
题目描述:
我们先前序遍历把这棵树给建出来:
解题思想:
①若该字符不是#,则我们先构建该值的结点,然后递归构建其左子树和右子树。
②若该字符是#,则说明该位置之下不能再构建结点了,返回即可。
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct TreeNode
- {
- struct TreeNode* left;
- struct TreeNode* right;
- char data;
- }TreeNode;
- //创建树
- TreeNode* CreateTree(char* str, int* pi)
- {
- if(str[*pi] == '#')//
- {
- (*pi)++;
- return NULL;
- }
- //不是NULL,构建结点
- TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
- root->left = NULL;
- root->right = NULL;
- root->data = str[*pi];
- (*pi)++;
- //递归构建左子树
- root->left = CreateTree(str, pi);
- //递归构建右子树
- root->right = CreateTree(str, pi);
- return root;
- }
- //中序遍历
- void Inorder(TreeNode* 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;
- TreeNode* root = CreateTree(str, &i);
- Inorder(root);
- return 0;
- }
PS:本篇博客中的前序,中序,后续遍历的动图借鉴了一下这位博主的精品文章
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。