非递归实现二叉树先序中序后序遍历:从创建到展示

需积分: 9 6 下载量 124 浏览量 更新于2024-09-01 收藏 4KB TXT 举报
本资源主要探讨了在C++和C语言中如何通过非递归方法实现二叉树的构建、遍历以及以括号表示法输出二叉树。首先,定义了一个名为`btnode`的结构体,用于存储二叉树节点,包含数据域`data`,以及左孩子指针`lchild`和右孩子指针`rchild`。接下来,函数`create()`是核心部分,它接收一个字符串`str`作为输入,根据输入的括号表示法解析并构建二叉树。该函数通过栈来跟踪当前的子树边界,并根据遇到的不同字符(左括号、右括号或逗号)进行相应的操作,如分配新节点、连接子节点等。 `preorder()`、`inorder()`和`postorder()`函数分别实现了二叉树的先序遍历、中序遍历和后序遍历。先序遍历遵循"根-左-右"的顺序,中序遍历遵循"左-根-右"的顺序,而后序遍历则是"左-右-根"。这些函数都是通过递归调用自身,直到遍历到空节点。 最后,`dispbtree()`函数用于以括号表示法展示二叉树的结构。如果节点存在左孩子或右孩子,会先打印出左括号,然后递归地遍历左子树和右子树,最后关闭当前节点的括号。这样,用户可以直观地看到二叉树的层次结构。 总结起来,本资源提供了一套完整的非递归方法来处理二叉树的创建、遍历和可视化,对于理解和实践二叉树的数据结构和算法分析具有较高的参考价值。通过学习和应用这些函数,开发者能够熟练掌握C++和C语言中的二叉树操作技巧。
2006-02-23 上传
1.先序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack;void PreOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec2.中序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack;void InOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历 }//endif }//endwhile}//InOrderUnrec3.后序遍历非递归算法#define maxsize 100typedef enum{L,R} tagtype;typedef struct { Bitree ptr; tagtype tag;}stacknode;typedef struct{ stacknode Elem[maxsize]; int top;}SqStack;void PostOrderUnrec(Bitree t){ SqStack s; stacknode x; StackInit(s); p=t; do { while (p!=null) //遍历左子树 { x.ptr = p; x.tag = L; //标记为左子树 push(s,x); p=p->lchild; } while (!StackEmpty(s) && s.Elem[s.top].tag==R) { x = pop(s); p = x.ptr; visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点 } if (!StackEmpty(s)) { s.Elem[s.top].tag =R; //遍历右子树 p=s.Elem[s.top].ptr->rchild; } }while (!StackEmpty(s));}//PostOrderUnrec