C语言 树与二叉树基础部分

树的基础概念

一、树的特点：
1.有且仅有一个节点没有前驱结点，即根结点；
2.除了根结点外，每个结点有且仅有一个直接前驱结点；
3.包括根结点在内，每个结点可以有多个后继结点。

二、基本术语名词
结点的度：该结点拥有的子树的数目。
树的度：树中结点度的最大值。
叶结点：度为0的结点。
分支节点：度非0的结点。
树的层次：根结点为第1层，若某层节点在第i层，则其孩子结点（若存在）为第i+1层。
树的深度/高度：树中结点所处的最大层次数。
路径：路径长度等于路径结点树-1.路径是从di到dj结点的一条结点序列。从根结点到树中其余结点均分别存在一条唯一路径。
祖先与子孙：一个结点的祖先是从根结点到该结点路径上所经过的所有结点；而一个结点的子孙则是以该结点为根的子树上的所有其他结点。
森林：m>=0颗不想交的树组成的树的集合。

判断：
1.度为2的树是二叉树？（×）
2.度为2的有序树是二叉树？（×）

图中没有区分左右子树，不是二叉树。
结论：子树有严格的左右之且度<=2的树是二叉树。

注意：具有三个节点的二叉树有几种形态？
具有三个结点的树有几种形态？

二叉树的性质

1.具有n个结点的非空二叉树共有n-1个分支（边）。
2.非空二叉树的第i层最多有2^(i-1)个结点。（i>=0）
3.深度为h的非空二叉树最多有2^h-1个结点。
4.若非空二叉树有n0个叶结点，有n2个度为2的结点，则n0=n2+1。

证明：
n=n0+n1+n2
设分支数目为B，则根据性质1：
B=n-1
这些分支来自于度为1和度为2的结点：
B=n1+2n2
则根据2和3式：n-1=n1+2n2
即n=1+n1+2n2
=n0+n1+n2
因此：n0=n2+1
推论：n0=n2+2n3+3n4+……+（m-1）nm+1

5.具有n个结点的非空完全二叉树的深度为：h=logn+1；
6.顺序存储结构中：结点i的父节点编号：（i-1）/2;
结点i的左孩子结点：2i+1；右孩子：2i+2;

数组存储方式只适用于完全二叉树和满二叉树，其他二叉树会造成内存的浪费。

二叉树的遍历

树的遍历一般是说在链式结构下的遍历，那么此时我们需要定义一个结构体：

typedef struct node
{int val;struct node* left;struct node* right;
}BTNode;
typedef BTNode* BTNodeptr;

前序遍历

void Preorder(BTNodeptr t)
{if(t==NULL)return;visit(t);//访问结点tPreorder(t->left);Preorder(t->right);
}

中序遍历

void Inorder(BTNodeptr t)
{if(t==NULL)return;Inorder(t->left);visit(t);Inorder(t->right);
}

后序遍历

void Postorder(BTNodeptr t)
{if(t==NULL)return;Postorder(t->left);Postorder(t->right);visit(t);
}

前中后序遍历都是深度优先遍历（DFS），而接下来的层序遍历则是广度优先遍历（BFS）；

层序遍历

这种遍历方法没有用到递归，而是使用了一个队列：
方法是：从根结点开始，父节点先入队列，再出队列并输出，同时将父节点的两个子节点（若存在）入队。再取出队头元素，同时将队头元素的两个子节点（若存在）入队。直至队列为空，输出的序列就是层序遍历的结果啦~

#define MAX 100
void Treeorder(BTNodeptr t)
{BTNode* queue[MAX];int Front=0;int Rear=MAX-1;int Count=0;if(t){Rear=(Rear+1)%MAX;queue[Rear]=t;Count++;}BTNode* front;while(Count!=0){front=queue[Front];Front=(Front+1)%MAX;Count--;visit(front);if(front->left){Rear=(Rear+1)%MAX;queue[Rear]=front->left;Count++;}if(front->right){Rear=(Rear+1)%MAX;queue[Rear]=front->right;Count++;}}
}

根据遍历结果恢复二叉树

前序+中序（√）
后序+中序（×）
前序+后序（×）
因为前序和后序分别一致的两颗树，也有可能结构不同，比如：

两颗树前序序列都为：ABDC
后序序列都为DBCA,
但很明显，结构不一样

