首页 > 代码库 > 二叉树基础算法总结
二叉树基础算法总结
记录一些二叉树的基础算法
二叉树节点结构：
typedef struct TreeNode{ int val; struct TreeNode *left; struct TreeNode *right; }TreeNode,*Node;
1.遍历
前、中、后序递归遍历：
void pre_order_traversal(TreeNode *root){ if(root! = NULL){ visit(root); pre_order_traversal(root->left); pre_order_traversal(root->right); }}
void in_order_traversal(TreeNode *root){ if(root! = NULL){ pre_order_traversal(root->left); visit(root); pre_order_traversal(root->right); }}
void post_order_traversal(TreeNode *root){ if(root! = NULL){ pre_order_traversal(root->left); pre_order_traversal(root->right); visit(root); }}
前、中、后序非递归遍历：
void pre_order_traversal(TreeNode *root){ if(root==NULL)return; stack<TreeNode> stack; while(root!=NULL || !stack.empty()){ if(root){ visit(root); stack.push(root); root=root->left; }else{ root=stack.pop(); root=root->right; } }}
void in_order_traversal(TreeNode *root){ if(root==NULL)return; stack<TreeNode> stack; while(root!=NULL || !stack.empty()){ if(root){ stack.push(root); root=root->left; }else{ root=stack.pop(); visit(root); root=root->right; } }}
void post_order_traversal(TreeNode *root){ if(root==NULL)return; stack<TreeNode> stack; TreeNode *flag = NULL; while(root!=NULL || !stack.empty()){ if(root){ stack.push(root); root=root->left; }else{ root=stack.top(); if(root->right && root->right != flag){ root=root->right; }else{ root=stack.pop(); visit(root); flag=root; root=NULL; } } }}
层次遍历：
void level_order_traversal(TreeNode *root){ if(root == NULL)return; queue<TreeNode> queue; queue.push(root); while(!queue.empty()){ root = queue.pop(); visit(root); if(root->left){ queue.push(root->left); } if(root->right){ queue.push(root->right); } }}
二叉树基础算法总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。