首页 > 代码库 > 二叉树的构造和遍历——递归实现
二叉树的构造和遍历——递归实现
一、二叉树的定义：
二叉树是每个结点最多有两个子树的有序树。二叉树常被用于实现二叉查找树。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于2。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。
二、二叉树与树的区别：
二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二 叉树有两个主要差别：
1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
三、二叉树的遍历;
二叉树的遍历分为先序遍历、中序遍历和后序遍历二叉树三种。
“遍历”是二叉树各种操作的基础，可以再遍历的过程中对结点进行各种操作，例如求结点的双亲、求结点的孩子结点、求二叉树的深度等操作都是建立在二叉树遍历的基础上，因此必须掌握二叉树的各种遍历过程，并能灵活运用一解决各种问题。
四、二叉树的构造和递归遍历实现代码如下：
View Code
1 #include <iostream> 2 #include <string> 3 #include <assert.h> 4 #include <stdlib.h> 5 #include <time.h> 6 using namespace std; 7 const int N =10; 8 9 typedef struct node //二叉树的数据结构10 {11 int data_;12 struct node* left_;13 struct node* right_;14 }BTree, *pBTree;15 16 void Create_Btree_with_arr(pBTree &T, int *arr, int begin, int end)//len俄日数组的长度，也是树的结点数17 {18 if(begin > end)19 return;20 21 int mid = (begin + end)/2;22 if( T == NULL)23 {24 T =(pBTree)malloc(sizeof(BTree)); //申请空间25 arr[mid] = rand()%100;26 cout<< arr[mid] <<" ";27 T->data_ = arr[mid]; //数值随机化28 T->left_ = NULL;29 T->right_ = NULL;30 }31 Create_Btree_with_arr(T->left_, arr, begin, mid-1);//左边(不包括T)32 Create_Btree_with_arr(T->right_, arr, mid+1, end); //右边(不包括T)33 }34 35 void Pre_Traversal(pBTree T) //前序遍历36 {37 if( T != NULL)38 {39 cout << T->data_ <<" ";40 Pre_Traversal( T->left_);41 Pre_Traversal( T->right_);42 }43 }44 45 void InOrder_Traversal( pBTree T)//中序遍历46 {47 if( T == NULL)48 return;49 InOrder_Traversal(T->left_);50 cout << T->data_ <<" ";51 InOrder_Traversal(T->right_);52 }53 54 void PostOrder_Traversal( pBTree T) //后续遍历 ‘55 {56 57 if( T != NULL)58 {59 PostOrder_Traversal( T->left_);60 PostOrder_Traversal( T->right_);61 cout << T->data_ <<" ";62 } 63 }64 65 void DestructBTree( pBTree &T) //二叉树的销毁66 {67 if( T == NULL)68 return;69 70 DestructBTree( T->left_);71 DestructBTree( T->right_);72 free(T); //free之后的指针成为了野指针，内容并不为空73 T = NULL;//置空74 }75 76 int main(int argc, char const *argv[])77 {78 srand(time(NULL));79 int arr[N]= {0};80 81 pBTree T =NULL;82 Create_Btree_with_arr(T, arr, 0,N-1);83 cout << endl;84 85 Pre_Traversal(T);86 cout << endl;87 88 InOrder_Traversal(T);89 cout << endl;90 91 PostOrder_Traversal(T);92 cout << endl;93 94 DestructBTree(T);95 cout <<"Free Over" << endl;96 assert( T == NULL); //验证 T 是否真的被释放97 return 0;98 }
完毕。
二叉树的构造和遍历——递归实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。