二叉树的创建 先序 中序 后续 递归和非递归遍历

本文主要是介绍二叉树的创建 先序 中序 后续 递归和非递归遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <stack>using namespace std;int index = 0;//标记着数组的下标
typedef struct BiTree
{int data;BiTree *lchild;BiTree *rchild;
}*Tree;//创建二叉树,需要使用结构体指针 这样树的结构出了函数 还会保存状态
void createBT(Tree &root,int data[])
{int value = data[index++];if(value == -1){root = NULL;}else{root = new BiTree;root->data = value;createBT(root->lchild,data);createBT(root->rchild,data);}
}
//二叉树的后序遍历 非递归
/**
根据后序遍历的形式 左->右->根，若访问的当前节点的左右孩子为空 就输出其值，要是
访问的当前节点的前驱存在 存在着左右孩子 即访问左右孩子节点 输出值 并将当前节点
至为前驱节点 以便下次访问 若不满足这俩种情况，按照栈的顺序 依次压入右孩子 、左孩子。
*/
void PostOrder(Tree& root)
{BiTree* cur;BiTree* pre = NULL;stack<BiTree*> s;if(root == NULL)return;s.push(root);while(!s.empty()){cur = s.top();if((cur->lchild == NULL && cur->rchild == NULL) ||(pre != NULL &&(pre ==cur->lchild || pre == cur->rchild))){cout << cur->data << " ";s.pop();pre = cur;}else{if(cur->rchild!=NULL)s.push(cur->rchild);if(cur->lchild!=NULL)s.push(cur->lchild);}}cout << endl;
}//后序遍历递归的形式
void visit(Tree&);
void PostOrder_Digui(Tree &root)
{if(root == NULL)return;PostOrder_Digui(root->lchild);PostOrder_Digui(root->rchild);visit(root);
}void visit(Tree &root)
{cout << root->data <<" ";
}//二叉树的先序遍历 递归形式
void PreOrder(Tree& root)
{if(root == NULL)return;visit(root);PreOrder(root->lchild);PreOrder(root->rchild);
}
//先序非递归的形式：
void PreOrder_Fdigui(Tree &root)
{stack<BiTree*> s;if(root == NULL)return;while(root || !s.empty()){while(root){s.push(root);cout << root->data << " ";root = root->lchild;}root = s.top();root = root->rchild;s.pop();}
}
//二叉树的中序遍历 递归的形式
void Inorder_Digui(Tree& root)
{if(root == NULL)return;Inorder_Digui(root->lchild);visit(root);Inorder_Digui(root->rchild);
}
//二叉树中序遍历非递归
void Inorder(Tree &root)
{stack<BiTree*> s;if(root == NULL)return;while(root || !s.empty()){while(root){s.push(root);root = root->lchild;}root = s.top();cout << root->data << " ";root = root->rchild;s.pop();}
}int main()
{int data[] = {8,6,4,-1,-1,7,-1,-1,10,9,-1,-1,11,-1,-1};Tree tree;createBT(tree,data);cout<<"输出树的遍历形式："<<endl;PostOrder(tree);cout<<"后序递归形式：" << endl;PostOrder_Digui(tree);cout << endl;cout<<"先序遍历递归的形式："<<endl;PreOrder(tree);cout << endl;cout << "先序非递归的形式：" << endl;PreOrder_Fdigui(tree);out << endl;cout << "中序遍历递归：" << endl;Inorder_Digui(tree);cout << endl;cout << "二叉树的中序遍历非递归形式："<< endl;Inorder(tree);return 0;
}

这篇关于二叉树的创建 先序 中序 后续 递归和非递归遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---