首页 > 代码库 > 二叉树遍历
二叉树遍历
1.首先是二叉树的建立
先序递归建立一个 建立一个二叉树 用#表示空
void CreatTree(BitNode **root){ char ch; scanf("\n%c",&ch); if(ch == ‘#‘) *root = NULL; else { *root = (BitNode *)malloc(sizeof(BitNode)); (*root)->data =http://www.mamicode.com/ ch; printf("%cleft child:",ch); CreatTree(&(*root)->lchild); printf("%cright child:",ch); CreatTree(&(*root)->rchild); }}
2. 运用递归的思想遍历二叉树， 这种方法最为简单。
void PreOrder(BitNode *root){ if(root == NULL) { return; } printf("%c ",root->data); PreOrder(root->lchild);
PreOrder(root->rchild); }
3.借助栈 可以实现非递归方法
思路: 按照我们的遍历方法走二叉树
1) 一直向左 (至叶子节点-> 左右都是NULL)
2) 弹栈 回退一个节点 向右走一步后继续 ( 再重复 1~2 步骤至栈空)
//前序非递归
void PreOrder_Nonrecrusive(pBittree T){ if(!T) return ; stack<pBittree> s; pBittree p= T; while(p != NULL || !s.empty()) { while(p != NULL) { cout << p->data << " "; s.push(p); p = p-> lchild; } if(!s.empty()) { p = s.top(); s.pop(); p = p->rchild; } }}
后续非递归：
遍历过程相似：
因为后续非递归方法是先访问左子树，再访问右子树，最后访问根节点，用栈储存时必须分清反悔跟节点是做还是右，所以需要一个辅助指针r;指向其最近访问节点。 也可增加一个标识域；
void PostOrder_Nonrecresive(pBittree T){ stack<pBittree> s; pBittree p = T, r = NULL, temp; while(p || !s.empty()) { if(p) { s.push(p); p = p->lchild; } else { p = s.top(); if(p->rchild && p->rchild != r ) { p = p->rchild; s.push(p); p = p->lchild; } else { p = s.top(); s.pop(); cout << p->data << " "; r = p; p = NULL; } } //else } //while}
二叉树遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。