已知前（后）序序列和中序序列，恢复二叉树：
在前（后）序序列中确定根，在中序序列中区分左右。

二叉树的创建

第一种

输入：A B D ^ ^ E J ^ ^ ^ C F ^ I ^ ^ G ^ ^
第一个字符表示根结点字符，后面的每一个字符表示前面字符的孩子结点字符，先输入的是左孩子，后输入右孩子，^表示没有孩子。
那么如何根据上述输入构造出如下的二叉树呢？

这个输入是一个前序遍历结果，那创建这个树的思想其实也是前序创建，也就是说访问到一个值，那么先创建这个子树的根结点，再创建它的左子树节点，再创建右子树结点，直到遇到^，返回NULL即可。
伪代码体现：

读入字符ch
if(ch==‘^’)
不创建结点，返回NULL
else
创建子树根结点
创建该根结点的左子树
创建该根结点的右子树

这是创建好树以后，按照前中后序遍历打印结果：

BTNodeptr createtree();
int main()
{BTNodeptr root;root=createtree();Preorder(root);printf("\n");Inorder(root);printf("\n");Postorder(root);return 0;
}
BTNodeptr createtree()
{BTNodeptr p;char ch;ch=getchar();if(ch=='^')return NULL;else{p=(BTNodeptr)malloc(sizeof(BTNodeptr));p->val=ch;p->left=createtree();p->right=createtree();return p;}
}

第二种

输入：
5
ABC
BDE
CFG
EJ^
F^I
先输入分支节点个数（非叶子结点），按层次从左到右依次输入父节点和孩子结点，若孩子结点不存在，则以^字符表示
那么如何根据上述输入构造如下二叉树呢？

我们有两种方法来解决：第一种用到队列，思想类似于层序遍历，因为输入形式为：根 左 右，因此根入队，根再出队，根的左右子节点入队；输入下一行时，判断队头是不是这一行的第一个字符，如果不是，说明队头元素是一个叶子结点；如果是，那么队头出队，这一行的后两个元素入队（非^时入队），并且链接到队头元素的左右子树上。

BTNodeptr createtree1();
int main()
{BTNodeptr root;root=createtree1();Preorder(root);printf("\n");Inorder(root);printf("\n");Postorder(root);return 0;
}
BTNodeptr createtree1()
{BTNodeptr root=NULL;BTNodeptr queue[MAX];BTNodeptr p=NULL;//这个用于取队头元素int Front=0,Rear=MAX-1;char str[4];//存储每一行输入的三个元素int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",str);if(root==NULL){root=(BTNodeptr)malloc(sizeof(BTNode));root->val=str[0];root->left=NULL;root->right=NULL;p=root;}else//这一步用于找头结点{do{p=queue[Front];Front=(Front+1)%MAX;} while (p->val!=str[0]);}if(str[1]!='^'){p->left=(BTNodeptr)malloc(sizeof(BTNode));p->left->left=NULL;p->left->right=NULL;p->left->val=str[1];Rear=(Rear+1)%MAX;queue[Rear]=p->left;}if(str[2]!='^'){p->right=(BTNodeptr)malloc(sizeof(BTNode));p->right->left=NULL;p->right->right=NULL;p->right->val=str[2];Rear=(Rear+1)%MAX;queue[Rear]=p->right;}}return root;
}

后三行为按照前中后序遍历输出的结果↑。

BUT/HOWEVER/NEVERTHELESS……！！！！这种方法存在一个很大的缺陷就是：
输入的时候只能按照层序来，也就是说，刚刚我们的输入顺序是：
ABC
BDE
CFG
EJ^
F^I
一旦这个顺序发生变化，这种算法就没办法实现了，比如：
ABC
CFG
F^I
BDE
EJ^
为什么不可以呢？原因就在于队列。当我们读入第一行后，队列中的元素为：
读第二行是时，我们发现队头元素不是C，于是继续向后查找，发现第二个元素是C，然后将C出队，C的子节点入队：
我们此时发现：B出队，但是在输入的第四行，还有B！但是此时B已经不在队列里了。因此，如果输入子树的顺序不是按照层序顺序来进行，那就需要另外定义一个查找函数find，用于在已经构建好的树中查找父节点。

