二叉树遍历的第一&最后结点

vlambda
2021-04-22

二叉树遍历的第一&最后结点

根结点root。

中序遍历：

第一结点：根结点左走到底，不一定是叶结点

if (root) { struct BinaryTreeNode *mostLeft=root; while (mostLeft->left) { mostLeft=mostLeft->left; }}

最后结点：根结点右走到底，不一定是叶结点

if (root) { struct BinaryTeeNode *mostRight=root; while (mostRight->right) { mostRight=mostRight->right; }}

前序遍历：

第一结点：根

最后结点：必为叶结点，是后序逆序遍历的第一个叶结点

if (root) { struct BinaryTreeNode *child=root;  while (child->right || child->left) { while (child->right) child=child->right; if (child->left) child=child->left;    }}

后序遍历：

第一结点：必为叶结点，是前序遍历的第一个叶结点

if (root) { struct BinaryTreeNode *child=root;  while (child->left || child->right) { while (child->left) child=child->left; if (child->right) child=child->right;    } }