首页 > 代码库 > 数据结构-王道2017-第4章 树与二叉树-二叉树的遍历
数据结构-王道2017-第4章 树与二叉树-二叉树的遍历
typedef int ElemType; typedef struct BitNode { ElemType data; //数据域 struct BitNode *lchild, *rchild; //左右孩子指针 }BitNode,*BitTree; void visit(BitNode *b) { printf("%d ", b->data); } //无论采用哪种遍历方法,时间复杂度都是O(n),因为每个结点都访问一次且仅访问一次,递归工作栈的栈深恰好为树的深度,空间复杂都为O(n) //先序遍历根左右 void PreOrder(BitTree T) { if (T != NULL) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } //中序遍历左根右 void InOrder(BitTree T) { if (T != NULL) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } //后序遍历左根右 void PostOrder(BitTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } //递归算法转换为非递归, void Inorder2(BitTree T) { stack<BitTree> s; BitTree p = T; while (p != NULL || !s.empty()) { //栈不空时或p不空时循环 if (p) { s.push(p); p = p->lchild; } else { p = s.top; s.pop(); //弹出时,p没有左指针 visit(p); p = p->rchild; } } } //二叉树层次遍历,借助队列 void LevelOrder(BitTree T) { queue<BitTree> q; BitTree p = T; q.push(p); while (!q.empty) { p = q.front; q.pop(); visit(p); if (p->lchild) q.push(p->lchild); //左子树不空,则左子树入队 if (p->rchild) q.push(p->rchild); } }
注意:由遍历序列构造二叉树,由二叉树的先序序列和中序序列,后续序列和中序序列,层序序列和中序序列可以唯一地确定一棵二叉树,如果只知道二叉树的先序序列和后序序列则无法唯一确定一棵二叉树
数据结构-王道2017-第4章 树与二叉树-二叉树的遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。