一、树的遍历算法
树的创建
struct BinaryTreeNode { int val; BinaryTreeNode* left; BinaryTreeNode* right; }; void creat_tree(BinaryTreeNode* &T) { char a; cin>>a; if(a=='#') T=NULL; else { T=new BinaryTreeNode; if(T==NULL) return; T->val=a-'0'; creat_tree(T->left); creat_tree(T->right); } }
前序遍历
void pre_trave1(BinaryTreeNode* T) { if(T==NULL) return; else { cout<<T->val<<" "; pre_trave1(T->left); pre_trave1(T->right); } } //非递归实现 void pre_trave2(BinaryTreeNode* T) { if(T==NULL) return; stack<BinaryTreeNode*> st_T; while(1) { cout<<T->val; while(T) { if(T->right) st_T.push(T->right); //先遍历左子树，遇到右子树入栈 if(T->left) cout<<T->left->val; T=T->left; } if(!st_T.empty()) { T=st_T.top(); st_T.pop(); } else break; } }
中序遍历
void mid_trave1(BinaryTreeNode* T) { if(T==NULL) return; else { mid_trave1(T->left); cout<<T->val<<" "; mid_trave1(T->right); } } //非递归实现 void mid_trave2(BinaryTreeNode* T) { if(T==NULL) return; stack<BinaryTreeNode*> st_T; while(1) { while(T) { st_T.push(T); //逢左子树入栈 T=T->left; } if(!st_T.empty()) { T=st_T.top(); st_T.pop(); cout<<T->val<<" "; T=T->right; } else break; } }
后序遍历
//递归实现 void post_trave1(BinaryTreeNode* T) { if(T==NULL) return; else { post_trave1(T->left); post_trave1(T->right); cout<<T->val<<" "; } } //非递归实现（破坏树的原结构） void post_trave2(BinaryTreeNode* T) { if(T==NULL) return; stack<BinaryTreeNode*> st_T; while(1) { while(T) { st_T.push(T); T=T->left; } if(!st_T.empty()) { T=st_T.top(); if(T->right) //第一次经过根节点后打断与右子树的联系 { BinaryTreeNode* temp=T->right; T->right=NULL; T=temp; } else { st_T.pop(); cout<<T->val<<" "; T=NULL; } } else break; } } //非递归实现 void post_trave3(BinaryTreeNode* T) { if(T==NULL) return; stack<BinaryTreeNode*> st_T; BinaryTreeNode* pre; while(1) { while(T) { st_T.push(T); T=T->left; } if(!st_T.empty()) { T=st_T.top(); if(T->right&&(pre!=T->right)) //当存在右子树且右子树没被打印时，先打印右子树 { T=T->right; } else { pre=T; st_T.pop(); cout<<T->val<<" "; T=NULL; } } else break; } }
层序遍历
void level_trave(BinaryTreeNode* T) { if(!T) return; queue<BinaryTreeNode*> qu_T; qu_T.push(T); while(!qu_T.empty()) { BinaryTreeNode* temp=qu_T.front(); qu_T.pop(); if(temp->left!=NULL) qu_T.push(temp->left); if(temp->right!=NULL) qu_T.push(temp->right); cout<<temp->val<<" "; } }
二、重建二叉树
问题描述：输入二叉树的前序与中序，输出重建的二叉树。
//很明显前序的首位是根结点，再从中序中查找根结点，就可以分为左右两个子树，依次递归可得。
//递归条件和边界一定要分析清楚，不然很容易出错
BinaryTreeNode* core_rebuild(vector<int>&,int,int,vector<int>&,int,int); BinaryTreeNode* rebulid_bT(vector<int>& pre,vector<int>& mid,int length) { if(!pre.size()||!mid.size()||length<=0) { return NULL; } return core_rebuild(pre,0,length-1,mid,0,length-1); } BinaryTreeNode* core_rebuild(vector<int>& pre,int pre_start,int pre_end,vector<int>& mid,int mid_start,int mid_end) { BinaryTreeNode* root=new BinaryTreeNode; root->val=pre[pre_start]; root->left=NULL; root->right=NULL; if(pre_start==pre_end) { return root; } int temp=mid_start; while(temp<=mid_end&&pre[pre_start]!=mid[temp]) temp++; int count=temp - mid_start; if(count>0) //temp不处于开始位置，则有左子树 root->left=core_rebuild(pre,pre_start+1,pre_start+count,mid,mid_start,temp-1); if(temp!=mid_end) //temp不处于终止位置，则有右子树 root->right=core_rebuild(pre,pre_start+count+1,pre_end,mid,temp+1,mid_end); return root; }
问题描述：输入二叉树的后序与中序，输出重建的二叉树。
BinaryTreeNode* core_rebuild2(vector<int>&,int,int,vector<int>&,int,int); BinaryTreeNode* rebulid_bT(vector<int>& pre,vector<int>& mid,int length) { if(!pre.size()||!mid.size()||length<=0) { return NULL; } return core_rebuild2(pre,0,length-1,mid,0,length-1); } BinaryTreeNode* core_rebuild2(vector<int>& post,int post_start,int post_end,vector<int>& mid,int mid_start,int mid_end) { BinaryTreeNode* root=new BinaryTreeNode; root->val=post[post_end]; root->left=NULL; root->right=NULL; if(post_start==post_end) { return root; } int temp=mid_start; while(post[post_end]!=mid[temp]) temp++; int count=temp-mid_start; if(count>0) root->left=core_rebuild2(post,post_start,post_start+count-1,mid,mid_start,temp-1); if(temp<mid_end) root->right=core_rebuild2(post,post_start+count,post_end-1,mid,temp+1,mid_end); return root; }