考研复习（7）树的基本操作

这次是树的基本操作，包括生成树，求树深度，求叶子节点个数。。。
附上二叉树的几个重要性质及证明（考研必考）。
1.在二叉树的第i层至多有2^（i-1）个结点；
2.深度为k的二叉树至多有2^(k)-1 个结点；
3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1；（n=n0+n1+n2=n1+2n2+1）;
4.具有n哥节点的完全二叉树深度为【log2n】+1；
#include <stdio.h>
#include<stdlib.h>
#define maxSize 20
#define maxWidth 20
typedef struct node
{
char data;
struct node *left,*right;
}Btree;
Btree* createNode(char ch,Btree *l,Btree *r);
//先序遍历
void preOrder(Btree *BT)
{
if(BT!= NULL)
{
printf("%c",BT->data);
preOrder(BT->left);
preOrder(BT->right);
}
}
//中序遍历
void inOrder(Btree *BT)
{
if(BT!= NULL)
{
inOrder(BT->left);
printf("%c",BT->data);
inOrder(BT->right);
}
}
//后序遍历
void postOrder(Btree *BT)
{
if(BT!= NULL)
{
postOrder(BT->left);
postOrder(BT->right);
printf("%c",BT->data);
}
}
//从括号表达式生成树
void createTree(Btree **BT,char *str)//create a tree BT according by hollow function str
{




Btree *stack[maxSize],*p;
int top=-1,k,j=0;//top is the point of stack,k is the tab of son,j is the point of str;
char ch;
*BT=NULL;
ch=str[j];


while(ch!=NULL)
{
switch(ch)
{
case'(':top++;stack[top]=p;k=1;//left son,push to stack
break;
case')':top--;//pop stack
break;
case ',':k=2;//right son
break;
default:
/*p=(Btree *)malloc(sizeof(Btree));//set a node
if(!(p))
{
exit(0);
}
p->data=ch;
p->left=p->right=NULL;*/
p=createNode(ch,NULL,NULL);
if(*BT==NULL)//the root node
{
*BT=p;
}
else
{
switch(k)
{
case 1:stack[top]->left=p;
break;
case 2:stack[top]->right=p;
break;
default:
;
}


}
}
j++;
ch=str[j];//get next char
}
}
/*
void createTree(Btree **BT,char *str)
{
int j=0;//top is the point of stack,k is the tab of son,j is the point of str;
Btree *T;
char ch;
ch=str[j];
if(ch=='') *BT=NULL;
else
{
if(!(T=))


}
}
*/
//生成节点
Btree* createNode(char ch,Btree *l,Btree *r)
{
printf("Create now!\n");
Btree *p;
p=(Btree *)malloc(sizeof(Btree));//set a node
if(!(p))
{
exit(0);
}
p->data=ch;
p->left=l;
p->right=r;
return p;
}
//复制树
//copy a tree and return the new tree's point
Btree* copyTree(Btree *T)
{


Btree *newptl,*newptr,*newT;
if(!T) return NULL;
if(T->left!=NULL)
{
newptl=copyTree(T->left);


}
else newptl=NULL;
if(T->right!=NULL) newptr=copyTree(T->right);
else newptr=NULL;
newT=createNode(T->data,newptl,newptr);
//newT=createNode(T->data,NULL,NULL);
//newT=NULL;
return newT;
}
//层次法打印树
void disptree(Btree *BT)
{
Btree *stack[maxSize],*p;
int level[maxSize][2],top,n,i,width=4;
if(BT!=NULL)
{
printf("Display a tree by hollow means.\n");
top=1;
stack[top]=BT;//push root point to stack.
level[top][0]=width;
while(top>0)
{
p=stack[top];
n=level[top][0];
for(i=1;i<=n;i++)
printf(" ");
printf("%c",p->data);
for(i=n+1;i<maxWidth;i+=2)
printf("--");
printf("\n");
top--;
if(p->right!=NULL)
{
top++;
stack[top]=p->right;
level[top][0]=n+width;
level[top][1]=2;
}
if(p->left!=NULL)
{
top++;
stack[top]=p->left;
level[top][0]=n+width;
level[top][1]=1;
}
}




}
}
int TreeDepth(Btree *BT)//calculate the depth of tree
{
int leftDep,rightDep;
if(BT==NULL) return 0;
else
{
leftDep=TreeDepth(BT->left);
rightDep=TreeDepth(BT->right);
if(leftDep>rightDep) return(leftDep+1);
else return (rightDep+1);
}
}
int NodeCount(Btree *BT)//cout the nodes
{
if(BT==NULL) return 0;
else return (NodeCount(BT->left)+NodeCount(BT->right)+1);
}
int LeafCount(Btree *BT)//count the leafnodes
{
if(BT==NULL) return 0;
else if(BT->left==NULL&&BT->right==NULL) return 1;
else return (LeafCount(BT->left)+LeafCount(BT->right));
}
void PrintTree(Btree *BT)//print tree
{
if(BT!=NULL)
{
printf("%c",BT->data);
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintTree(BT->left);
if(BT->right!=NULL) printf(",");
PrintTree(BT->right);
printf(")");
}
}
}
main()
{
Btree *B,*C;
char *s="A(B(D,E(H,I)),C(G))";
createTree(&B,s);
printf("preOder:");
preOrder(B);
printf("\n");
printf("inOder:");
inOrder(B);
printf("\n");
printf("postOder:");
postOrder(B);
printf("\n");
printf("Display tree\n");
disptree(B);
printf("copy tree\n");
//disptree(B);
C=copyTree(B);
preOrder(C);
disptree(C);


printf("Deep: %d\n",TreeDepth(B));
printf("Sum of nodes: %d\n",NodeCount(B));
printf("Sum of leafnodes: %d\n",LeafCount(B));
PrintTree(B);
printf("\nHello,world!");
}