C语言搜索二叉树测试代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <stdbool.h>
  4 
  5 typedef int DATA;
  6 typedef struct _SNode_
  7 {
  8     DATA data;
  9     struct _SNode_ *p_Right, *p_Left;
 10 } SNode;
 11 
 12 // 创建二叉树
 13 SNode *CreateTree(const DATA d)
 14 {
 15     SNode *m_root = (SNode *)malloc(sizeof(SNode));
 16     m_root->data = d;
 17     m_root->p_Left = m_root->p_Right = NULL;
 18     return m_root;
 19 }
 20 // 插入右子树
 21 void InsertRight(SNode *p, const DATA d)
 22 {
 23     SNode *pNew = CreateTree(d);
 24     p->p_Right = pNew;
 25 }
 26 // 插入左子树
 27 void InsertLeft(SNode *p, const DATA d)
 28 {
 29     SNode *pNew = CreateTree(d);
 30     p->p_Left = pNew;
 31 }
 32 // 前序遍历DLR
 33 void PreOrder(SNode *p)
 34 {
 35     printf("%d ", p->data);
 36     if (p->p_Left)
 37         PreOrder(p->p_Left);
 38     if (p->p_Right)
 39         PreOrder(p->p_Right);
 40 }
 41 // 中序遍历LDR
 42 void InOrder(SNode *p)
 43 {
 44     if (p->p_Left)
 45         InOrder(p->p_Left);
 46     printf("%d ", p->data);
 47     if (p->p_Right)
 48         InOrder(p->p_Right);
 49 }
 50 // 后序遍历LRD
 51 void PostOrder(SNode *p)
 52 {
 53     if (p->p_Left)
 54         PostOrder(p->p_Left);
 55     if (p->p_Right)
 56         PostOrder(p->p_Right);
 57     printf("%d ", p->data);
 58 }
 59 // 查找二叉树中的元素
 60 bool LookUp(SNode *p, const DATA d)
 61 {
 62     while (p)
 63     {
 64         if (p->data == d)
 65             return true;
 66         else if (p->data > d)
 67             p = p->p_Left;
 68         else
 69             p = p->p_Right;
 70     }
 71     return false;
 72 }
 73 // 创建搜索二叉树
 74 void SetAt(SNode *p, const DATA d)
 75 {
 76     SNode **ppRoot = &p;
 77     while (*ppRoot)
 78     {
 79         if ((*ppRoot)->data < d)
 80             ppRoot = &(*ppRoot)->p_Right;
 81         else if ((*ppRoot)->data > d)
 82             ppRoot = &(*ppRoot)->p_Left;
 83     }
 84     SNode *pNew = CreateTree(d);
 85     *ppRoot = pNew;
 86 }
 87 
 88 int main()
 89 {
 90     SNode *pRoot = CreateTree(30);
 91     SetAt(pRoot, 75);
 92     SetAt(pRoot, 20);
 93     SetAt(pRoot, 40);
 94     SetAt(pRoot, 10);
 95     SetAt(pRoot, 60);
 96     SetAt(pRoot, 50);
 97 
 98     if (LookUp(pRoot, 52))
 99         printf("找到了！\n");
100     else
101         printf("没有找到！\n");
102 
103     if (LookUp(pRoot, 40))
104         printf("找到了！\n");
105     else
106         printf("没有找到！\n");
107 
108     InOrder(pRoot);
109 
110     return 0;
111 }