首页 > 代码库 > 算法之二叉树各种遍历
算法之二叉树各种遍历
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
1 //二叉树结点 2 typedef struct BiTNode{ 3 //数据 4 char data; 5 //左右孩子指针 6 struct BiTNode *lchild,*rchild; 7 }BiTNode,*BiTree;
二叉树的创建：
通过读入一个字符串，建立二叉树的算法如下：
1 //按先序序列创建二叉树 2 int CreateBiTree(BiTree &T){ 3 char data; 4 //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 5 scanf("%c",&data); 6 if(data =http://www.mamicode.com/= ‘#‘){ 7 T = NULL; 8 } 9 else{ 10 T = (BiTree)malloc(sizeof(BiTNode)); 11 //生成根结点 12 T->data =http://www.mamicode.com/ data; 13 //构造左子树 14 CreateBiTree(T->lchild); 15 //构造右子树 16 CreateBiTree(T->rchild); 17 } 18 return 0; 19 }
二叉树的遍历：
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
递归算法：
1 //输出 2 void Visit(BiTree T){ 3 if(T->data != ‘#‘){ 4 printf("%c ",T->data); 5 } 6 } 7 //先序遍历 8 void PreOrder(BiTree T){ 9 if(T != NULL){ 10 //访问根节点 11 Visit(T); 12 //访问左子结点 13 PreOrder(T->lchild); 14 //访问右子结点 15 PreOrder(T->rchild); 16 } 17 } 18 //中序遍历 19 void InOrder(BiTree T){ 20 if(T != NULL){ 21 //访问左子结点 22 InOrder(T->lchild); 23 //访问根节点 24 Visit(T); 25 //访问右子结点 26 InOrder(T->rchild); 27 } 28 } 29 //后序遍历 30 void PostOrder(BiTree T){ 31 if(T != NULL){ 32 //访问左子结点 33 PostOrder(T->lchild); 34 //访问右子结点 35 PostOrder(T->rchild); 36 //访问根节点 37 Visit(T); 38 } 39 }
非递归算法：
<1>先序遍历：
【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
1 /* 先序遍历(非递归) 2 思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 3 */ 4 void PreOrder2(BiTree T){ 5 stack<BiTree> stack; 6 //p是遍历指针 7 BiTree p = T; 8 //栈不空或者p不空时循环 9 while(p || !stack.empty()){ 10 if(p != NULL){ 11 //存入栈中 12 stack.push(p); 13 //访问根节点 14 printf("%c ",p->data); 15 //遍历左子树 16 p = p->lchild; 17 } 18 else{ 19 //退栈 20 p = stack.top(); 21 stack.pop(); 22 //访问右子树 23 p = p->rchild; 24 } 25 }//while 26 }
<2>中序遍历
【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
1 void InOrder2(BiTree T){ 2 stack<BiTree> stack; 3 //p是遍历指针 4 BiTree p = T; 5 //栈不空或者p不空时循环 6 while(p || !stack.empty()){ 7 if(p != NULL){ 8 //存入栈中 9 stack.push(p); 10 //遍历左子树 11 p = p->lchild; 12 } 13 else{ 14 //退栈，访问根节点 15 p = stack.top(); 16 printf("%c ",p->data); 17 stack.pop(); 18 //访问右子树 19 p = p->rchild; 20 } 21 }//while 22 }
<3>后序遍历
【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
1 //后序遍历(非递归) 2 typedef struct BiTNodePost{ 3 BiTree biTree; 4 char tag; 5 }BiTNodePost,*BiTreePost; 6 7 void PostOrder2(BiTree T){ 8 stack<BiTreePost> stack; 9 //p是遍历指针 10 BiTree p = T; 11 BiTreePost BT; 12 //栈不空或者p不空时循环 13 while(p != NULL || !stack.empty()){ 14 //遍历左子树 15 while(p != NULL){ 16 BT = (BiTreePost)malloc(sizeof(BiTNodePost)); 17 BT->biTree = p; 18 //访问过左子树 19 BT->tag = ‘L‘; 20 stack.push(BT); 21 p = p->lchild; 22 } 23 //左右子树访问完毕访问根节点 24 while(!stack.empty() && (stack.top())->tag == ‘R‘){ 25 BT = stack.top(); 26 //退栈 27 stack.pop(); 28 BT->biTree; 29 printf("%c ",BT->biTree->data); 30 } 31 //遍历右子树 32 if(!stack.empty()){ 33 BT = stack.top(); 34 //访问过右子树 35 BT->tag = ‘R‘; 36 p = BT->biTree; 37 p = p->rchild; 38 } 39 }//while 40 }
<4>层次遍历
【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。
1 //层次遍历 2 void LevelOrder(BiTree T){ 3 BiTree p = T; 4 //队列 5 queue<BiTree> queue; 6 //根节点入队 7 queue.push(p); 8 //队列不空循环 9 while(!queue.empty()){ 10 //对头元素出队 11 p = queue.front(); 12 //访问p指向的结点 13 printf("%c ",p->data); 14 //退出队列 15 queue.pop(); 16 //左子树不空，将左子树入队 17 if(p->lchild != NULL){ 18 queue.push(p->lchild); 19 } 20 //右子树不空，将右子树入队 21 if(p->rchild != NULL){ 22 queue.push(p->rchild); 23 } 24 } 25 }
测试用例：
输入：
ABC##DE#G##F###
输出：
代码：
1 #include<iostream> 2 #include<stack> 3 #include<queue> 4 #include<cstdio> 5 #include<cstdlib> 6 using namespace std; 7 8 //二叉树结点 9 typedef struct BiTNode{ 10 //数据 11 char data; 12 //左右孩子指针 13 struct BiTNode *lchild,*rchild; 14 }BiTNode,*BiTree; 15 16 //按先序序列创建二叉树 17 int CreateBiTree(BiTree &T){ 18 char data; 19 //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 20 scanf("%c",&data); 21 if(data =http://www.mamicode.com/= ‘#‘){ 22 T = NULL; 23 } 24 else{ 25 T = (BiTree)malloc(sizeof(BiTNode)); 26 //生成根结点 27 T->data =http://www.mamicode.com/ data; 28 //构造左子树 29 CreateBiTree(T->lchild); 30 //构造右子树 31 CreateBiTree(T->rchild); 32 } 33 return 0; 34 } 35 //输出 36 void Visit(BiTree T){ 37 if(T->data != ‘#‘){ 38 printf("%c ",T->data); 39 } 40 } 41 //先序遍历 42 void PreOrder(BiTree T){ 43 if(T != NULL){ 44 //访问根节点 45 Visit(T); 46 //访问左子结点 47 PreOrder(T->lchild); 48 //访问右子结点 49 PreOrder(T->rchild); 50 } 51 } 52 //中序遍历 53 void InOrder(BiTree T){ 54 if(T != NULL){ 55 //访问左子结点 56 InOrder(T->lchild); 57 //访问根节点 58 Visit(T); 59 //访问右子结点 60 InOrder(T->rchild); 61 } 62 } 63 //后序遍历 64 void PostOrder(BiTree T){ 65 if(T != NULL){ 66 //访问左子结点 67 PostOrder(T->lchild); 68 //访问右子结点 69 PostOrder(T->rchild); 70 //访问根节点 71 Visit(T); 72 } 73 } 74 /* 先序遍历(非递归) 75 思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 76 */ 77 void PreOrder2(BiTree T){ 78 stack<BiTree> stack; 79 //p是遍历指针 80 BiTree p = T; 81 //栈不空或者p不空时循环 82 while(p || !stack.empty()){ 83 if(p != NULL){ 84 //存入栈中 85 stack.push(p); 86 //访问根节点 87 printf("%c ",p->data); 88 //遍历左子树 89 p = p->lchild; 90 } 91 else{ 92 //退栈 93 p = stack.top(); 94 stack.pop(); 95 //访问右子树 96 p = p->rchild; 97 } 98 }//while 99 } 100 /* 中序遍历(非递归) 101 思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 102 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 103 */ 104 void InOrder2(BiTree T){ 105 stack<BiTree> stack; 106 //p是遍历指针 107 BiTree p = T; 108 //栈不空或者p不空时循环 109 while(p || !stack.empty()){ 110 if(p != NULL){ 111 //存入栈中 112 stack.push(p); 113 //遍历左子树 114 p = p->lchild; 115 } 116 else{ 117 //退栈，访问根节点 118 p = stack.top(); 119 printf("%c ",p->data); 120 stack.pop(); 121 //访问右子树 122 p = p->rchild; 123 } 124 }//while 125 } 126 127 //后序遍历(非递归) 128 typedef struct BiTNodePost{ 129 BiTree biTree; 130 char tag; 131 }BiTNodePost,*BiTreePost; 132 133 void PostOrder2(BiTree T){ 134 stack<BiTreePost> stack; 135 //p是遍历指针 136 BiTree p = T; 137 BiTreePost BT; 138 //栈不空或者p不空时循环 139 while(p != NULL || !stack.empty()){ 140 //遍历左子树 141 while(p != NULL){ 142 BT = (BiTreePost)malloc(sizeof(BiTNodePost)); 143 BT->biTree = p; 144 //访问过左子树 145 BT->tag = ‘L‘; 146 stack.push(BT); 147 p = p->lchild; 148 } 149 //左右子树访问完毕访问根节点 150 while(!stack.empty() && (stack.top())->tag == ‘R‘){ 151 BT = stack.top(); 152 //退栈 153 stack.pop(); 154 printf("%c ",BT->biTree->data); 155 } 156 //遍历右子树 157 if(!stack.empty()){ 158 BT = stack.top(); 159 //访问过右子树 160 BT->tag = ‘R‘; 161 p = BT->biTree; 162 p = p->rchild; 163 } 164 }//while 165 } 166 //层次遍历 167 void LevelOrder(BiTree T){ 168 BiTree p = T; 169 //队列 170 queue<BiTree> queue; 171 //根节点入队 172 queue.push(p); 173 //队列不空循环 174 while(!queue.empty()){ 175 //对头元素出队 176 p = queue.front(); 177 //访问p指向的结点 178 printf("%c ",p->data); 179 //退出队列 180 queue.pop(); 181 //左子树不空，将左子树入队 182 if(p->lchild != NULL){ 183 queue.push(p->lchild); 184 } 185 //右子树不空，将右子树入队 186 if(p->rchild != NULL){ 187 queue.push(p->rchild); 188 } 189 } 190 } 191 int main() 192 { 193 BiTree T; 194 CreateBiTree(T); 195 printf("先序遍历：\n"); 196 PreOrder(T); 197 printf("\n"); 198 printf("先序遍历(非递归)：\n"); 199 PreOrder2(T); 200 printf("\n"); 201 printf("中序遍历：\n"); 202 InOrder(T); 203 printf("\n"); 204 printf("中序遍历(非递归)：\n"); 205 InOrder2(T); 206 printf("\n"); 207 printf("后序遍历：\n"); 208 PostOrder(T); 209 printf("\n"); 210 printf("后序遍历(非递归)：\n"); 211 PostOrder2(T); 212 printf("\n"); 213 printf("层次遍历：\n"); 214 LevelOrder(T); 215 printf("\n"); 216 return 0; 217 }
算法之二叉树各种遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。