数据结构-二叉树-链式

一、链式二叉树的结构

typedef int BTNodeDataType;
typedef struct BTNode
{
BTNodeDataType data;
struct BTNode* left;
struct BTNode* right;
}BTNode;

二叉树的前中后序遍历

前序：根左右

中序：左根右

后序：左右根

void PreOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
printf("%d", root->data);
PreOrder(root->left);
PreOrder(root->right);
}

void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}

InOrder(root->left);
printf("%d", root->data);
InOrder(root->right);
}

void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d", root->data);
}

递归展开图

前序遍历

左右子树的递归使用同一块栈帧。因为在调用右子树的递归之前，左子树的栈帧就已经还给操作系统了。

中序遍历

二、分治

首先我们可以使用分治的思想来思考一个问题，二叉树的节点个数怎么求。我们可以这样思考，先求出左右子树的节点个数，然后返回左右子树节点的数量+根的数量。其实这就是一个分治的思想。

int TreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftsize = TreeSize(root->left);
int rightsize = TreeSize(root->right);
return leftsize + rightsize + 1;
}

我们可以再来举一个例子来思考这个问题，学校的管理制度

比如校长要统计人数，我们就可以把任务分发给院长，然后院长在找到系主任，系主任找到班长，班长找舍长，最后由舍长上报人数。班长开始上报给系主任，系主任报给院长，院长报给校长。这就是分治的思想。

求树的高度，也可以应用分治的思想。

int TreeHeight(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeight(root->left);
int right = TreeHeight(root->right);

return left > right ? left + 1 : right + 1;
}

不可以这样写，这个写法相当于上面的班长，系主任，院长，校长都是只有七秒记忆的人，导致舍长要报好多遍。

会造成栈溢出的结果。

求第K层的节点个数

根的第k层 = 左子树的第k-1层个数 + 右子树的第k-1层个数。

int TreeKLevel(BTNode* root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
int left = TreeKLevel(root->left, k - 1);
int right = TreeKLevel(root->right, k - 1);
return left + right;
}

原文地址：https://blog.csdn.net/m0_67635008/article/details/138153344

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！