南京平台公司,宁波seo免费优化软件,温州网站推广站建设,阿里云网站建设#x1f970;作者: FlashRider #x1f30f;专栏: 初阶数据结构 #x1f356;知识概要#xff1a;详解二叉树的概念、二叉树的遍历、以及代码实现。 目录
树的基本概念
树的存储结构与二叉树的实现
树的存储
什么是二叉树
二叉链存储二叉树
二叉树的代码实现 树的基本… 作者: FlashRider 专栏: 初阶数据结构 知识概要详解二叉树的概念、二叉树的遍历、以及代码实现。 目录
树的基本概念
树的存储结构与二叉树的实现
树的存储
什么是二叉树
二叉链存储二叉树
二叉树的代码实现 树的基本概念
我们说的树是一种非线性的数据结构它是由n(n0)个有限结点组成的具有层次关系的集合。 因为外形看起来像是一棵根朝上叶朝下的倒挂的树所以我们把它称作树。
注意子树不能有交集否则就不是树形结构即每个节点只能有一个父节点。
一些术语
节点的度一个节点含有的字数个数。 叶节点度为0的节点。 非叶节点/分支节点度不为0的节点。 父/双亲节点有子树的节点。 子节点有父节点的节点。 兄弟节点具有相同父节点的节点。 树的度整个树中节点的度取最大值。 节点的层次从根节点为第一层开始依次往下递增。 树的高度节点的最大层次。 祖先从根节点到该节点所经过的分支上所有的节点。 森林由m(m0)棵互不相交的树组成的集合。
树的图示 注树的节点存储什么样的数据根据情况而议图中使用字母表示节点只是为了方便。 树的存储结构与二叉树的实现
树的存储
我们可以观察一下树的结构首先对于每一个父节点来说它都有至少一个子节点如果有多个兄弟我们可以都看作兄弟节点。对于没有子节点或兄弟节点的节点我们可以把它的子节点或兄弟节点看作空。 因此我们可以发现任意节点都可以这么表示子节点兄弟节点。 字节点存储它的第一个儿子兄弟节点存储它的兄弟。这样根据一个儿子的兄弟节点就可以遍历所有的儿子而根据子节点又可以继续往深处找。
typedef int DataType;//树的数据类型
typedef struct TreeNode
{ struct Node* _child; //第一个孩子 struct Node* _brother; //自己的兄弟DataType _data; //节点内存的数据
}TNode;
而对于我们目前而言研究一些特殊的树就可以了而树中比较典型的一种就是二叉树。
什么是二叉树
二叉树是一种树的结点的有限集合该集合满足两个性质
1. 可以为空。 2. 由一个根加上左右两颗子树组成。 对于途中的结点2来说它的右子树为空对于3、5、6来说左右子树都为空但也满足二叉树的性质。因此这棵树是一颗二叉树。
完全二叉树
除了最后一层叶子结点可以不用铺满其他每一层的结点都必须满足最大值。比如上图中的第一层和第二层都满足结点为最多第三层叶子节点最多为4个但只有3个因为叶子节点不用满足铺满所以上图是一个完全二叉树。
满二叉树
每一层的结点都为最大值即每一层结点都铺满。满二叉树是一种特殊的完全二叉树。
二叉树的一些性质
1. 若根节点层次为1则一颗非空二叉树第i层最多有2的i-1次方。 2. 若根节点层次为1则深度为h的二叉树最大结点数为2的h次方-1。 3. 对于任何一颗二叉树如果度为0的叶节点个数为n0 则度为2的分支结点个数为n2则满足 n0 n2 1。 4. 若根节点层次为1则有n个结点的满二叉树深度为h log2(n1) 以2为底 n1为对数。 5. 如果从上到下从左到右根结点为0开始编号对于结点 i 则 5.1 若 i 不为0则(i-1)/2为父节点. 5.2 若2i1n 则2i1为左孩子。否则无左孩子。 5.3 若2i2n 则2I2为右孩子。否则无右孩子。
二叉链存储二叉树
我们可以使用链式结构存储二叉树。
typedef int DataType;//数据类型
typedef struct BinaryTreeNode
{struct BinaryTreeNode* _left;//左孩子struct BinaryTreeNode* _right;//右孩子DataType _data;//数据
}BTNode;
三叉链 如果使用三叉链存储二叉树那么就多一个指向父亲的指针可以快速找到父节点在某些需要频繁找父节点的情况下可以使用。
typedef int DataType;//数据类型
typedef struct BinaryTreeNode
{struct BinaryTreeNode* _parent;//父节点struct BinaryTreeNode* _left;//左孩子struct BinaryTreeNode* _right;//右孩子DataType _data;//数据
}BTNode;
二叉树的代码实现
有了前面的知识我们已经明白二叉树的结构是怎样的了那么我们可以考虑如何创建二叉树的节点其实也很简单和链表节点类似malloc一个新节点出来并存储数据就行了而二叉树节点的创建与链接我们一般用递归实现这里就不再赘述我们就直接手动连接。
#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.h
//二叉树结构
typedef int 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 fail);return NULL;}newnode-data x;newnode-left newnode-right NULL;return newnode;
}
//手动链接一颗二叉树
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;
}
二叉树的遍历
二叉树的遍历分为前序中序后序三种而这三种的区别就是根节点在前还是在后。 遍历顺序为左子树根节点右子树。 左根右因此是中序遍历。以此类推。 而我们可以使用递归非常简单的去实现这三种遍历因为树本身就是一种递归结构。
如果当前节点为空代表不需要再递下去了就return如果不为空代表可以继续递左右子树因此看遍历需求考虑先递再打印还是先打印再递。
//前序遍历 根 左 右
void PrevOrder(BTNode* bt)
{if (bt NULL){printf(N );return;}printf(%d , bt-data);PrevOrder(bt-left);PrevOrder(bt-right);
}
//中序遍历 左 根 右
void InOrder(BTNode* bt)
{if (bt NULL){printf(N );return;}PrevOrder(bt-left);printf(%d , bt-data);PrevOrder(bt-right);
}
//后序遍历 左 右 根
void PostOrder(BTNode* bt)
{if (bt NULL){printf(N );return;}PrevOrder(bt-left);PrevOrder(bt-right);printf(%d , bt-data);
}
一些简单常见的操作
对于一颗二叉树我们也许会求它的高度或结点个数这些该怎么做呢 对于求结点个数来说我们也可以使用递归思想分治思想一棵树的结点个数等于左子树节点数右子树节点数根结点因此sum left right 1对于这棵树的每一颗子树我们都可以这么想因此代码就显而易见了。求叶子结点个数也很简单只要一个树左右子树都为空则就是叶结点了在求结点个数的基础上改一改就行。 对于求高度来说我们也可以递归一棵树的高度为左右子树高度的最大值加上本身这一层。即h max(左子树高度右子树高度) 1。 //求结点个数
int BTreeSize(BTNode* bt)
{if (bt NULL) return 0;return BTreeSize(bt-left) BTreeSize(bt-right) 1;
}
//求叶结点个数
int BLeafSize(BTNode* bt)
{if (bt NULL)return 0;if (bt-left NULL bt-right NULL)return 1;return BLeafSize(bt-left) BLeafSize(bt-right);
}
//求树的高度
int BTreeHeight(BTNode* bt)
{if (bt NULL)return 0;int left BTreeHeight(bt-left);int right BTreeHeight(bt-right);return left right ? left 1 : right 1;
}
一些常见操作
求树的第k层的结点个数因为这个问题指定了求哪一层所以我们拿一个变量k来存储剩余层数当k减到1时代表就是第k层了。
查找值为x的结点也是用一个变量存储x如果当前结点的data前提是结点不为空为x就可以返回当前结点否则返回左子树右子树中递归查找结果不为空的那一个。
//求树第k层的结点个数
int BinaryTreeLevelKSize(BTNode* bt, int k)
{assert(k 0);if (k 1)return 1;if (bt NULL)return 0;return BinaryTreeLevelKSize(bt-left, k - 1) BinaryTreeLevelKSize(bt-right, k - 1);
}
//二叉树查找值为x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* r1 BTreeFind(root-left, x);if (r1) return r1;BTNode* r2 BTreeFind(root-right, x);if (r2) return r2;return NULL;//if (r1 NULL r2 NULL)// return NULL;//if (r1 NULL) return r2;//else return r1;
}
二叉树的基本知识点就差不多到这了接下来我们就可以调试代码了。
//求前中后序遍历并打印二叉树的结点/叶结点个数以及高度
int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);printf(%d\n, BTreeSize(root));printf(%d\n, BLeafSize(root));printf(%d\n, BTreeHeight(root));return 0;
}
当然为了避免内存泄漏记得要销毁二叉树噢。
//二叉树的结点空间释放
void BTreeDestroy(BTNode* bt)
{if(bt NULL) return;BTreeDestroy(bt-left);BTreeDestroy(bt-right);free(bt);
}