BTNodeptr createtree2();
BTNodeptr find(BTNodeptr root,char ch);
int main()
{BTNodeptr root;root=createtree2();Preorder(root);printf("\n");Inorder(root);printf("\n");Postorder(root);return 0;
}
BTNodeptr createtree2()
{BTNodeptr root=NULL;BTNodeptr p=NULL;//这个用于表示每一步的父节点char str[4];//存储每一行输入的三个元素int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",str);if(root==NULL){root=(BTNodeptr)malloc(sizeof(BTNode));root->val=str[0];root->left=NULL;root->right=NULL;p=root;}else//这一步用于找头结点{p=find(root,str[0]);}if(str[1]!='^'){p->left=(BTNodeptr)malloc(sizeof(BTNode));p->left->left=NULL;p->left->right=NULL;p->left->val=str[1];}if(str[2]!='^'){p->right=(BTNodeptr)malloc(sizeof(BTNode));p->right->left=NULL;p->right->right=NULL;p->right->val=str[2];}}return root;
}
BTNodeptr find(BTNodeptr root,char ch)
{BTNodeptr p=NULL;if(root!=NULL){if(root->val==ch)p=root;else{p=find(root->left,ch);if(p==NULL)p=find(root->right,ch);}   }return p;
}

改进的地方，就是把找每一行头结点的那一步，从在队列里找，变成了在已有的树中找。同时，find函数也是一个比较基础的树操作，大致和中序遍历的思想一致，先判断头结点的值是否和要找的字符一致，如果不一致，再在左子树里找，如果没找到，再在右子树里找。

二叉树的典型操作有很多：
检查二叉树是否为空
在二叉树中查找给定元素
获得二叉树中包含给定元素路径
在二叉树中插入一个元素
从二叉树中删除一个元素
获得二叉树的高度
获得二叉树的节点数目
获得二叉树叶节点的数目
遍历二叉树
拷贝二叉树
删除二叉树
现在现在这里介绍加粗的这几种，剩下的插入、删除、结点路径这几种留在一会儿的搜索二叉树（二叉查找树）中介绍。

二叉树的其他典型操作

查找指定元素（一般二叉树）

BTNodeptr find(BTNodeptr root,char ch)
{BTNodeptr p=NULL;if(root!=NULL){if(root->val==ch)p=root;else{p=find(root->left,ch);if(p==NULL)p=find(root->right,ch);}   }return p;
}

二叉树的高度（深度）

int height(BTNodeptr p)
{if(p==NULL)return 0;else return 1+max(height(p->left),height(p->right));
}

二叉树的拷贝

BTNodeptr copy(BTNodeptr src)
{BTNodeptr obj;if(src==NULL)obj=NULL;else{obj=(BTNodeptr)malloc(sizeof(BTNode));obj->val=src->val;obj->left=copy(src->left);obj->right=copy(src->right);}return obj;
}

拷贝的时候按照前中后序拷贝都可以，但是二叉树销毁，就必须按照后序了：

二叉树的销毁

void destroy(BTNodeptr p)
{if(p!=NULL){destroy(p->left);destroy(p->right);free(p);p=NULL;}
}

二叉树的节点个数

int TreeSize(BTNodeptr root)
{return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}

第k层的节点个数

可以先拆解一下问题：
递归子问题：
第k层结点个数=左子树第k-1层结点个数+右子树第k-1层结点个数
最小子问题：
遍历到空节点：返回0；该结点不为空但是该结点是叶子结点即k==1

int levelnum(BTNodeptr p,int k)
{if(p==NULL)return 0;if(p!=NULL&&k==1)return 1;return levelnum(p->left,k-1)+level(p->right,k-1);
}

以这一棵树为例，我们测试一下各个层的节点个数：
完全正确。

二叉树叶子结点个数

这个题和上一道题趋同，我们先来分解一下问题：
遍历到空节点：返回0
遍历到叶子结点（左右子树都为NULL）：返回1
叶子结点个数=左子树的叶子节点个数+右子树的叶子结点个数
写起来：

int leaf(BTNodeptr root)
{if(root==NULL)return 0;if(root->left==NULL&&root->right==NULL)return 1;return leaf(root->left)+leaf(root->right);
}

还是刚刚那个二叉树，我们检测一下叶子结点个数对不对：
完全正确。

搜索二叉树

