本博客前面文章已对树与二叉树有过简单的介绍，本文主要是重点介绍有关二叉树的一些具体操作与应用

阅读本文前，可以先参考本博客



各种基本算法实现小结（三）—— 树与二叉树

和

各种基本算法实现小结（二）—— 堆 栈

二叉树

深度层数、叶子数、节点数和广度优先算法

以及树的先序、中序、后序的递归与非递归（深度优先）

测试环境：VS2008（C）

<br /> #include "stdafx.h"<br /> #include <stdlib.h><br /> #include <malloc.h><br /> #define DataType char<br /> int d_tree=0; /* tree's depth */<br /> int l_tree=0; /* tree's leaf */<br /> int n_tree=0; /* tree's node */<br /> /**************************************/<br /> /******** 树的结构定义 ********/<br /> /**************************************/<br /> struct _tree<br /> {<br /> DataType data;<br /> struct _tree *lchild;<br /> struct _tree *rchild;<br /> };<br /> typedef struct _tree tree, *ptree;<br /> /**************************************/<br /> /******** 栈的结构定义 ********/<br /> /**************************************/<br /> struct _node<br /> {<br /> ptree pt;<br /> struct _node *next;<br /> };<br /> typedef struct _node node, *pnode;<br /> struct _stack<br /> {<br /> int size;<br /> pnode ptop;<br /> };<br /> typedef struct _stack stack, *pstack;<br /> /**************************************/<br /> /******** 堆的结构定义 ********/<br /> /**************************************/<br /> struct _queue<br /> {<br /> pnode front;<br /> pnode rear;<br /> };<br /> typedef struct _queue queue, *pqueue;<br /> /**************************************/<br /> /******** 栈的数据操作 ********/<br /> /**************************************/<br /> pstack init_stack()<br /> {<br /> pnode pn=NULL;<br /> pstack ps=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> ps=(pstack)malloc(sizeof(stack));<br /> pn->pt=NULL;<br /> pn->next=NULL;<br /> ps->ptop=pn;<br /> return ps;<br /> }<br /> int empty_stack(pstack ps)<br /> {<br /> if(ps->ptop->next==NULL)<br /> return 1;<br /> else<br /> return 0;<br /> }<br /> void push_stack(pstack ps, ptree pt) /* flag for post tree: 0 for lchild; 1 for rchild */<br /> {<br /> pnode pn=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->pt=pt;<br /> pn->next=ps->ptop;<br /> ps->ptop=pn;<br /> }<br /> ptree pop_stack(pstack ps)<br /> {<br /> ptree pt=NULL;<br /> pnode pn=NULL;<br /> if(!empty_stack(ps))<br /> {<br /> pn=ps->ptop;<br /> ps->ptop=ps->ptop->next;<br /> pt=pn->pt;<br /> free(pn);<br /> }<br /> return pt;<br /> }<br /> ptree gettop_stack(pstack ps)<br /> {<br /> if(!empty_stack(ps))<br /> return ps->ptop->pt;<br /> }<br /> /**************************************/<br /> /******** 堆的数据操作 ********/<br /> /**************************************/<br /> queue init_queue()<br /> {<br /> pnode pn=NULL;<br /> queue qu;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->pt=NULL;<br /> pn->next=NULL;<br /> qu.front=qu.rear=pn; /* init: pn is header */<br /> return qu;<br /> }<br /> int empty_queue(queue &qu)<br /> {<br /> if(qu.front==qu.rear)<br /> return 1;<br /> else<br /> return 0;<br /> }<br /> void en_queue(queue &qu, ptree pt)<br /> {<br /> pnode pn=NULL;<br /> pn=(pnode)malloc(sizeof(node));<br /> pn->pt=pt;<br /> pn->next=qu.rear->next;<br /> qu.rear->next=pn;<br /> qu.rear=qu.rear->next;<br /> }<br /> ptree de_queue(queue &qu)<br /> {<br /> ptree pt=NULL;<br /> pnode pn=NULL;<br /> if(!empty_queue(qu))<br /> {<br /> pn=qu.front->next;<br /> if(pn==qu.rear) /* qu is null: qu.front==qu.rear */<br /> qu.rear=qu.front;<br /> else<br /> qu.front->next=qu.front->next->next;<br /> pt=pn->pt;<br /> free(pn);<br /> }<br /> return pt;<br /> }<br /> /**************************************/<br /> /******** 树的数据操作 ********/<br /> /**************************************/<br /> ptree init_tree()<br /> {<br /> ptree pt=NULL;<br /> pt=(ptree)malloc(sizeof(tree));<br /> pt->data='0';<br /> pt->lchild=NULL;<br /> pt->rchild=NULL;<br /> return pt;<br /> }<br /> ptree create_tree()<br /> {<br /> char ch;<br /> ptree pt=NULL;</p> <p> scanf("%c", &ch);<br /> getchar();<br /> if(ch==' ')<br /> return NULL;<br /> else<br /> {<br /> pt=(ptree)malloc(sizeof(tree));<br /> pt->data=ch;<br /> pt->lchild=create_tree();<br /> pt->rchild=create_tree();<br /> }<br /> return pt;<br /> }<br /> int depth_tree(ptree pt)<br /> {<br /> int l_len, r_len;<br /> ptree p=pt;<br /> if(p==NULL)<br /> return 0;<br /> else<br /> {<br /> l_len=depth_tree(p->lchild);<br /> r_len=depth_tree(p->rchild);<br /> return l_len>r_len?(l_len+1):(r_len+1);<br /> }<br /> }<br /> void leaf_tree(ptree pt)<br /> {<br /> ptree p=pt;<br /> if(p->lchild==NULL && p->rchild==NULL)<br /> l_tree++;<br /> else<br /> {<br /> leaf_tree(p->lchild);<br /> leaf_tree(p->rchild);<br /> }<br /> }<br /> void node_tree(ptree pt)<br /> {<br /> ptree p=pt;<br /> if(p!=NULL)<br /> {<br /> n_tree++;<br /> node_tree(p->lchild);<br /> node_tree(p->rchild);<br /> }<br /> }<br /> void print_pretree(ptree pt)<br /> {<br /> if(pt!=NULL)<br /> {<br /> printf("%3c", pt->data);<br /> print_pretree(pt->lchild);<br /> print_pretree(pt->rchild);<br /> }<br /> }<br /> void print_pretree2(ptree pt)<br /> {<br /> pstack ps=NULL;<br /> ptree p=NULL;<br /> ps=init_stack();<br /> p=pt;<br /> while(p!=NULL || !empty_stack(ps))<br /> {<br /> while(p!=NULL)<br /> {<br /> printf("%3c", p->data);<br /> push_stack(ps, p);<br /> p=p->lchild;<br /> }<br /> if(!empty_stack(ps))<br /> {<br /> p=pop_stack(ps);<br /> p=p->rchild;<br /> }<br /> }<br /> }<br /> void print_midtree(ptree pt)<br /> {<br /> if(pt!=NULL)<br /> {<br /> print_midtree(pt->lchild);<br /> printf("%3c", pt->data);<br /> print_midtree(pt->rchild);<br /> }<br /> }<br /> void print_midtree2(ptree pt)<br /> {<br /> pstack ps=NULL;<br /> ptree p=NULL;<br /> ps=init_stack();<br /> p=pt;<br /> while (p!=NULL || !empty_stack(ps))<br /> {<br /> while(p!=NULL)<br /> {<br /> push_stack(ps, p);<br /> p=p->lchild;<br /> }<br /> if(!empty_stack(ps))<br /> {<br /> p=pop_stack(ps);<br /> printf("%3c", p->data);<br /> p=p->rchild;<br /> }<br /> }<br /> }<br /> void print_posttree(ptree pt)<br /> {<br /> if(pt!=NULL)<br /> {<br /> print_posttree(pt->lchild);<br /> print_posttree(pt->rchild);<br /> printf("%3c", pt->data);<br /> }<br /> }<br /> void print_posttree2(ptree pt)<br /> {<br /> pstack ps=NULL;<br /> ptree p=NULL;<br /> ptree p2=NULL;<br /> ptree lastvisit=NULL;<br /> ps=init_stack();<br /> p=pt;<br /> while (p!=NULL || !empty_stack(ps))<br /> {<br /> while(p!=NULL)<br /> {<br /> push_stack(ps, p);<br /> p=p->lchild;<br /> }<br /> p2=gettop_stack(ps); /* top: rchild==null or sub_root */<br /> if(p2->rchild==NULL || p2->rchild==lastvisit)<br /> {<br /> printf("%3c", p2->data);<br /> lastvisit=pop_stack(ps); /* pop */<br /> }<br /> else<br /> p=p2->rchild;<br /> }<br /> }<br /> void bfs_tree(ptree pt)<br /> {<br /> ptree p=NULL;<br /> queue qu;<br /> qu=init_queue();<br /> p=pt;<br /> if(p!=NULL)<br /> {<br /> en_queue(qu, p);<br /> while (!empty_queue(qu))<br /> {<br /> p=de_queue(qu);<br /> printf("%3c", p->data);<br /> if(p->lchild!=NULL)<br /> en_queue(qu, p->lchild);<br /> if(p->rchild!=NULL)<br /> en_queue(qu, p->rchild);<br /> }<br /> }<br /> }<br /> int _tmain(int argc, _TCHAR* argv[])<br /> {<br /> ptree pt=NULL;<br /> /*pt=init_tree();*/</p> <p> printf("Create tree:/n");<br /> pt=create_tree();<br /> /************ recursion ************/<br /> printf("/n/nrecursion...");<br /> printf("/npre tree.../n");<br /> print_pretree(pt);<br /> printf("/nmid tree.../n");<br /> print_midtree(pt);<br /> printf("/npost tree.../n");<br /> print_posttree(pt);<br /> /************ stack ************/<br /> printf("/n/nstack, non recursion:");<br /> printf("/npre tree.../n");<br /> print_pretree2(pt);<br /> printf("/nmid tree.../n");<br /> print_midtree2(pt);<br /> printf("/npost tree.../n");<br /> print_posttree2(pt);<br /> /********** bfs tree **********/<br /> printf("/n/nbfs_tree:/n");<br /> bfs_tree(pt);<br /> /********* tree operation ********/<br /> printf("/n/ntree operation:");<br /> d_tree=depth_tree(pt);<br /> leaf_tree(pt);<br /> node_tree(pt);<br /> printf("/ntree's depth: %d", d_tree);<br /> printf("/ntree's leaf: %d", l_tree);<br /> printf("/ntree's node: %d", n_tree);<br /> printf("/n");<br /> return 0;<br /> }<br />

运行结果：

======================================

===================================================================