二叉树的创建与遍历
【摘要】 二叉树的创建，递归遍历，非递归遍历，直接看代码
#include<iostream>
#include<stack>
using namespace std;
//结构体
typedef struct Node
{ char data; Node *lchild; Node *rchild;
}Node, *Tree;
//创建一个结点
N...
二叉树的创建，递归遍历，非递归遍历，直接看代码
#include<iostream>
#include<stack>
using namespace std;
//结构体
typedef struct Node
{ char data; Node *lchild; Node *rchild;
}Node, *Tree;
//创建一个结点
Node *CreateNode()
{ Node*p = new(nothrow)(Node); if(p==NULL) { exit(-1); } memset(p, 0, sizeof(Node)); return p;
}
//创建一棵二叉树
Node* CreateTree(char *&s)
{ if(s==NULL) { return NULL; } Node*p =NULL; if(*s != '$') { p = CreateNode(); p->data = *s; p->lchild = CreateTree(++s); p->rchild = CreateTree(++s); } return p;
}
//先序
void preorder(Node *root)
{ if(root != NULL) { cout<<root->data<<" "; preorder(root->lchild ); preorder(root->rchild); }
}
//后序
void back(Node*p)
{ if(p) { back(p->lchild); back(p->rchild); cout<<p->data<<" "; }
}
//后序非递归遍历
void Back(Node *root)
{ if(root==NULL) { return ; } stack<Node*>s; Node*cur=NULL; Node*pre =NULL; cur = root; s.push(cur); while(!s.empty()) { cur = s.top(); if((cur->lchild==NULL && cur->rchild==NULL) || (pre !=NULL &&(pre==cur->lchild || pre==cur->rchild))) {//肯定先访问右孩子，在访问左孩子，因为入栈是先右孩子再左孩子； //我认为主要是防止只有左孩子，或只有右孩子； cout<<cur->data<<" "; pre = cur; s.pop(); } else { if(cur->rchild != NULL) { s.push(cur->rchild); } if(cur->lchild != NULL) { s.push(cur->lchild); } } }
}
//中序递归遍历
void Inorder(Node*root)
{ if(root != NULL) { Inorder(root->lchild); cout<<root->data<<" "; Inorder(root->rchild); }
} //非递归先序遍历
void Pre2(Node*root)
{ if(root == NULL) { return ; } stack<Node*>s; Node* p =root; while(p !=NULL || !s.empty() ) { while(p !=NULL) { s.push(p); cout<<p->data<<" "; p=p->lchild ; } if(!s.empty()) { p=s.top(); s.pop(); p=p->rchild; } }
}
//费递归中序遍历
void _Inorder(Node*root)
{ if(root ==NULL) { return ; } stack<Node*>s; Node*p = root; while(p !=NULL || !s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); s.pop(); cout<<p->data<<" "; p=p->rchild; } }
}
int main()
{ char *s="fdba$$c$$e$$g$ih$$j$$"; Node*root = CreateTree(s); back(root); cout<<endl; preorder(root); cout<<endl; Pre2(root); cout<<endl; Inorder(root); cout<<endl; Back(root); cout<<endl; _Inorder(root); cout<<endl; return 0;
}
文章来源: blog.csdn.net，作者：IM-STONE，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/doubleintfloat/article/details/52398872
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）