本文共 5972 字,大约阅读时间需要 19 分钟。
树 :一种非线性数据结构
树的应用:
操作系统中:用树表示文件目录组织结构
编译系统中: 用树表示源程序语法结构
相关概念常见表示方法:
树有且仅有一个根节点
树的结构定义是一个递归的定义
树可以看做一个集合,每个集合下面又有很多子集合,所以单节点与子树之间可以表示为 T={跟结点,左孩子,右孩子}
-实例:T1 ={A,B,C}
当然,树还可以用括号表示,这样更加容易看
还可以通过图形来表示:
二叉树:树的度为2的二叉树(结点最大度为2)。
1、满二叉树:
深度为k且含有2^k-1个结点。看图很容易理解。2、完全二叉树:
每个结点都与所对应的完全二叉树一 一对应,叶子几点只可能出现在最后两层。1、前序遍历:ABDGHCEIF(规则是先是根结点,再前序遍历左子树,再前序遍历右子树)
2、中序遍历:GDHBAEICF(规则是先中序遍历左子树,再是根结点,再是中序遍历右子树)
3、后序遍历:GHDBIEFCA(规则是先后序遍历左子树,再是后序遍历右子树,再是根结点)
typedef struct BTree{ char data; struct BTree *lChild; //左孩子 struct BTree *rChild; //右孩子}BinTree;
输入顺序是先遍历根结点,再遍历左右结点,也就是先序遍历,然后重复把左右孩子当做根节点,重复上诉过程,这就是一个递归过程。这里用“#”表示孩子为空,所以下图中B就表示叶子结点,而C没有左孩子。
这里要求要通过先序遍历输入各结点,如果要创建这个树应该输入:AB##C#D##
BinTree *CreateTree(BinTree *p){ char ch; scanf("%c",&ch); if (ch == '#') { return NULL; } p=(BinTree *)malloc(sizeof(BinTree)); p->data = ch; p->lChild = CreateTree(p->lChild); //递归左孩子 p->rChild = CreateTree(p->rChild); //递归又孩子 return p;}
这里有碰到个问题,才发现自己对scanf还是没理解深刻。明明我只输入了(一次性输入了所有字符),char型的ch一次也只能接收一个字符,那么为什么可以实现二叉树的创建呢?
原来scanf输入是把所有的字符都存入了缓冲区,每调用一次scanf就从缓冲区读入一个字符,如果读到回车,scanf就结束。
通过一个程序验证一下:
#includeint main(){ char a; char b; char c; printf("input a:\n"); scanf("%c",&a); //如果这里输入abc,则接下来的scanf会分别读取b , c //getchar(); printf("input b:\n"); scanf("%c",&b); printf("input c:\n"); scanf("%c",&c); printf("%c",a); printf("%c",c); return 0;}
根结点->左孩子->右孩子
void PreOrder(BinTree *T){ if(T) { printf("%c",T->data); //先打印数据,也就是遍历根节点 PreOrder(T->lChild); PreOrder(T->rChild); }}
左孩子->根结点->右孩子
void MidOrder(BinTree *T){ if (T) { MidOrder(T->lChild); printf("%c",T->data); MidOrder(T->rChild); }}
左孩子->右孩子->根结点
void LastOrder(BinTree *T){ if(T) { LastOrder(T->lChild); LastOrder(T->rChild); printf("%c",T->data); }}
void Copy(BinTree *T,BinTree **newTree) //二级指针存放指针的地址{ if(T == NULL) { *newTree = NULL; return ; } else { *newTree = (BinTree *)malloc(sizeof(BinTree)); (*newTree)->data = T->data; Copy(T->lChild,&(*newTree)->lChild); //注意带*号变量指向成员时要加括号 Copy(T->rChild,&(*newTree)->rChild); //注意第二个参数穿的是地址,所以需要在前面加取地址符号 & }}
这里用了二级指针存放了指针地址,如果不用二级指针,则需要用返回值的形式来返回新树的地址。如下:程序改为了:
BinTree *Copy(BinTree *T) //只需要传入T即可,直接返回一个新的地址{ if(T == NULL) { newTree = NULL; return newTree; } else { newTree = (BinTree *)malloc(sizeof(BinTree)); newTree->data = T->data; newTree->lChild=Copy(T->lChild); newTree->rChild=Copy(T->rChild); } return newTree;}
int Sumleaf(BinTree *T) //求叶结点总数{ int sum=0,m,n; if (T) { if ((!T->lChild) && (!T->rChild)) { sum++; } m=Sumleaf(T->lChild); sum+=m; n=Sumleaf(T->rChild); sum+=n; } return sum;}int Depth(BinTree *T) //树的深度{ int dep=0,dep1,depr; if (!T) { dep=0; } else //分别对左右孩子遍历,看谁的层数大就取谁的值 { dep1=Depth(T->lChild); depr=Depth(T->rChild); dep=1+(dep1>depr ? dep1:depr); } return dep;}
在这个过程中,遇到最大问题就是在复制二叉树那段代码。因为对二级指针操作不是太熟练,所以递归的时候开始的时候老是提示错误:
expected ‘struct BinTree **’ but argument is of type ‘struct BTree *’
后来不断检查才知道,因为二级指针要传的是地址,第一次传了地址,但是第二次没有加取地址符。
带*号变量应该正确的指向方法应该是:(*p)->a
而不应该是*p->a
#include#include //for malloc typedef struct BTree{ char data; struct BTree *lChild; struct BTree *rChild;}BinTree;BinTree *CreateTree(BinTree *p){ char ch; scanf("%c",&ch); if (ch == '#') //# standard for the leaf node { return NULL; } p=(BinTree *)malloc(sizeof(BinTree)); p->data = ch; p->lChild = CreateTree(p->lChild); p->rChild = CreateTree(p->rChild); return p;}int Sumleaf(BinTree *T){ int sum=0,m,n; if (T) { if ((!T->lChild) && (!T->rChild)) { sum++; } m=Sumleaf(T->lChild); sum+=m; n=Sumleaf(T->rChild); sum+=n; } return sum;}int Depth(BinTree *T){ int dep=0,dep1,depr; if (!T) { dep=0; } else { dep1=Depth(T->lChild); depr=Depth(T->rChild); dep=1+(dep1>depr ? dep1:depr); } return dep;}void PreOrder(BinTree *T){ if(T) { printf("%c",T->data); PreOrder(T->lChild); PreOrder(T->rChild); }}void MidOrder(BinTree *T){ if (T) { MidOrder(T->lChild); printf("%c",T->data); MidOrder(T->rChild); }}void LastOrder(BinTree *T){ if(T) { LastOrder(T->lChild); LastOrder(T->rChild); printf("%c",T->data); }}void Copy(BinTree *T,BinTree **newTree) { if(T == NULL) { *newTree = NULL; return ; } else { *newTree = (BinTree *)malloc(sizeof(BinTree)); (*newTree)->data = T->data; Copy(T->lChild,&(*newTree)->lChild); Copy(T->rChild,&(*newTree)->rChild); }}int main(){ BinTree *Tree; BinTree *newtree; printf("请以前序遍历的方式输入扩展二叉树,用“#”表示空结点:\n"); Tree=CreateTree(Tree); printf("前序遍历:\n"); PreOrder(Tree); printf("\n中序遍历:\n"); MidOrder(Tree); printf("\n后序遍历:\n"); LastOrder(Tree); printf("\n叶结点总数:%d\n",Sumleaf(Tree)); printf("\n树的层数:%d\n",Depth(Tree)); Copy(Tree,&newtree); //如果Copy()函数是返回值的形式调用应该如此: //newtree=Copy(Tree); printf("\n复制树后序遍历:\n"); LastOrder(newtree); //用来检验是否成功 return 0;}
测试:
要创建如下二叉树,并且输出:先/中/后序遍历结果输入(先序遍历输入):AB##C#D##
测试结果:本文参考: