二叉树

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的字数由左右之分，顺序不可颠倒。

二叉树的存储结构：1.顺序存储结构（仅适用于完全二叉树） 2.链式存储结构

二叉树的遍历：

先序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

（1）访问根结点

（2）先序遍历左子树

（3）先序遍历右子树

中序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

后序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

// 二叉树.cpp : 定义控制台应用程序的入口点。  
//  
  
#include "stdafx.h"  
#include <iostream>  
#include <cstdlib>  
#include <queue>  
#include <malloc.h>  
/*  
 
 *以先序遍历输入一棵二叉树并完成二叉树的建立 以及 前序·中序·后序·层次的遍历 二叉树的 结点个数 高度 
 
 *参考数据结构C语言版（严蔚敏） 
 
 
*/  
  
#include <string>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
//定义节点  
typedef struct BiTNode {  
char data;  
struct BiTNode *lChild,*rChild;  
}BiTNode,*BiTree;  
  
void CreateBiTree(BiTree &T)   
  
{//二叉树的建立  
    char ch;  
//按照先序输入二叉树中结点的值（一个字符），‘@’表示结点为空  
  
//构造二叉链表表示的二叉树T  
    ch = getchar();  
    if(ch=='@')  
        T = NULL;  
    else {  
        T = new BiTNode;  
        T->data = ch;  
        CreateBiTree(T->lChild);  
        CreateBiTree(T->rChild);  
    }  
}  
  
void PreOrderTraverse(BiTree T)  
{//先序遍历  
    if(T)  
    {  
        cout << T->data;  
        PreOrderTraverse(T->lChild);  
        PreOrderTraverse(T->rChild);  
    }  
}  
  /* 何问起 hovertree.com */
void InOrderTraverse(BiTree T)  
{//中序遍历  
    if(T)  
    {  
        InOrderTraverse(T->lChild);  
        cout << T->data;  
        InOrderTraverse(T->rChild);  
    }  
}  
  
void PostOrderTraverse(BiTree T)  
{//后序遍历  
    if(T)  
    {  
        PostOrderTraverse(T->lChild);  
        PostOrderTraverse(T->rChild);  
        cout << T->data;  
    }  
}  
  
void LevelOrder(BiTree T)  
{//层次遍历  
    queue<BiTree> q; //队列  
    BiTree t = T; //从t结点开始进行层次遍历  
    if(t) q.push(t); //t非空，入队  
    while(!q.empty())  
    {  
        t = q.front();  
        q.pop();  
        cout << t->data;  
        if(t->lChild!=NULL) //t的左子树非空，入队  
            q.push(t->lChild);  
        if(t->rChild!=NULL) //t的右子树非空，入队  
            q.push(t->rChild);  
    }  
}  
  
  
  /* 何问起 hovertree.com */
int NodeCountHelp(BiTree T)  
{//返回以T为根的二叉树的结点个数  
    if(T==NULL)   
        return 0; //空二叉树结点个数为0  
    else return NodeCountHelp(T->lChild) + NodeCountHelp(T->rChild) + 1 ;   
//非空二叉树的结点个数为 左子树结点个数+右子树结点个数+1  
}  
  
int HeightHelp(BiTree T)  
{//返回以T为根的二叉树的高度  
    if(T==NULL)   
        return 0; //空二叉树的高度为0  
    else{//非空二叉树的高度为 左右字数高度的最大值+1  
        int lHeight = HeightHelp(T->lChild); //左子树高度  
        int rHeight = HeightHelp(T->rChild); //右子树高度  
        return (lHeight>rHeight ? lHeight : rHeight) + 1;//高为左右子树高度最大值+1  
    }  
}  
  
int main()  
{  
    BiTree root;  
    printf("请以先序遍历的方式输入二叉树，空结点用‘@’代替，如AB@@C@@,ABC@@DE@G@@F@@@");  
    CreateBiTree(root);  
    //输出先序遍历  
    cout << "此二叉树的先序遍历是：" ;  
    PreOrderTraverse(root);  
    cout << endl;  
    //输出中序遍历  
    cout << "此二叉树的中序遍历是：" ;  
    InOrderTraverse(root);  
    cout << endl;  
    //输出后序遍历  
    cout << "此二叉树的后序遍历是：" ;  
    PostOrderTraverse(root);  
    cout << endl;  
    //输出层次遍历  
    cout<< "此二叉树的层次遍历是：" ;  
    LevelOrder(root);  
    cout << endl;  
    //输出二叉树的结点数  
    cout << "此二叉树的结点数为:" << NodeCountHelp(root) << endl;  
    //输出二叉树的高度  
    cout << "此二叉树的高度为：" << HeightHelp(root) << endl;  
    return 0;  
}