二叉树遍历及C语言实现,二叉树的构造

二叉树的结构、遍历
//2008.04.12
#include<stdio.h>
#include<iostream>
using namespace std;
struct binaryTreeNode
{
 char data;
 struct binaryTreeNode *lefttree,*righttree;
};
typedef struct binaryTreeNode BinaryTree;
char ch=’ ‘;
void CreateTree(BinaryTree *&tree)

 if(ch!=’n’)
 { ch=getchar();
    if(ch==’n’)
     return;
       if(ch==’.’)
      tree=NULL;
     else
  {
     tree=new BinaryTree;    
     tree->data=ch;
     tree->lefttree=NULL;
     tree->righttree=NULL;
           CreateTree(tree->lefttree);
     CreateTree(tree->righttree);
  }
 }
 else return;
}

二叉树遍历及C语言实现

void PreOrder(BinaryTree *tree)
{
 if(tree!=NULL)
 {  
  putchar(tree->data);
     PreOrder(tree->lefttree);
  PreOrder(tree->righttree);
 }
}

已知中序和前序连串,恐怕已知中序和后序连串,都能够协会一棵二叉树。在本例中,本人用C语言写程序解答了上边三个算法题:

void InOrder(BinaryTree *tree)
{
 if(tree!=NULL)
 {  
  InOrder(tree->lefttree);
  putchar(tree->data);
  InOrder(tree->righttree);
 }
}

(1)给出一棵二叉树的中序与后序遍历系列,求出它的先序遍历系列。

void PostOrder(BinaryTree *tree)
{
 if(tree!=NULL)
 {  
  PostOrder(tree->lefttree);  
  PostOrder(tree->righttree);
  putchar(tree->data);
 }
}

(2)给出一棵二叉树的中序与先序遍历系列,求出它的后序遍历体系。

int main()
{
 BinaryTree *t=NULL;
 cout<<“(输入时以前序和完全二叉树的款型,空结点用’.’替代,遭逢叶子结点时加输两个’.’)”<<endl;
 cout<<“请输入一串字符串:”<<endl;
 CreateTree(t);
 cout<<“按前序遍历:”<<endl;
 PreOrder(t);
 cout<<endl;
 cout<<“按中序遍历:”<<endl;
 InOrder(t);
 cout<<endl;
 cout<<“按后序遍历:”<<endl;
 PostOrder(t);
 cout<<endl;
 return 0;
}

知识点扼要回想:
所谓二叉树的遍历,是指按自然的顺序对二叉树中的每一种结点均访问二遍,且仅访问一。根据根结点访谈地方的两样,平常把二叉树的遍历分为七种:
TLR(根左右), TRL(根右左), LTR(左根右)
RTL(右根左), LRT(左右根), RLT(右左根)

当中,TTiguanL、RTL和EscortLT三种顺序在左右子树之间均是先右子树后左子树,那与大家先左后右的习于旧贯差异,因而,往往不予选拔。余下的二种顺序TLEscort、LT奥德赛和LRT依据根访谈的岗位差别分别被可以称作前序遍历、中序遍历和后序遍历。

发表评论

电子邮件地址不会被公开。 必填项已用*标注