- #include <stdio.h>
- #include <stdlib.h>
- struct tree
- {
- int data;
- struct tree *left;
- struct tree *right;
- };
- typedef struct tree treenode;
- typedef treenode *btree;
- /*
- 往链表二叉树插入数据
- */
- btree insertnode(btree root, int val)
- {
- btree newnode;
- btree current;
- btree backnode;
- newnode = (btree)malloc(sizeof(treenode));
- newnode->data = val;
- newnode->right = NULL;
- newnode->left = NULL;
- if(root == NULL)
- {
- return newnode;
- }else{
- current = root;
- while(current != NULL)
- {
- backnode = current;
- if(val > current->data)
- current = current->right;
- else
- current = current->left;
- }
- if(backnode->data > val)
- backnode->left = newnode;
- else
- backnode->right = newnode;
- }
- return root;
- }
- /**
- * 二叉树的非递归查找
- */
- btree find_tree(btree root,int e)
- {
- btree ptr;
- ptr = root;
- while(ptr != NULL)
- {
- if(ptr->data == e)
- return ptr;
- else
- {
- if(ptr->data > e)
- ptr = ptr->left;
- else
- ptr = ptr->right;
- }
- }
- return NULL;
- }
- /**
- * 递归的查找遍历
- */
- btree trave_btree(btree ptr,int e)
- {
- btree ptr1,ptr2;
- if(ptr != NULL)
- {
- if(ptr->data == e)
- return ptr;
- else{
- ptr1 = trave_btree(ptr->left,e);
- ptr2 = trave_btree(ptr->right,e);
- if(ptr1 != NULL)
- return ptr1;
- else{
- if(ptr2 != NULL)
- return ptr2;
- else
- return NULL;
- }
- }
- }else{
- return NULL;
- }
- }
- //创建链表的二叉树
- btree create_sbtree(int *data, int len)
- {
- int i;
- btree root = NULL;
- for(i=0;i<len;i++)
- {
- printf("%d\\t",data[i]);
- root = insertnode(root,data[i]);
- }
- return root;
- }
- void printbtree(btree root)
- {
- btree ptr;
- printf("\\nroot is :%d\\n",root->data);
- ptr = root->left;
- printf("输出左子树:\\n");
- while(ptr)
- {
- printf("%d\\n",ptr->data);
- if(ptr->right)
- {
- printf("%d\\n",ptr->right->data);
- }
- ptr = ptr->left;
- }
- ptr = root->right;
- printf("输出右子树:\\n");
- while(ptr)
- {
- printf("%d\\n",ptr->data);
- if(ptr->left)
- {
- printf("%d\\n",ptr->left->data);
- }
- ptr = ptr->right;
- }
- }
- /**
- * 复制二叉树
- *
- */
- btree copy_btree(btree ptr)
- {
- btree newnode;
- if(ptr == NULL)
- {
- return NULL;
- }else{
- newnode = (btree)malloc(sizeof(treenode));
- newnode->data = ptr->data;
- newnode->left = copy_btree(ptr->left);
- newnode->right = copy_btree(ptr->right);
- return newnode;
- }
- }
- void main()
- {
- int data[10] = {5,6,4,8,2,3,7,1,9};
- //create a bree
- btree root = NULL;
- int i;
- root =create_sbtree(data,9);
- printbtree(root);
- printf("#########一般查找############");
- btree find_res;
- //查找成功
- find_res = find_tree(root,7);
- if(find_res != NULL)
- printf("%d\\n",find_res->data);
- //查找失败
- find_res = find_tree(root,7);
- if(find_res != NULL)
- printf("%d\\n",find_res->data);
- printf("##########遍历递归查找##########");
- btree trave_res;
- //查找成功
- trave_res = trave_btree(root,7);
- if(find_res != NULL)
- printf("%d\\n",trave_res->data);
- //查找失败
- trave_res = trave_btree(root,7);
- if(find_res != NULL)
- printf("%d\\n",trave_res->data);
- btree newtree = copy_btree(root);
- printbtree(root);
- }
- //该片段来自于http://www.codesnippet.cn/detail/3010201410859.html
来源: http://www.codesnippet.cn/detail/3010201410859.html