C++ 实现二叉树的三种遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++ 实现二叉树的三种遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2658字，纯文字阅读大概需要4分钟。

内容图文

二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。二又树的特点是每个结点最多有两个子女，分别称为该结点的左子女和右子女。在二又树中不存在度大于2的结点，并且二又树的子树有左、右之分，其子树的次序不能颠倒。二又树是分支数最大不超过2的有根有序树。

 

先序遍历：

 

 

中序遍历：

 

代码：

构造如下的一个二叉树：G(E(B(A,),C),F(,D))

 

 1 #include <iostream>
 2 
 3 //结点类型
 4 template <typename T>
 5 struct BinTreeNode
 6 {
 7     T data;                                                                                                        //结点中存储的数据
 8     BinTreeNode<T> *leftChild, *rightChild;                                                                        //左子树和右子树
 9     BinTreeNode() : leftChild(NULL), rightChild(NULL) {}                                                           //无参构造函数
10     BinTreeNode(T x, BinTreeNode<T> *l = NULL, BinTreeNode<T> *r = NULL) : data(x), leftChild(l), rightChild(r) {} //带默认值的有参构造参数
11 };
12 
13 //先序遍历  PreOrder
14 template<typename T>
15 void PreOrder(BinTreeNode<T>* root){
16     if (root != NULL){
17         std::cout << root->data << std::endl;
18         PreOrder(root->leftChild);
19         PreOrder(root->rightChild);
20     }
21 }
22 
23 //中序遍历  InOrder
24 template<typename T>
25 void InOrder(BinTreeNode<T>* root){
26     if (root != NULL){
27         InOrder(root->leftChild);
28         std::cout << root->data << std::endl;
29         InOrder(root->rightChild);
30     }
31 }
32 
33 //后序遍历  PostOrder
34 template<typename T>
35 void PostOrder(BinTreeNode<T>* root){
36     if (root != NULL){
37         PostOrder(root->leftChild);
38         PostOrder(root->rightChild);
39         std::cout << root->data << std::endl;
40     }
41 }
42 
43 int main()
44 {
45     //构建二叉树
46     BinTreeNode<char>* btA = new BinTreeNode<char>('A');
47     BinTreeNode<char>* btB = new BinTreeNode<char>('B', btA, NULL);
48     BinTreeNode<char>* btC = new BinTreeNode<char>('C');
49     BinTreeNode<char>* btD = new BinTreeNode<char>('D');
50     BinTreeNode<char>* btE = new BinTreeNode<char>('E', btB, btC);
51     BinTreeNode<char>* btF = new BinTreeNode<char>('F', NULL, btD);
52     BinTreeNode<char>* btG = new BinTreeNode<char>('G', btE, btF);
53 
54     //执行先序遍历
55     std::cout << "先序遍历：" << std::endl;
56     PreOrder(btG);
57 
58     //执行中序遍历
59     std::cout << "中序遍历：" << std::endl;
60     InOrder(btG);
61 
62     //执行后序遍历
63     std::cout << "后序遍历：" << std::endl;
64     PostOrder(btG);
65 }

输出结果：

先序遍历：
G
E
B
A
C
F
D
中序遍历：
A
B
E
C
G
F
D
后序遍历：
A
B
C
E
D
F
G

 

内容总结

以上是互联网集市为您收集整理的C++ 实现二叉树的三种遍历全部内容，希望文章能够帮你解决C++ 实现二叉树的三种遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---