遍历,中跟遍历,后根遍历"/>
二叉树的先跟遍历,中跟遍历,后根遍历
- //二叉树结点的定义。
- typedef struct BiTreeNode
- {
- int data;
- BiTreeNode* left;
- BiTreeNode* right;
- public:
- BiTreeNode();//定义了一个结构体的构造函数。
- }BiTreeNode,*LinkBiTree;
- //构造函数的实现
- BiTreeNode::BiTreeNode()
- {
- left = NULL;
- right = NULL;
- }
- int SqBiTree::PreOrderTraverse(LinkBiTree root)
- {
- LinkBiTree p = root;
- Stack stack;//定义一个栈
- stack.InitStack();//栈初始化
- cout<<"The Tree is ..."<<endl;
- while(!stack.IsEmpty() || p != NULL)
- {
- //从头结点开始遍历到左子树最左边的叶子节点。把每一个遍历的节点入栈,用于准备遍历其相应的右子树
- while (p!=NULL)
- {
- cout<<p->data<<" ";//访问节点
- stack.Push(p);
- p = p->left;
- }
- stack.Pop(p);
- //先一个循环遍历相应节点的右子树
- p = p->right;
- }
- cout<<endl;
- return 0;
- }
- //中根遍历的非递归算法
- int SqBiTree::InOrderTraverse(LinkBiTree root)
- {
- LinkBiTree p = root;
- Stack stack;
- stack.InitStack();
- cout<<"The Tree is ..."<<endl;
- while(!stack.IsEmpty() || p != NULL)
- {
- //从根节点开始到最左边的叶子节点,入栈
- while (p!=NULL)
- {
- stack.Push(p);
- p = p->left;
- }
- stack.Pop(p);
- cout<<p->data<<" "; //访问节点
- p = p->right; //下一次循环把节点p的右子树入栈
- }
- cout<<endl;
- return 0;
- }
- //后根遍历的非递归算法
- int SqBiTree::PostOrderTraverse(LinkBiTree root)
- {
- LinkBiTree p = root;
- Stack stack;
- stack.InitStack();
- while(!stack.IsEmpty() || p != NULL)
- {
- //从根节点开始到最左边的叶子节点,入栈
- while (p!=NULL)
- {
- stack.Push(p,1);
- p = p->left;
- }
- int skip = 0;
- stack.Pop(p,skip);
- if (skip == 0)
- {
- cout<<p->data<<" ";
- p = NULL;
- }
- else if (skip == 1)
- {
- p =p->right;
- }
- }
- return 0;
- }
后根遍历用到的栈有一些特殊,栈中元素要出栈两次才会被真正出栈。也就是说:
该栈的链式存储节点的定义如下:
[cpp] view plain copy
- typedef struct StackNode
- {
- LinkBiTree data;//数据域
- int skip; //出栈操作被“忽略”的次数
- StackNode *next;//指向下一结点的指针域
- public:
- StackNode();
- }StackNode,*LinkList;
例如:
栈的某个节点的skip = 0时,只需执行一次出栈操作即可正常出栈。
栈的某个节点的skip = 1时,第一次出栈操作只会返回该节点数据域中的数据,第二次出栈操作才会真正的出栈(当然数据域中的数据也返回)
栈的某个节点的skip = 2时,前两次出栈操作只会返回该节点数据域中的数据,第三次出栈操作才会真正的出栈(当然数据域中的数据也返回)
......
通过比较二叉树的先根遍历,中根遍历,后根遍历的非递归算法可以发现:这三个算法的实现是极其相似的(如同它们递归算法的也很相似一般)。
1:都用到了栈来暂存节点。
2:都是两个while的嵌套循环。
3: 如果除去访问节点的语句,先根遍历和中根遍历是完全相同的,后根遍历也只是出栈函数的参数不同而已。
更多推荐
二叉树的先跟遍历,中跟遍历,后根遍历
发布评论