C语言之——Binary Tree

算是对C语言的一次总结复习了，在参考一篇二叉树的文章后，自己实现了二叉树的一系列操作。时间有点晚了，就贴上参考文章和代码吧，感觉这里递归思想用的很多，我全部用递归写的。

 

http://cslibrary.stanford.edu/110/BinaryTrees.html

 

#define NULL 0#include <stdlib.h>

struct node{ int data; struct node *left; struct node *right;};

typedef struct node BTree;

int max2(int a,int b);

BTree * insert(BTree *root,int data){ if(root==NULL){  root=(BTree *)malloc(sizeof(BTree));  root->data=data;root->left=NULL;root->right=NULL; }else{  if(data<=root->data)root->left=insert(root->left,data);  else root->right=insert(root->right,data); } return root;}

BTree * buildTree(int data[],int size){ int i=0; BTree *root=NULL; for(i=0;i<size;i++){  root=insert(root,data[i]); } return root;}

int lookup(BTree *root,int target){ if(root==NULL){  return 0; }else{  if(target==root->data)return 1;  else{   if(target<root->data)return lookup(root->left,target);   else return lookup(root->right,target);  } }}

int size(BTree *root){ if(root==NULL)return 0; else{  return 1+size(root->left)+size(root->right); }}

int maxDepth(BTree *root){ if(root==NULL)return 0; else{  return 1+max2(maxDepth(root->left),maxDepth(root->right)); }}

int max2(int a,int b){ return a>b?a:b;}

int minValue(BTree *root){ if(root==NULL)return; while(root->left!=NULL)root=root->left; return root->data;}

void printTree(BTree *root){ if(root==NULL)return; else{  printTree(root->left);  printf("%d",root->data);  printTree(root->right); }}

int hasPathSum(BTree *root,int sum){ if(root==NULL){  if(sum==0)return 1;  else return 0; }else{  return (hasPathSum(root->left,sum-root->data)||hasPathSum(root->right,sum-root->data)); }}

void printPaths(BTree *root){ if(root==NULL)return; else{  if(root->left!=NULL){   printf("%d ",root->data);   printPaths(root->left);  }  if(root->right!=NULL){   printf("%d ",root->data);   printPaths(root->right);  }  if(root->left==NULL&&root->right==NULL){   printf("%d/n",root->data);  } }}

void mirror(BTree *root){ BTree *temp; if(root==NULL)return; else{  temp=root->left;  root->left=root->right;  root->right=temp;  mirror(root->left);  mirror(root->right); }}

void doubleTree(BTree *root){ BTree *new; if(root==NULL)return; else{  new=(BTree *)malloc(sizeof(BTree));  new->data=root->data;new->left=NULL;new->right=NULL;  new->left=root->left;  root->left=new;  doubleTree(new->left);  doubleTree(root->right); }}

int sameTree(BTree *a,BTree *b){ if(a==NULL&&b==NULL)return 1; else if(a!=NULL&&b!=NULL&&a->data==b->data)  return (sameTree(a->left,b->left)&&sameTree(a->right,b->right)); else return 0;}

int isBST(BTree *root,int min,int max){ if(root==NULL)return; else{  if(root->data<=max&&root->data>min)   return isBST(root->left,min,root->data)&&isBST(root->right,root->data,max);  else return 0; }}

main(){ int data[]={2,1,3,4}; BTree *root=buildTree(data,4); BTree *root2=buildTree(data,4); printf("%d/n",root->right->right->data); printf("%d/n",hasPathSum(root,3)); doubleTree(root); doubleTree(root2); printf("%d/n",isBST(root,0,5));}