亚马逊网站建设评述,杭州公司注销流程及费用,公司部门管理制度,做网站那个公司前言#xff1a;我们前面已经了解了二叉树的一些概念#xff0c;那么我们今天就来了解下二叉树的遍历实现和一些性质。 二叉树的遍历方式有三种#xff1a;前序#xff0c;中序#xff0c;后序。 前序#xff1a;先根节点#xff0c;再左子树#xff0c;最后右子树。 中… 前言我们前面已经了解了二叉树的一些概念那么我们今天就来了解下二叉树的遍历实现和一些性质。 二叉树的遍历方式有三种前序中序后序。 前序先根节点再左子树最后右子树。 中序先左子树再根节点最后右子树。 后序先左子树再右子树最后根节点。 前序遍历
void PrevOrder(TreeNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}如果我们的根节点为空就返回空不为空就递归左子树如果左子树为空就返回递归访问右子树。 中序遍历
void InOrder(TreeNode* root)
{if (root NULL){printf(N);return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}先访问遍历左子树再根节点最后在访问右子树。 后序遍历
void Tailorder(TreeNode* root)
{if (root NULL){printf(N);return;}Tailorder(root-left);Tailorder(root-right);printf(%d, root-data);
}先遍历左子树再遍历右子树最后在根节点。 求二叉树节点个数
int TreeSize(TreeNode* root)
{return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
}我们递归实现左子树的节点个数加上右子树的节点个数再加上根节点的个数就是节点的总个数。 求叶子结点的个数
int TreeLeafSize(TreeNode* root)
{// 空 返回0if (root NULL)return 0;// 不是空是叶子 返回1if (root-left NULL root-right NULL)return 1;// 不是空 也不是叶子 分治左右子树叶子之和return TreeLeafSize(root-left) TreeLeafSize(root-right);
}
求二叉树的高度
int TreeHeight(TreeNode* root)
{if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}因为我们的递归结合上三目操作符会使得非常的复杂所以我们用一个数据来保存左右子树的高度我们的二叉树的高度为左右子树较高的那个子树加上1所以我们返回的是左右子树高度更高的再加上1就是二叉树的高度。 我们的代码还可以进行改进我们C语言的fmax函数该函数的作用是比较两个数得到较大的那一个数
int TreeHeight(TreeNode* root)
{if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
}
求二叉树第k层节点个数
int TreeLevelK(TreeNode* 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);
}第k层的节点等于第k-1层的节点数相加。 现在我们要求第三层的节点数相当于我们返回它的第二层而我们的第二层节点数要返回我们的第一层节点数我们的左子树返回一个节点右子树返回两个节点所以就是三个节点。 如果对大家有所帮助的话就支持一下吧
