题解：二叉排序树的建立和遍历（malloc函数和typedf）

第二次修改，增加了new和二叉树的一些基本操作。

---

题目描述

输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。

输入

输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。

自己不熟悉的地方：

• 用到了malloc函数：

1.malloc函数是一种分配长度为num_bytes字节的内存块的函数，可以向系统申请分配指定size个字节的内存空间。
2.malloc的全称是memory allocation，中文叫动态内存分配，当无法知道内存具体位置的时候，想要绑定真正的内存空间，就需要用到动态的分配内存。
3.返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定，void* 类型可以通过类型转换强制转换为任何其它类型的指针。
4.相关：

作用	代码
malloc函数原型	extern void *malloc(unsigned int num_bytes);
malloc函数头文件	#include <stdlib.h>或者#include <malloc.h>

谢谢提示，这里用new建立也可以，还简单一些。百度了一下malloc和new的区别，放这了。https://www.cnblogs.com/shilinnpu/p/8945637.html

• 用到了typedef定义新的结构体

大佬总结很详细：https://blog.csdn.net/superhoy/article/details/53504472

---

代码实现如下：

| 

#include <iostream>
#include <malloc.h>
using namespace std;
 
typedef struct Bnode
{
    int data;
    struct Bnode *Ichild,*Rchild; 
} Bnode,*Btree;
 
void Creat_BST(Btree &T,int a)
{
    if(T==NULL)
    {
        T=(Btree)malloc(sizeof(Bnode));  //强制转换
        T->Ichild=NULL;
        T->Rchild=NULL;
        T->data=a;
    }
    else{
        if(a>T->data){
            Creat_BST(T->Rchild,a);
        }
        if(a<T->data){
            Creat_BST(T->Ichild,a);
        }
        else return;
    }
}
 
int preOrder(Btree T)    //先序遍历
{
    if(T==NULL) return 0;
    cout<<T->data<<" ";
    preOrder(T->Ichild);
    preOrder(T->Rchild);
}
 
int inOrder(Btree T)     //中序遍历
{
    if(T==NULL)  return 0;
    inOrder(T->Ichild);
    cout<<T->data<<" ";
    inOrder(T->Rchild);
}
 
int postOrder(Btree T)  //后序遍历
{
    if(T==NULL)  return 0;
    postOrder(T->Ichild);
    postOrder(T->Rchild);
    cout<<T->data<<" ";
}
 
int main()
{
    int n;
    while(cin>>n)
    {
        Btree T=NULL;
        while(n)
        {
            int a;
            n--;
            cin>>a;
            Creat_BST(T,a);
        }
        preOrder(T);
        cout<<endl;
        inOrder(T);
        cout<<endl;
        postOrder(T);
        cout<<endl;
    }
}

---

二叉树节点总数目：

int Nodenum(Btree T)
{
    if(!T) return 0;
    else return  1+(Nodenum(T->Ichild)+Nodenum(T->Rchild)) ;
}

二叉树深度：（和高度同理）

int DepthOfTree(Btree T)
{
    if(!T) return 0;
    else 
    return  DepthOfTree(T->Ichild)>DepthOfTree(T->Rchild)? 1+DepthOfTree(T->Ichild):1+DepthOfTree(T->Rchild);
}

二叉树叶子节点数：

int Leafnum(Btree T)
{
    if(!T) return 0;
    else if((T->Ichild== NULL) && (T->Rchild == NULL) ) return 1;
    else return  (Leafnum(T->Ichild)+Leafnum(T->Rchild)) ;
}