二叉树递归,非递归遍历代码,C代码库,德仔网

代码语言
代码分类
【C】二叉树递归,非递归遍历
作者:Gooogle / 发布于2012/3/6/ 835
#include <stdio.h></div>
#include <stdlib.h></div>
#include <assert.h></div>
<div>/* struct of tree */</div>
<div>typedef struct tree {</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>int data;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>struct tree *left;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>struct tree *right;</div>
<div>} tree_item, *tree_pitem, *tree_list;</div>
<div></div>
<div>/* alloc_item alloc a struct of tree_item, and return it */</div>
<div>tree_pitem alloc_item(int data){</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tree_pitem tmp = (tree_pitem)malloc(sizeof(tree_item));</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tmp->data = data;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tmp->left = NULL;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tmp->right = NULL;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>return tmp;</div>
<div>}
<div></div>
<div>/* print root of the tree */</div>
<div>void put_root(tree_item *l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>printf("[%d]", l->data);</div>
<div>}
<div></div>
<div>/* insert item into tree */</div>
<div>void insert_to_tree(int data, tree_list *l){//需要修改l的left和right 所以用**</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL == *l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>*l = alloc_item(data);//这里是根节点初始化</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>if(data < (*l)->data){</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>if(NULL == (*l)->left){</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>(*l)->left = alloc_item(data);</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>insert_to_tree(data, &(*l)->left);//小的往左边塞</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}else if(data > (*l)->data){</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>if(NULL == (*l)->right){</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>(*l)->right = alloc_item(data);</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>insert_to_tree(data, &(*l)->right);//大的往右边塞</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>return;</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>void first_put(tree_list l){//先序递归</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>put_root(l);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>first_put(l->left);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>first_put(l->right);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>void middle_put(tree_list l){//中序递归</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>middle_put(l->left);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>put_root(l);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>middle_put(l->right);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>void last_put(tree_list l){//后续递归</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>last_put(l->left);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>last_put(l->right);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>put_root(l);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>/* 栈没有定义, 也没有验证正确与否, 算是个伪代码 */</div>
<div>void iteration_first(tree_list l){非递归先序</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tree_list tmp = l;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>while(!is_empty(tmp)){</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>visit(tmp);//先访问根</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>if(tmp->left != NULL){//如果有左子节点</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>push(tmp);//保存根</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>tmp = tmp->left;//开始访问左子树</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>if(tmp->right != NULL){//如果没有左子节点, 但有右子节点</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>push(tmp);//保存根</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = tmp->right;//开始访问右子树</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = pop();//既没有左也没有右, 回到父节点</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>void iteration_middle(tree_list l){//非递归中序</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tree_list tmp = l;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>while(!is_empty(tmp)){</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>if(tmp->left != NULL){</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>push(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>tmp = tmp->left;</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>visit(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>if(tmp->right != NULL){</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>push(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = tmp->right;</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = pop();</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div>        }
<div>    }
<div>}
<div></div>
<div>void iteration_last(tree_list l){//非递归后序</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tree_list tmp = l;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(NULL != l){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>while(!is_empty(tmp)){</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>if(tmp->left != NULL){</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>push(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>tmp = tmp->left;</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>if(tmp->right != NULL){</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>push(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = tmp->right;</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}else{</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>visit(tmp);</div>
<div><span class="Apple-tab-span" style="white-space:pre">					</span>tmp = pop();</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>}
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div>}
<div></div>
<div>int main(int argc, char **argv){</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>tree_list tree = (tree_list)0;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>int i;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>for(i = 1; i <= 10; i++){</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>insert_to_tree(i, &tree);//insert_to_tree(rand() % 100, &tree)</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>first_put(tree);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>puts("\n");</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>middle_put(tree);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>puts("\n");</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>last_put(tree);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>puts("\n");</div>
<div>}
<div></div>
试试其它关键字
　二叉树　
同语言下
可能有用的
Gooogle贡献的其它代码(3)