二叉樹的操作

二叉樹的操作

#include <stdlibh>
#include <stdioh>
#define queuesize
#define null
typedef char datatype;
typedef struct node{
　　datatype data;
　　struct node *lchild*rchild;
　}bintnode;//定義二叉鏈表結點結構
typedef bintnode *bintree;//定義二叉鏈表指針類型

typedef struct{
　　int frontrear;
　　bintree data[queuesize];//循環隊列元素類型為二叉鏈表結點指針
　　int count;
　}cirqueue;//循環隊列結構定義

main()//主函數
　{//建立二叉樹的二叉鏈表表示並進行先序遍歷中序遍歷後序遍歷和按層次遍歷
　　//求出所有葉子和結點總數
　　bintree t=null;
　　int n;
　　printf(please input nodes of bintree:\n);
　　createbintree(&t);//建立二叉鏈表

　　printf(the preorder is:);
　　preorder(t);//對二叉樹t進行先序遍歷
　　printf(\n);

　　printf(the inorder is:);
　　inorder(t);//對二叉樹t進行中序遍歷

　　printf(\nthe postorder is:);
　　postorder(t);//對二叉樹t進行後序遍歷

　　printf(\nthe leverorder is:);
　　leverorder(t);//對二叉樹t進行按層次遍歷

　　n=leave(t);// 求出二叉樹的葉子數n

　　printf(\nthe leave of bintree is: %dn);//打印二叉樹的葉子總數
　　if (n){//當葉子數不為
　　　　printf(\nthe list of leave is:);
　　　　leavelist(t);//輸出所有的葉子
　　　}
　　else
　　　　printf(\nno leave!);//輸出無葉子（即空樹）信息
　　printf(\nthe nodes of bintree is: %d\nnodes(t));//輸出二叉樹的總結點數
　}

createbintree(bintree *t)
　{//輸入二叉樹的先序遍歷序列創建二叉鏈表
　　char ch;
　　if ((ch=getchar())== )//如果讀入空格字符創建空樹
　　　　　*t=null;
　　else{
　　　　　*t=(bintnode*)malloc(sizeof(bintnode));//申請根結點*t空間
　　　　　(*t)>data=ch;//將結點數據ch放入根結點的數據域
　　　　　createbintree(&(*t)>lchild);//建左子樹
　　　　　createbintree(&(*t)>rchild);//建右子樹
　　　　}//end of if
　}//end of creatbintree

preorder(bintree t)
　{//對二叉樹進行先序遍歷
　　if (t){
　　　printf(%ct>data);
　　　preorder(t>lchild);
　　　preorder(t>rchild);
　　}//end of if
　}//end of preorder
　
inorder(bintree t)
　{//對二叉樹進行中序遍歷
　　if (t){
　　　　　　　inorder(t>lchild);
　　　　　　　printf(%ct>data);
　　　　　　　inorder(t>rchild);
　　　　　}//end of if
　}//end of inorder

postorder(bintree t)
　{//對二叉樹進行後序遍歷
　　if (t){
　　　　　　postorder(t>lchild);
　　　　　　postorder(t>rchild);
　　　　　　printf(%ct>data);
　　　　　}//end of if
　}//end of postorder

error(char *message)
　{//出錯時調用的返回出錯信息終止程序運行的函數
　　　fprintf(stderrerror:%s\nmessage);
　　　exit();
　}

leverorder(bintree t)
　{
　　cirqueue *q;
　　bintree p;
　　q=(cirqueue*)malloc(sizeof(cirqueue));//申請循環隊列空間
　　q>rear=q>front=q>count=;//將循環隊列初始化為空
　　q>data[q>rear]=t;q>count++;q>rear=(q>rear+)%queuesize;//將根結點入隊
　　while (q>count)//若隊列不為空做以下操作
　　　　if (q>data[q>front]){//當隊首元素不為空指針做以下操作
　　　　　　p=q>data[q>front];//取隊首元素*p
　　　　　　printf(%cp>data);//打印*p結點的數據域信息
　　　　　　q>front=(q>front+)%queuesize;q>count;//隊首元素出隊
　　　　　　if (q>count==queuesize)//若隊列為隊滿則打印隊滿信息退出程序的執行
　　　　　　　　　error(the queue full!);
　　　　　　else{//若隊列不滿將*p結點的左孩子指針入隊
　　　　　　　　　q>count++;q>data[q>rear]=p>lchild;
　　　　　　　　　q>rear=(q>rear+)%queuesize;
　　　　　　　　}//enf of if
　　　　　　if (q>count==queuesize)//若隊列為隊滿則打印隊滿信息退出程序的執行
　　　　　　　　　error(the queue full!);
　　　　　　else{//若隊列不滿將*p結點的右孩子指針入隊
　　　　　　　　　　q>count++;q>data[q>rear]=p>rchild;
　　　　　　　　　　q>rear=(q>rear+)%queuesize;
　　　　　　　　}//end of if
　　　　　}//end of if
　　　　else{//當隊首元素為空指針將空指針出隊
　　　　　　　q>front=(q>front+)%queuesize;q>count;}
　}//end of leverorder

int leave(bintree t)
　{//求以t為樹根的二叉樹的葉子總數
　　if (!t)//若根結點為
　　　return ;//返回葉子數
　　else//若根結點非空
　　　if ((t>lchild==null)&&(t>rchild==null))//若根結點的左右孩子都為空
　　　　　return ;//返回葉子數
　　　else //根結點的左右孩子有個不為空
　　　　　return(leave(t>lchild)+leave(t>rchild));
　　　　　　　//葉子數為左子樹的葉子數加右子樹中的葉子數
　}

leavelist(bintree t)
　{
　　if (t){
　　　　leavelist(t>lchild);//輸出左子樹中的所有葉子
　　　　if ((t>lchild==null)&&(t>rchild==null))
　　　　　　//若根結點為葉子則輸出葉子的數據域信息
　　　　　　printf(%ct>data);
　　　　　　leavelist(t>rchild);//輸出右子樹中的所有葉子
　　　　　}//end of if
　}//end of inorder

int nodes(bintree t)
　{
　　if (!t)//若二叉樹為空樹
　　　　return ;//返回結點數
　　else //若二叉樹非空
　　　　return nodes(t>lchild)+nodes(t>rchild)+;
　　　　　　//二叉樹的結點總數為左右子樹的結點總數加上（根結點）
　}//end of node

From:http://tw.wingwit.com/Article/program/sjjg/201311/23277.html