首页 > 代码库 > 二叉树学习一：二叉树创建与遍历
二叉树学习一：二叉树创建与遍历
二叉树的遍历有三种方式：
1）先序遍历:若二叉树为空，则空操作；不为空，则先访问根结点，先序遍历左子树，先序遍历右子树。
2）后序遍历:若二叉树为空，则空操作；不为空，则中序遍历左子树，访问根结点，中序遍历右子树。
3）后序遍历:若二叉树为空，则空操作；不为空，则后序遍历左子树，后序遍历右子树，访问根结点。
例：
1）先序遍历结果为：ABDECF
2）中序遍历结果为：DBEAFC
3）后序遍历结果为：DEBFCA
二叉树输出的思想是将树转换成线性结构输出，一般采用递归方式，非递归方式是使用栈实现，C++递归实现如下：
1 #include<iostream> 2 using namespace std; 3 4 typedef struct BiTreeNode{ 5 char data; 6 BiTreeNode* pLchild; 7 BiTreeNode* pRchild; 8 }BiTreeNode, *BiTree; 9 10 //创建二叉树11 void CreateBiTree(BiTree &pTree){12 char ch;13 cin >> ch;14 if (ch == ‘*‘)15 {16 pTree = NULL;17 }18 else19 {20 pTree = new BiTreeNode;21 pTree->data =http://www.mamicode.com/ ch;22 CreateBiTree(pTree->pLchild);23 CreateBiTree(pTree->pRchild);24 }25 }26 27 //先序遍历二叉树28 void PreOrderTrav(BiTree &pTree){29 if (pTree != NULL)30 {31 cout << pTree->data << ‘\t‘;32 PreOrderTrav(pTree->pLchild);33 PreOrderTrav(pTree->pRchild);34 }35 }36 37 //中序遍历38 void InOrderTrav(BiTree &pTree){39 if (pTree != NULL)40 {41 InOrderTrav(pTree->pLchild);42 cout << pTree->data << ‘\t‘;43 InOrderTrav(pTree->pRchild);44 }45 }46 47 //后序遍历48 void PosOrderTrav(BiTree &pTree){49 if (pTree != NULL)50 {51 PosOrderTrav(pTree->pLchild);52 PosOrderTrav(pTree->pRchild);53 cout << pTree->data << ‘\t‘;54 }55 }56 57 void main()58 {59 BiTree pTree = NULL;60 CreateBiTree(pTree);61 cout << "先序遍历：" << endl;62 PreOrderTrav(pTree);63 cout << endl << "中序遍历：" << endl;64 InOrderTrav(pTree);65 cout << endl << "后序遍历：" << endl;66 PosOrderTrav(pTree);67 cout << endl;68 }
二叉树学习一：二叉树创建与遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。