景安网络网站建设,数字展馆公司,个人网站可以做点什么,成都网多多【二叉树入门指南】链式结构的实现 一、前置说明二、二叉树的遍历2.1前序遍历2.2中序遍历2.3 后序遍历 三、以前序遍历为例#xff0c;递归图解四、层序遍历五、节点个数以及高度等5.1 二叉树节点个数5.2二叉树叶子节点个数5.3 二叉树第k层节点个数5.4 二叉树查找值为x的节点5… 【二叉树入门指南】链式结构的实现 一、前置说明二、二叉树的遍历2.1前序遍历2.2中序遍历2.3 后序遍历 三、以前序遍历为例递归图解四、层序遍历五、节点个数以及高度等5.1 二叉树节点个数5.2二叉树叶子节点个数5.3 二叉树第k层节点个数5.4 二叉树查找值为x的节点5.5 二叉树的高度 六、二叉树的创建和销毁6.1 构建二叉树6.2 二叉树的销毁6.3 判断二叉树是否为完全二叉树 一、前置说明
其他数据结构不同二叉树的增删查改接口实现的意义不大后续搜索树的增删查改才有意义。普通初阶二叉树更重要的是学习控制结构为后续的AVL树、红黑树等高级数据结构打下基础。同时大部分OJ题也出在此处。 二、二叉树的遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问顺序根节点—左子树—右子树中序遍历(Inorder Traversal)——访问顺序左子树—根节点—右子树后序遍历(Postorder Traversal)——访问顺序左子树—右子树—根节点 2.1前序遍历
【代码思路】:
若二叉树为空则直接返回。访问根节点。递归遍历左子树即调用前序遍历函数传入左子树的根节点。递归遍历右子树即调用前序遍历函数传入右子树的根节点
代码
void PrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}2.2中序遍历
【代码思路】
首先判断二叉树是否为空若为空则直接返回。对当前节点的左子树进行中序遍历即递归调用中序遍历函数。访问当前节点的值。对当前节点的右子树进行中序遍历即递归调用中序遍历函数。
代码
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}2.3 后序遍历
【代码思路】
判断当前节点是否为空若为空则返回。递归遍历当前节点的左子树。递归遍历当前节点的右子树。访问当前节点。
代码
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}三、以前序遍历为例递归图解
前序遍历递归图解 上述三种遍历结果
前序遍历结果1 2 3 4 5 6中序遍历结果3 2 1 5 4 6后序遍历结果3 2 5 6 4 1 四、层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 【代码思路】核心思想上一层出时带下一层进队列即根节点出栈时根节点的孩子节点入栈
首先将根节点入栈。循环进行以下操作直到栈为空。 。弹出栈顶元素并将其值输出 。如果该节点有右子节点则将右子节点入栈。 。 如果该节点有左子节点则将左子节点入栈
栈相关代码自行查看栈和队列代码实现
代码
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)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);
}五、节点个数以及高度等
5.1 二叉树节点个数
【代码思路】
如果二叉树为空则节点个数为0。否则节点个数等于根节点的个数加上左子树的节点个数和右子树的节点个数。递归计算左子树的节点个数。递归计算右子树的节点个数。返回根节点个数加上左子树和右子树的节点个数。
代码
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}5.2二叉树叶子节点个数
【代码思路】
判断根节点是否为空若为空则返回0。判断根节点的左右子树是否为空若都为空则表示根节点是叶子节点返回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);
}5.3 二叉树第k层节点个数
【代码思路】
判断二叉树是否为空如果是则返回0。判断k是否等于1如果是则返回1表示当前层为第k层只有一个节点。如果以上条件都不满足则递归计算二叉树的左子树和右子树的第k-1层节点个数然后将左右子树的第k-1层节点个数相加即为二叉树第k层节点个数。
代码
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}5.4 二叉树查找值为x的节点
【代码思路】
如果当前节点为空则返回空。如果当前节点的值等于x则返回当前节点。否则递归查找左子树如果找到则返回左子树中的节点。否则递归查找右子树如果找到则返回右子树中的节点。
代码
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTreeFind(root-right, x);if (ret2)return ret2;return NULL;
}5.5 二叉树的高度
【代码思路】
如果树为空树则高度为0。如果树不为空树则高度为左子树的高度和右子树的高度中的较大值加1。递归地计算左子树和右子树的高度并取较大值。返回左子树和右子树高度的较大值加1。
代码
int BinaryTreeHeight(BTNode* root)
{if (root NULL){return 0;}int LeftHeight BinaryTreeHeight(root-left);int RightHeight BinaryTreeHeight(root-right);return LeftHeight RightHeight ? LeftHeight 1 : RightHeight 1;
}六、二叉树的创建和销毁
6.1 构建二叉树
Tips 构建二叉树的方式有很多 这里我们通过前序遍组ABD##E#H##CF##G##构建二叉树。‘#’表示空树 【代码思路】
如果节点为“#”表示空返回空。遍历创建左子树并和根节点链接。遍历创建右子树并和根节点链接。返回根节点
代码
typedef int BTDataType;
typedef struct BinaryTreeNode//结构体类型
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//创建节点
BTNode* BuyNode(BTDataType x)
{BTNode* Node (BTNode*)malloc(sizeof(BTNode));if (Node NULL){perror(malloc fail);exit(-1);}Node-data x;Node-left NULL;Node-right NULL;return Node;
}//先序创建二叉树
BTNode* createrroot(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(a[*pi]);(*pi);root-left createrroot(a, pi);root-right createrroot(a, pi);return root;
}6.2 二叉树的销毁
【代码思路】
从根节点开始递归地销毁左子树。从根节点开始递归地销毁右子树。将根节点从内存中删除。
代码
void BinaryTreeDestroy(BTNode* root)
{if (root NULL)return;BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root);
}6.3 判断二叉树是否为完全二叉树
博主数据结构初阶是用C语言来实现的所以此处直接栈代码从博主代码仓库中拷贝过来的读者可以用其他语言来实现大同小异
【代码思路】
遍历二叉树使用层次遍历的方式从根节点开始逐层遍历每个节点。当遇到第一颗空树时停止遍历。从第一颗空树开始后续节点如果有非空就不是完全二叉树否则为完全二叉树。
栈相关代码自行查看栈和队列代码实现 代码
int BinaryTreeComplete(BTNode* root)
{Que q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//遇空就跳过if (frontNULL){break;}QueuePush(q, root-left);QueuePush(q, root-right);}//检查后续节点是否有非空//有非空就不是完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}【数据结构入门指南】二叉树顺序结构: 堆及实现全程配图非常经典
