06.02 二叉树遍历

根据根的访问顺序不同，根在前面被称为先序遍历（DLR），根在中间被称为中序遍历（LDR），根在最后被称为后历（LRD）。

A B D E C F G


A B C D E F G

D B E A F G C

B C D A F E J H I G

D E B G F C A

D C B F J I H G E A

A B C D E F G

A B E C F G D H J I

例如，已知二叉树的先序列ABDECFG和中序序列DBEAFGC，画这棵二叉树。

traverse.cpp

#include  #include //引入队列头文件 using namespace std;  typedef struct Bnode /*定义二叉树存储结构*/ {  char data;  struct Bnode* lchild, * rchild; }Bnode, * Btree;  void Createtree(Btree& T) /*创建二叉树函数*/ {  //按顺序输入二叉树结点的值(一个字符)，创建二叉链表示二叉树T  char ch;  cin >> ch;  if (ch == '#')   T = NULL;   ///递归结束，建空树  else {   T = new Bnode;   T->data = ch;     //生成根结点   Createtree(T->lchild); //递归创造左子树   Createtree(T->rchild); //递归创建右子树  } }  void preorder(Btree T)///先序遍历 {  if (T)  {   cout << T->data << "  ";   preorder(T->lchild);   preorder(T->rchild);  } }  void inorder(Btree T)///中序遍历 {  if (T)  {   inorder(T->lchild);   cout << T->data << "  ";   inorder(T->rchild);  } }  void posorder(Btree T)///后序遍历 {  if (T)  {   posorder(T->lchild);   posorder(T->rchild);   cout << T->data << "  ";  } }  bool Leveltraverse(Btree T) {  Btree p;  if (!T)   return false;  queueQ; ///创建一个普通(先进先出)，存储指针类型  Q.push(T); ///根指针入队  while (!Q.empty()) //如果队列不空  {   p = Q.front()livenode   Q.pop(); ///队头元素出队   cout << p->data << "  ";   if (p->lchild)    Q.push(p->lchild); ///左孩子指针入队   if (p->rchild)    Q.push(p->rchild); ///右孩子指针入队  }  return true; }  int main() {  Btree mytree;  cout << "二叉树输入二叉树结点值(儿童空时输入#)，创造一棵二叉树" << endl;  Createtree(mytree);//创造二叉树  cout << endl;  cout << "二叉树的先序遍历结果：" << endl;  preorder(mytree);//先序遍历二叉树  cout << endl;  cout << "二叉树中序遍历结果：" << endl;  inorder(mytree);//中序遍历二叉树  cout << endl;  cout << "二叉树后序遍历结果：" << endl;  posorder(mytree);//后序遍历二叉树  cout << endl;  cout << "二叉树层次遍历结果：" << endl;  Leveltraverse(mytree);///层次遍历二叉树  return 0; } 

PreinCreateBitree.cpp

#include  using namespace std; typedef struct node {  char data;  struct node* lchild, * rchild; }BiTNode, * BiTree;  BiTree pre_mid_createBiTree(char* pre, char* mid, int len) /// {  if (len == 0)   return NULL;  char ch = pre[0];  ////在先序中找到第一个结点  int index = 0;  while (mid[index] != ch)///在中序中找到的根结点的左边是结点的左子树，右边是右子树  {   index  ;  }  BiTree T = new BiTNode;//创建根结点  T->data = ch;  T->lchild = pre_mid_createBiTree(pre   1, mid, index);//建左子树  T->rchild = pre_mid_createBiTree(pre   index   1, mid   index   1, len - index - 1)///建立右子树  return T; }  BiTree pro_mid_createBiTree(char* last, char* mid, int len)/// {  if (len == 0)   return NULL;  char ch = last[len - 1]; ///获得后序遍历顺序的最后一个结点  int index = 0；///在中序序列中找到根结点，并用index记录长度  while (mid[index] != ch)///在中序中找到根结点，左边是结点的左子树，右边是右子树   index  ;  BiTree T = new BiTNode;//创建根结点  T->data = ch;  T->lchild = pro_mid_createBiTree(last, mid, index);//建左子树  T->rchild = pro_mid_createBiTree(last   index, mid   index   1, len - index - 1)///建立右子树  return T; }  void pre_order(BiTree T)// {  if (T)  {   cout << T->data;   pre_order(T->lchild);   pre_order(T->rchild);  } }  void pro_order(BiTree T)///后序递归遍历二叉树 {  if (T)  {   pro_order(T->lchild);   pro_order(T->rchild);   cout << T->data;  } } int main() {  BiTree T;  int n;  char pre[100], mid[100], last[100];  cout << "1. 二叉树按顺序恢复\n";  cout << "2. 二叉树按顺序恢复\n";  cout << "0. 退出\n";  int choose = -1;  while (choose != 0)  {   cout << "请选择:";   cin >> choose;    switch (choose)   {   case 1://前序中序还原二叉树    cout << "请输入结点数：" << endl;    cin >> n;    cout << "请输入前序列：" << endl;    for (int i = 0; i < n; i  )     cin >> pre[i];    cout << "请输入中序列：" << endl;    for (int i = 0; i < n; i  )     cin >> mid[i];    T = pre_mid_createBiTree(pre, mid, n);    cout << endl;    cout << "二叉树恢复成功，输出后续序列：" << endl;    pro_oder(T);
			cout << endl << endl;
			break;
		case 2://后序中序还原二叉树
			cout << "请输入结点的个数:" << endl;
			cin >> n;
			cout << "请输入后序序列:" << endl;
			for (int i = 0; i < n; i++)
				cin >> last[i];
			cout << "请输入中序序列:" << endl;
			for (int i = 0; i < n; i++)
				cin >> mid[i];
			T = pro_mid_createBiTree(last, mid, n);
			cout << endl;
			cout << "二叉树还原成功，输出其先序序列:" << endl;
			pre_order(T);
			cout << endl << endl;
			break;
		}
	}
	return 0;
}