二叉树的遍历的完整代码是什么
二叉树遍历代码
#include“iostream.h“
#include“stdlib.h“
#include“stdio.h“
#include《stack》
using namespace std;
#define NULL 0
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}*bitree;
int k=0;
int depth(bitree T)//树的高度
{
if(!T)return 0;
else
{
int m=depth(T-》lchild); int n=depth(T-》rchild); return (m》n?m:n)+1;
}
}
//先序，中序 建树
struct node *create(char *pre,char *ord,int n) {
struct node * T;
int m;
T=NULL;
if(n《=0)
{
return NULL;
}
else
{
m=0;
T=new(struct node);
T-》data=*pre;
T-》lchild=T-》rchild=NULL; while(ord[m]!=*pre)
m++;
T-》lchild=create(pre+1,ord,m);
T-》rchild=create (pre+m+1,ord+m+1,n-m-1); return T;
}
}
//中序递归遍历
void inorder(struct node *T)
{
if(!T)
return;
else
{
inorder(T-》lchild );
cout《《T-》data;
inorder(T-》rchild );
}
}
void inpre(struct node *T)
{
if(!T)
return;
else
{
cout《《T-》data;
inpre(T-》lchild );
inpre(T-》rchild );
}
}
void postorder(struct node *T)
{
if(!T)
return;
else
{
postorder (T-》lchild );
postorder (T-》rchild );
cout《《T-》data;
}
}
//先序非递归遍历
void inpre1(struct node *T)
第2/4页
{
struct node *p;
struct node *stack;
int top=0;
p=T;
cout《《“非递归先序为:“《《endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
cout《《p-》data;
p=p-》lchild;
}
p=stack[--top];
p=p-》rchild ;
}
}
//中序非递归遍历
void inorder1(struct node *T)
{
struct node *p;
struct node *stack;
int top=0;
p=T;
cout《《“非递归中序为:“《《endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p-》lchild ;
}
p=stack[--top];
cout《《p-》data;
p=p-》rchild ;
}
}
//主函数
int main()
{
bitree T;
char pre,ord;
第3/4页
int n,m;
cout《《“请输入先序为-+a*b%cd/ef的二叉树:“《《endl; gets(pre);
cout《《“请输入中序为a+b*c%d-e/f的二叉树:“《《endl; gets(ord);
n=strlen(pre);
T=create(pre,ord,n);
cout《《 “后序遍历为:“《《endl;
postorder (T);
cout《《endl;
inpre1(T);
cout《《endl;
inorder1(T);
cout《《endl;
m=depth(T);
cout《《“二叉树高度为：“《《m《《endl;
return 0;
}
二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
[cpp] view plaincopy
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。-二叉树遍历代码
[cpp] view plaincopy
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。
第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。-二叉树
[cpp] view plaincopy
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后：
访问完第1层之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plaincopy
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plaincopy
#include《iostream》
#include《vector》
#include《deque》
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == ’#’) {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)-》data = c;
create_tree(&(*T)-》lchild);
create_tree(&(*T)-》rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout 《《 T-》data 《《 “ “;
print_tree(T-》lchild);
print_tree(T-》rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level 《 0)
return 0;
if (0 == level) {
cout 《《 T-》data 《《 “ “;
return 1;
}
return print_at_level(T-》lchild, level - 1) + print_at_level(T-》rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout 《《 endl;
}
void print_by_level_2(Tree T) {
deque《tree_node_t*》 q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout 《《 temp-》data 《《 “ “;
if (temp-》lchild)
q_second.push_back(temp-》lchild);
if (temp-》rchild)
q_second.push_back(temp-》rchild);
}
cout 《《 endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector《tree_node_t*》 vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur 《 vec.size()) {
end = vec.size();
while (cur 《 end) {
cout 《《 vec[cur]-》data 《《 “ “;
if (vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if (vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cur++;
}
cout 《《 endl;
}
}
int main(int argc, char *argv) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout 《《 endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
完全二叉树与满二叉树的区别是什么
1、含义不同：
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
2、表示不同：
对于满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。而完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
判断一棵树是否是完全二叉树的思路
1》如果树为空，则直接返回错
2》如果树不为空：层序遍历二叉树
2.1》如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
2.1》如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2》如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；
以上内容参考：百度百科-完全二叉树
