数据结构——二叉树
目录
二叉树基础知识：
二叉树的结论：
二叉树的遍历：
先序：
中序：
后序：
基于二叉树遍历的其他操作：
统计结点个数：
统计叶子个数：
统计度为一节点个数：
统计度为二节点个数：
求二叉树深度：
1：
2：
从下往上打印指定元素的所有祖先：
二叉树的层次遍历：
层次输出第n个结点：
二叉树的建立：
已知空树：
直接返回树版：
c++引用返回树版（提前建立树，然后通过函数来改变树）：
先序+中序：
后序＋中序：
二叉树基础知识：
二叉树的结论：
二叉树的遍历：
先序：
中序：
后序：
基于二叉树遍历的其他操作：
统计结点个数：
统计叶子个数：
统计度为一节点个数：
统计度为二节点个数：
求二叉树深度：
1：
2：
从下往上打印指定元素的所有祖先：
二叉树的层次遍历：
层次输出第n个结点：
二叉树的建立：
已知空树：
直接返回树版：
#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;BiTree CreatBinTree();
void preorder( BiTree T );int main()
{BiTree T = CreatBinTree();preorder( T );return 0;
}
void preorder( BiTree T )
{if(T){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);}
}
BiTree CreatBinTree()
{char ch;BiTree T;scanf("%c",&ch);if(ch=='#') return NULL;T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;T->lchild=CreatBinTree();T->rchild=CreatBinTree();return T;
}c++引用返回树版（提前建立树，然后通过函数来改变树）：
#include <stdio.h>
#include <stdlib.h>
typedef char ElementType;
typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;void CreatBinTree(BiTree &T);
void preorder( BiTree T );int main()
{BiTree T;CreatBinTree(T);preorder( T );return 0;
}
void preorder( BiTree T )
{if(T){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);}
}
void CreatBinTree(BiTree &T)
{char ch;scanf("%c",&ch);if(ch=='#') T=NULL;else{(BiTree)malloc(sizeof(BiTNode));T->data=ch;CreatBinTree( T->lchild);CreatBinTree( T->rchild);}
}c语言指针版（和引用版底层逻辑一样，只不过c语言更呆）：
#include <stdio.h>
#include <stdlib.h>typedef char ElementType;
typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;void CreatBinTree(BiTree *T);
void preorder( BiTree T );int main()
{BiTree T;CreatBinTree(&T);preorder( T );return 0;
}
void preorder( BiTree T )
{if(T){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);}
}
void CreatBinTree(BiTree *T)
{char ch;scanf("%c",&ch);if(ch=='#') *T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=ch;CreatBinTree( &(*T)->lchilde);注意一下优先级->的优先级高于*，所以给*加（）CreatBinTree( &(*T)->rchilde);}
}除了已知空树的情况外，如果我们已知先序+中序或者后序加中序那么我们也可以唯一确定一棵树。
先序+中序：
先序是跟左右进行遍历，所以我们一定可以确定根节点是什么；
记录当前根节点，然后在中序数组中寻找根节点的位置，并记录这个位置；
因为中序是左根右进行遍历，所以根节点左边的都是左树，右边的都是右树；
递归进行除了左树和右数即可；
注意：1：creat函数的返回值是BiTree类型，最后要返回T；
2：递归不用想太多，只想一层的效果即可，往后每一层都是如此操作，直至最终到边界
（其实递归所传参数就是对应数组的起始位置以及数组长度，寻找位置传参即可，具体看代码后的图片，图片和代码结合着看）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;BiTree CreatBinTree(char *pre,char *in,int n );
void postorder( BiTree T );int main()
{BiTree T;char prelist[100];char inlist[100];int length;scanf("%s",prelist);scanf("%s",inlist);length=strlen(prelist);T=CreatBinTree(prelist,inlist, length);postorder( T );return 0;
}
void postorder( BiTree T )//后序输出二叉树
{if(T){postorder(T->lchild);postorder(T->rchild);printf("%c",T->data);}
}
BiTree CreatBinTree(char *pre,char *in,int n)
pre是先序数组，in是中序数组，n是树的节点数
随着递归的深入，先序数组和中序数组会不断缩小，直至节点个数<=0，递归结束
{BiTree T;int i;if(n<=0) return NULL;T=(BiTree)malloc(sizeof(BiTNode));T->data=pre[0];记录根节点for(i=0;in[i]!=pre[0];i++);寻找根节点的位置T->lchild=CreatBinTree(pre+1,in,i);//递归左树T->rchild=CreatBinTree(pre+i+1,in+1+i,n-i-1);//递归右树return T;
}
后序＋中序：
思路和先序+中序差不多，都是寻找根节点，然后递归左树和右树；
不同的是后序是左右根遍历，所以根节点在最后面；
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild;
}BiTNode,*BiTree;BiTree CreatBinTree(char *post,char*in,int n);
void preorder( BiTree T );int main()
{BiTree T;char postlist[100];char inlist[100];int length;scanf("%s",postlist);scanf("%s",inlist);length=strlen(postlist);T=CreatBinTree(postlist,inlist, length);preorder( T );return 0;
}
void preorder( BiTree T )
{if(T){printf("%c",T->data);preorder(T->lchild);preorder(T->rchild);}
}
BiTree CreatBinTree(char *post,char*in,int n )
post是后序数组，in是中序数组，n是树的节点数
随着递归的深入，后序数组和中序数组会不断缩小，直至节点个数<=0，递归结束
{BiTree T;int i;if(n<=0) return NULL;T=(BiTree)malloc(sizeof(BiTNode));T->data=post[n-1];记录根节点for(i=0;in[i]!=post[n-1];i++);寻找根节点的位置T->lchild=CreatBinTree(post,in,i);递归左树T->rchild=CreatBinTree(post+i,in+1+i,n-i-1);递归右树return T;
}
尚未完结。