二叉树非递归遍历

需要注意非递归遍历需要借助栈这个数据结构来完成先序步骤把结点 访问和压入栈。把指针指向左子结点。重复第1步直到没有左子结点为止。再从栈 顶部拿出结点, 把指针指向此结点的右子结点。重复第1步骤 直到栈空或没有结点。代码void PreOrder(struct TreeNode* root) { stack<TreeNode*> S; struct TreeNode* T = root; while (!S.empty()||T) { while (T) { cout << T->val << " "; S.push(T); T = T->left; } if (!S.empty()) { T = S.top(); S.pop(); T = T...

二叉树的性质和遍历

二叉树特征一个二叉树第i层的最大结点数为 2^i-1,当i>=1时深度为K的二叉树最大节结点总数为: (2^k)-1 ,当k>=1时二叉树遍历方法​ 先序 (根 --> 左子树-->右子树)​ 中序 (左子树 --> 根-->右子树)​ 后序 (左子树 --> 右子树-->根)​ 层次遍历 (从上到下、从左到右)序号关系当根节点 i>1时,子节点序号等于 左(i 2) 右(i 2)+1,而父节点的序号等于(i/2)取整存储结构代码typedef struct TreeNode { char val; /*左右节点*/ struct TreeNode *left; struct TreeNode *right; };二叉树遍历代码先序遍历void PreOrder(struct TreeNode* root) { if (root == NULL) { return; } printf("%c", root->...