杭州网站设计公司哪家好,网页设计师工作职责,网络平面广告设计,天天新网站文章目录 前言构建二叉树前序遍历中序遍历后序遍历二叉树的结点个数二叉树的叶节点个数二叉树的高度二叉树第K层结点个数 前言
二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章#xff0c;小编将介绍二叉树的前序遍历、中序遍历、后序遍历#xff0c;求二叉树… 文章目录 前言构建二叉树前序遍历中序遍历后序遍历二叉树的结点个数二叉树的叶节点个数二叉树的高度二叉树第K层结点个数 前言
二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章小编将介绍二叉树的前序遍历、中序遍历、后序遍历求二叉树结点个数、叶节点个数、第K层结点个数、二叉树的深度。
构建二叉树
手搓二叉树的结构
小编简单构建一个二叉树的结构方便后面的测试
构建的方式比较简单在树的结构中有当前结点的数据、当前结点的左节点、右节点。除此之外还需要开辟结点。
有了 前面数据结构的学习小编认为手搓一个二叉树的结构相对来说简单一些
typedef int Tdatatype;typedef struct Tree
{Tdatatype data;struct Tree* left;struct Tree* right;
}Tree;Tree* BuyTree(Tdatatype x)
{Tree* node (Tree*)malloc(sizeof(Tree));if (node NULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}Tree* CreatTree()
{Tree* node1 BuyTree(1);Tree* node2 BuyTree(2);Tree* node3 BuyTree(3);Tree* node4 BuyTree(4);Tree* node5 BuyTree(5);Tree* node6 BuyTree(6);Tree* node7 BuyTree(7);node1-left node2;node1-right node4;node2-left node3;node2-right node7;node4-left node5;node4-right node6;return node1;
}前序遍历
若二叉树为空则操作为空 否则 1访问根节点 2先序遍历左子树 3先序遍历右子树
void PrevOrder(Tree* root)
{if (root NULL){printf(N );return;}PrevOrder(root-left);printf(%d , root-data);PrevOrder(root-right);
}中序遍历
若二叉树为空则操作为空 否则 1中序遍历左子树 2访问根节点 3中序遍历右子树
void InOrder(Tree* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}后序遍历
若二叉树为空则操作为空 否则 1后序遍历左子树 2后序遍历右子树 3访问根节点
void PostOrder(Tree* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}二叉树的结点个数
求二叉树的结点个数还是用到递归的思想即子问题分治还需要有结束条件
子问题分治左子树结点个数右子树结点个数1 返回条件根节点为空
int TreeSize(Tree* root)
{return root NULL ? 0 : TreeSize(root-right) TreeSize(root-right) 1;
}二叉树的叶节点个数
求二叉树叶节点个数依然是递归思想
子问题分治左子树叶子节点个数右子树叶子节点个数 返回条件根节点为空返回0是叶子节点返回1
int TreeLeaSize(Tree* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeLeaSize(root-left) TreeLeaSize(root-right);
}
二叉树的高度
子问题分治找左子树和右子树中高度较大的那一个并1 返回条件根节点为空返回0
int TreeHight(Tree* root)
{if (root NULL)return 0;int left TreeHight(root-left);int right TreeHight(root-right);return left right ? left 1 : right 1;
}
二叉树第K层结点个数
二叉树第k层的节点数左子树的第k-1层的节点数右子树第k-1层的节点数。
因为二叉树没有第0层是从第一层开始的所以k1时返回1。
int TreeLevelK(Tree* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return TreeLevelK(root-left, k - 1) TreeLevelK(root-right, k - 1);
}