树的构造
# include <stdio.h>
# include <stdlib.h>
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode *create(struct TreeNode *tree)
{
int ch;
scanf("%d", &ch);
if(ch == 0)
{
tree = NULL;
}
else
{
tree = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));
tree -> val = ch;
tree -> left = create(tree -> left);
tree -> right = create(tree -> right);
}
return tree;
}
void printorder(struct TreeNode *tree)
{
if(tree)
{
printf("%d ", tree -> val);
printorder(tree -> left);
printorder(tree -> right);
}
}
main()
{
struct TreeNode *tree = NULL;
tree = create(tree);
printf("xianxu ->> ");
printorder(tree);
printf("\n\n");
}
验证程序正确
// 中序遍历非递归实现
void zhong(TreeNode* root){
if(root == NULL){
cout<<"树为空";
return ;
}
TreeNode* p = root;
stack<TreeNode*> sk;
while(!s.empty() || p){
if(p){
sk.push(p);
p = p->lchild;
}
else{
p = sk.top();
sk.pop();
cout<<p->data<<" ";
p = p->rchild;
}
}
}
// 前序遍历非递归实现
void qian(TreeNode* root){
if(root == NULL){
cout<<"树为空";
return ;
}
TreeNode* p = root;
stack<TreeNode* > sk;
while(!s.empty() || p){
if(p){
cout<<p->data<<" ";
sk.push(p);
p = p->lchild;
}
else{
p = s.top();
s.pop();
p = p->rchild;
}
}
}
// 后序遍历非递归实现
void hou(TreeNode* root){
if(root == NULL){
cout<<"树为空";
return ;
}
TreeNode* p = root;
stack<TreeNode* > sk;
//pCur:当前访问节点，pLastVisit:上次访问节点
BTNode* pCur, *pLastVisit;
//pCur = root;
pCur = root;
pLastVisit = NULL;
//先把pCur移动到左子树最下边
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
while (!s.empty())
{
//走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
pCur = s.top();
s.pop();
//一个根节点被访问的前提是：无右子树或右子树已被访问过
if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
{
cout << setw(4) << pCur->data;
//修改最近被访问的节点
pLastVisit = pCur;
}
/*这里的else语句可换成带条件的else if:
else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
*/
else
{
//根节点再次入栈
s.push(pCur);
//进入右子树，且可肯定右子树一定不为空
pCur = pCur->rchild;
while (pCur)
{
s.push(pCur);
pCur = pCur->lchild;
}
}
}
cout << endl;
}
