第二次修改柏卤，增加了new和二叉樹的一些基本操作省容。
題目描述
輸入一系列整數(shù)抖拴，建立二叉排序數(shù)，并進(jìn)行前序腥椒，中序阿宅，后序遍歷。
輸入
輸入第一行包括一個(gè)整數(shù)n(1<=n<=100)笼蛛。接下來的一行包括n個(gè)整數(shù)洒放。
輸出
可能有多組測(cè)試數(shù)據(jù)，對(duì)于每組數(shù)據(jù)滨砍，將題目所給數(shù)據(jù)建立一個(gè)二叉排序樹往湿，并對(duì)二叉排序樹進(jìn)行前序妖异、中序和后序遍歷。每種遍歷結(jié)果輸出一行领追。每行最后一個(gè)數(shù)據(jù)之后有一個(gè)空格他膳。
自己不熟悉的地方：
-
用到了malloc函數(shù)：
1.malloc函數(shù)是一種分配長(zhǎng)度為num_bytes字節(jié)的內(nèi)存塊的函數(shù)，可以向系統(tǒng)申請(qǐng)分配指定size個(gè)字節(jié)的內(nèi)存空間绒窑。
2.malloc的全稱是memory allocation棕孙，中文叫動(dòng)態(tài)內(nèi)存分配，當(dāng)無法知道內(nèi)存具體位置的時(shí)候些膨，想要綁定真正的內(nèi)存空間蟀俊，就需要用到動(dòng)態(tài)的分配內(nèi)存。
3.返回類型是 void* 類型订雾。void* 表示未確定類型的指針肢预。C,C++規(guī)定，void* 類型可以通過類型轉(zhuǎn)換強(qiáng)制轉(zhuǎn)換為任何其它類型的指針葬燎。
4.相關(guān)：
| 作用 | 代碼 |
|---|---|
| malloc函數(shù)原型 | extern void *malloc(unsigned int num_bytes); |
| malloc函數(shù)頭文件 | #include <stdlib.h>或者#include <malloc.h> |
謝謝提示误甚，這里用new建立也可以，還簡(jiǎn)單一些谱净。百度了一下malloc和new的區(qū)別，放這了擅威。https://www.cnblogs.com/shilinnpu/p/8945637.html
-
用到了typedef定義新的結(jié)構(gòu)體
大佬總結(jié)很詳細(xì)：https://blog.csdn.net/superhoy/article/details/53504472
代碼實(shí)現(xiàn)如下：
|
#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)); //強(qiáng)制轉(zhuǎn)換
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;
}
}
二叉樹節(jié)點(diǎn)總數(shù)目：
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);
}
二叉樹葉子節(jié)點(diǎn)數(shù)：
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)) ;
}