也叫二叉查找树，特点为：
若根结点的左子树不空，则左子树上所有结点都小于根结点；若右子树不为空，则右子树上结点值都小于根结点。每一颗子树上也符合上述特点。

逐点插入法

利用这个方法可以建立起搜索二叉树，核心在于和根结点比较，值比根结点大，往右子树插入，比根结点小，插到左子树，相等的话，根据具体情况做具体操作。

现可用递归和非递归两种方式来构建逐点插入法：

递归：

BTNodeptr insert(BTNodeptr p,int item);
int main()
{BTNodeptr root=NULL;int i,item;for(i=0;i<10;i++){scanf("%d",&item);root=insert(root,item);}Inorder(root);printf("\n");return 0;
}
BTNodeptr insert(BTNodeptr p,int item)
{if(p==NULL){p=(BTNodeptr)malloc(sizeof(BTNode));p->val=item;p->left=p->right=NULL;}else if(item<p->val){p->left=insert(p->left,item);}else if(item>p->val){p->right=insert(p->right,item);}else{//如果相等，根据具体要求做。}return p;
}

看看测试结果：

按照中序遍历输出，序列递增。

非递归：

void insert1(int item);
BTNodeptr root=NULL;
int main()
{int i,item;for(i=0;i<10;i++){scanf("%d",&item);insert1(item);}Inorder(root);printf("\n");return 0;
}
void insert1(int item)
{BTNodeptr new=(BTNodeptr)malloc(sizeof(BTNode));new->val=item;new->left=new->right=NULL;if(root==NULL){root=new;return;}BTNodeptr cur=root;while(1){if(item<cur->val){if(cur->left==NULL){cur->left=new;     break;       }elsecur=cur->left;}else if(item>cur->val){if(cur->right==NULL){cur->right=new;break;}         elsecur=cur->right;}  else{//具体情况具体判断}}return;
}

真心建议各位朋友都用非递归，调试起来也更方便明了，递归的话，调试的时候你的脑子是真跟不上F11的跳跃……

查找

BTNodeptr search(BTNodeptr p,int n)
{BTNodeptr cur=p;while(cur!=NULL){if(n>cur->val)cur=cur->right;else if(n<cur->val)cur=cur->left;elsereturn cur;}return NULL;
}

到指定节点的路径

搜索二叉树和普通二叉树的这个算法区别还是很大的，因为搜索二叉树的特殊性质：

搜索二叉树：

void searchBST(BTNodeptr p,int n)
{BTNodeptr cur=p;while(cur!=NULL){if(n>cur->val){printf("%d ",cur->val);cur=cur->right;}else if(n<cur->val){printf("%d ",cur->val);cur=cur->left;            }else{printf("%d ",cur->val);break;}}
}

在主函数中测试一下：

void searchBST(BTNodeptr p,int n);
BTNodeptr root=NULL;
int main()
{int i,item;for(i=0;i<10;i++){scanf("%d",&item);insert1(item);}searchBST(root,100);printf("\n");searchBST(root,90);printf("\n");searchBST(root,80);printf("\n");searchBST(root,70);return 0;
}
void searchBST(BTNodeptr p,int n)
{BTNodeptr cur=p;while(cur!=NULL){if(n>cur->val){printf("%d ",cur->val);cur=cur->right;}else if(n<cur->val){printf("%d ",cur->val);cur=cur->left;            }else{printf("%d ",cur->val);break;}}
}

我们先用Insert函数创建了一个有10个结点的二叉树：
我们看看打印的祖先结点：

完全正确。
其实这个算法就是把刚刚的查找部分改了改。
在每一次判断大小的时候加了一个print语句。

普通二叉树：
这个时候也要用到遍历，但是只能是前序遍历。而且这时候要借助一个栈来存放祖先节点。

void preorder(BTNodeptr p,int item)
{if(t!=NULL){push(t);if(item==t->data)//弹出栈中所有元素preorder(t->left);preorder(t->right);pop();
}

解释一下，就是我把一个子树的根结点放在了栈里，如果在这个子树的左子树里找到了目标，那么栈中所有元素就是路径；如果左子树里没有就转战右子树。如果两个子树都没找到，那说明这颗子树不行，“连根拔起”，也就是把刚刚放入栈中的子树根节点剔除栈。

搜索二叉树还有几个比较经典的题，比如:表达式树、词频统计，这个我们第五次作业里有，在下一篇文章中再整理。