DataStructure_Tree

树的遍历

树的声明

#include <stdio.h>
#include "iostream"
using namespace std;
//树的声明
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;                      //数据域
    struct BiTNode *lchild,*rchild;     //左孩子指针与右孩子指针
}BiTNode,*BiTree;

树的赋值

BiTree PreCreateTree(BiTree tree){
    char ch;
    cin>>ch;
    if (ch=='#') return NULL;						//这里我们让#视为NULL
    else{
        tree = (BiTree) malloc(sizeof(BiTNode));	//申请一片空间存放数据
        tree->data=ch;								//头节点开始赋值
        tree->lchild=PreCreateTree(tree->lchild);	//左孩子开始赋值
        tree->rchild=PreCreateTree(tree->rchild);	//右孩子开始赋值
        return tree;								//返回treee
    }
}

注释:
	1、特别的我们开始进行赋值的时候得注意：
	头赋值->左孩子赋值->左孩子的左孩子节点进行赋值(若为null即为右孩子赋值)
	2、左/右孩子为NULL 返回当前节点的父节点
	3、举例
		1、若我们需要赋值的树为
			A
		B		C
      D  E     # #
    # #	 # #
    在输入的数据时开始为:ABD##E##c##

前序遍历

//先序遍历
void PreOrder(BiTree root){
    if (root!=NULL){
        printf("%c",root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

中序遍历

//中序遍历
void InOrder(BiTree root){
    if (root!=NULL){
        InOrder(root->lchild);
        printf("%c",root->data);
        InOrder(root->rchild);
    }
}

后序遍历

//后序遍历
void PostOrder(BiTree tree){
    if (tree!=NULL){
        PostOrder(tree->lchild);
        PostOrder(tree->rchild);
        printf("%c",tree->data);
    }
}

全部代码

#include <stdio.h>
#include "iostream"
using namespace std;
//树的声明
typedef char ElemType;
typedef struct BiTNode{
    ElemType data;                      //数据域
    struct BiTNode *lchild,*rchild;     //左孩子指针与右孩子指针
}BiTNode,*BiTree;
BiTree PreCreateTree(BiTree tree){
    char ch;
    cin>>ch;
    if (ch=='#') return NULL;
    else{
        tree = (BiTree) malloc(sizeof(BiTNode));
        tree->data=ch;
        tree->lchild=PreCreateTree(tree->lchild);
        tree->rchild=PreCreateTree(tree->rchild);
        return tree;
    }
}
//先序遍历
void PreOrder(BiTree root){
    if (root!=NULL){
        printf("%c",root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}
//中序遍历
void InOrder(BiTree root){
    if (root!=NULL){
        InOrder(root->lchild);
        printf("%c",root->data);
        InOrder(root->rchild);
    }
}
//后序遍历
void PostOrder(BiTree tree){
    if (tree!=NULL){
        PostOrder(tree->lchild);
        PostOrder(tree->rchild);
        printf("%c",tree->data);
    }
}
int main(){
    BiTree tree;
    tree=NULL;
    tree=PreCreateTree(tree);
    cout<<"先序遍历"<<endl;
    PreOrder(tree);
    cout<<endl;
    cout<<"中序遍历"<<endl;
    InOrder(tree);
    cout<<endl;
    cout<<"后序遍历"<<endl;
    PostOrder(tree);

}

输出结果:
ABE##F##C##
先序遍历
ABEFC
中序遍历
EBFAC
后序遍历
EFBCA

注意:
	1、如果不能理解注意我们给的赋值函数这里的ABE##F##C##是这样的
		A
	  B     C
    E   F  # #
   # # # #
    2、自己慢慢体会，现在可以本子上画一个你喜欢的树，然后根据函数的输入写出它的赋值输入字符，再在你的本子上列出你自己的前序、后序、中序遍历，看是否是和电脑的一模一样。如果是那么你就理解到了这三个遍历的意思和方法并且对上诉代码也已经掌握到了~；如果不是那么还需要看看是哪里还没理解到哦~