• 72427

    文章

  • 659

    评论

  • 17

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

递归和非递归实现二叉树的建立,遍历及镜像树

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>
#include<stdio.h>
#include<stdlib.h>
#define SIZE 20

typedef struct Node{
        int data;
        struct Node *left, *right;
}TreeNode, *Tree;																																								
//功能要求
//二叉搜索树的建立和储存,前序和中序,后序的遍历(非递归)统计高度,及镜像树
//定义节点结构
//添加节点(递归思想实现)


void AddNode(Tree* TR,int key){
        //若头节点为空,则申请内存
        if(*TR == NULL){
                 (*TR) = (Tree)malloc(sizeof(TreeNode));
                 (*TR)->data = key;  
                (*TR)->left = NULL;
                (*TR)->right = NULL;
        }
        //若比该节点值小,则是左子树节点
        else if(((*TR))->data > key){
               AddNode(&((*TR)->left),key);
        }else if(((*TR))->data < key){
               AddNode(&((*TR)->right),key);
        }
		
}

//创建二叉搜索树
 void Init(Tree* TR,int arr[],int n){
        int i = 0;
        //若为空,申请内存
        
        for(i= 0; i<n; i++){
               AddNode(TR, arr[i]);
        }     
}

//遍历树(中序)  - 递归
void Middle_Search(Tree TR){
        if(TR){
                Middle_Search(TR->left);
                printf("%d ", TR->data);
                Middle_Search(TR->right);
        }
}

//非递归遍历(中序)  使用栈的思想
void Middle_NoSearch(Tree Thead){
        //定义结构体指针数组,作为栈的实现结构
        Tree queen[SIZE];
        int head = -1;

	//stop
        while(Thead != NULL || head != -1){      
                //先让左子树节点入栈
                while(Thead != NULL){
                        //入栈
                        queen[++head] = Thead;
                        Thead = Thead ->left;
                }

                if(head != -1){
                         //一直走到叶子节点
                        Thead = queen[head--];
                        printf("%d ", Thead->data);
                        //将当前接节点的右子树节点入栈
                        Thead = Thead ->right;
                }

        }


}
//计算树的深度
int Lenght(Tree HT){
        //需要比较左子树和右子树
        int rightDepth = 0, leftDepth = 0;
        if(HT ==NULL){
                return 0;
        }else{
                rightDepth = Lenght(HT->left)+1;
                leftDepth  = Lenght(HT->right)+1;
                return rightDepth >= leftDepth ? rightDepth : leftDepth;
        }

}

//

 
int main(){
        //不能有重复值
	    Tree head = NULL;
		int len= 0;

        int arr[11] = {5,3,4,1,7,8,2,6,0,9,10};
      
        Init(&head,arr,11);
        printf("递归中序遍历:");
        Middle_Search(head);
        printf("\n");

        printf("非递归中序遍历:");
        Middle_NoSearch(head);
        printf("\n");

	len = Lenght(head);
        printf("树的深度: %d\n",len);
        return 0;
}

结果:


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

欢迎来到梁钟霖个人博客网站。本个人博客网站提供最新的站长新闻,各种互联网资讯。 还提供个人博客模板,最新最全的java教程,java面试题。在此我将尽我最大所能将此个人博客网站做的最好! 谢谢大家,愿大家一起进步!

转载原创文章请注明出处,转载至: 梁钟霖个人博客www.liangzl.com

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤
注册梁钟霖个人博客