1 二叉树

1 树

（1）树的概念与结构

树是⼀种⾮线性的数据结构，它是由 n（n>=0） 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
• 有⼀个特殊的结点，称为根结点，根结点没有前驱结点。

树形结构中，⼦树之间不能有交集，否则就不是树形结构

 • 除了根结点外，每个结点有且仅有⼀个⽗结点

• ⼀棵N个结点的树有N-1条边

（2）树的相关术语

⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的⽗ 结点

⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点

结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0

树的度：⼀棵树中，最⼤的结点的度称为树的度；如上图：树的度为 6  0 的结点；

 兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点

结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；

树的⾼度或深度：树中结点的最⼤层次；如上图：树的⾼度为 4

 结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先

路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q  

⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙

 森林：由 m（m>0） 棵互不相交的树的集合称为森林；

2 二叉树

（1）概念与性质

   在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点 加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

⼆叉树具备以下特点：
1. ⼆叉树不存在度⼤于 2 的结点
2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

(2)特殊的二叉树

1 满二叉树

⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀
个⼆叉树的层数为 K ，且结点总数是2 − ，则它就是满⼆叉树。

2 完全二叉树

满⼆叉树是⼀种特殊的完全⼆叉树

二叉树的性质

1）若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有2 个结点
i−1
2）若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是2 − 
h 1

3）若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度 ( log以2为底， n+1 为对数)

3 二叉树的存储结构

⼆叉树⼀般可以使⽤两种结构存储，⼀种顺序结构，⼀种链式结构。

（1)顺序结构

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

（2）链式结构

通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。

4实现顺序结构二叉树 

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。

堆的性质：

• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
• 堆总是⼀棵完全⼆叉树。

二叉树的性质：

• 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从
0 开始编号，则对于序号为 i 的结点有：
1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点
2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦
3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

堆的实现

（1）定义堆结构

//定义堆结构
typedef int HPDataType;
typedeef struct Heap
{
  HPDataType* arr;
  int size;//有效数据个数
  int capacity;//空间大小
}HP; 

(2)堆的初始化

​
//初始化
void HPnit(HP* php)
{
  assert(php);
  php->arr = NULL;
  php->size = php->capacity = 0;
}

​

(3)堆的销毁

//销毁
void HPDesTroy(HP* hp)
{
 assert(php);
 if(php->arr)
  free(php->arr);
 php->arr = NULL:
 php->size = php->capacity = 0;
}

（4）向上调整算法

算法思路：（以大堆为例）

1. 初始位置：将新元素插入到堆的末尾（对应数组的最后一个位置）。
2. 循环比较与交换：
   • 计算当前元素的父节点位置（对于数组索引 i，父节点索引为 (i-1)//2）。
   • 若当前元素的值 大于 父节点的值，说明违反大根堆性质，交换两者位置。
   • 更新当前元素的索引为父节点的索引，重复上述步骤，直到当前元素的索引为堆顶（i=0），或当前元素的值 小于等于 父节点的值。
3. 终止条件：当元素无法再向上调整（已满足堆性质），算法结束。

//向上调整算法
void AdjustUp(HPDataType*a, int child)
//第一个参数为指向HPDataType的指针，第二个参数表示需要向上调整的元素在数组中的下标
{
  int parent = (child-1)/2;
  while(child>0)
  {
   //孩子节点的值大于父亲节点
    if(arr[child] > arr[parent])
    {
      Swap(&arr[child], &arr[parent]);
      child = parent;
      parent = (child-1)/2;
    }
    else
    {
      break:
    }

其中的交换函数如下：

void Swap(int* x, int* y)
 {
   int tmp = *x;
   *x = *y;
   *y = tmp;
 }

(5)入堆------向堆中插入数据

//入堆
void HPPush(HP* hp, HPDataType x)
{
  assert(php);
  //空间不够要增容
  if(php->size == php->capacity)
  {
   //增容
   int newCapaty = php->capacity == 0 ? 4 : 2*capacity;
   HPDataType* tmp = (HPDataType*)realloc(php->arr,newCapacity* sizeof(HDPataType));
   if(tmp == NULL)
   {
     preeor("realloc fail!");
     exit(1);
   }
   php->arr = tmp;
   php->capacity = newCapacity;
  }
//空间足够
 php->arr[size] = x;
//向上调整算法
 AdjustUp(php->arr, php->size);
 ++php->size;
}

(6)判断堆是否为空

//判空
void HPEmpty(HP* hp)
{
 assert(php);
 return php->size == 0;
}

(7)向下调整算法

算法步骤（以大堆为例）

1. 初始位置：从需要调整的元素（通常是堆顶）开始。
2. 循环比较与交换：
   • 计算当前元素的左右子节点位置（对于数组索引 i，左子节点索引为 2i+1，右子节点索引为 2i+2）。
   • 选择子节点中值较大的一个（若存在）。
   • 若当前元素的值 小于 较大子节点的值，说明违反大根堆性质，交换两者位置。
   • 更新当前元素的索引为较大子节点的索引，重复上述步骤，直到当前元素没有子节点，或当前元素的值 大于等于 所有子节点的值。
3. 终止条件：当元素无法再向下调整（已满足堆性质），算法结束。

适用场景

• 堆的删除操作（如优先队列的元素出队）。
• 修复因元素值变小而被破坏的堆结构。
• 堆化（Heapify）操作：将一个无序数组转换为堆。

​
//向下调整算法
void AdjustDown(HPDAtaType* arr,int parent,int n)
//第二个参数是父亲节点的下标，第三个参数是数组个数，防止孩子节点向下调整时越界
{
  int child = parent*2 + 1;
  while(child < n)
  {
    //找最大的孩子
    if(child + 1 < n && arr[child] < arr[child+1])
     {
       child++;
     }
    //孩子和父亲比较
    if(arr[child] > arr[parent]) 
    {
      Swap(&arr[child], &arr[parent]);
      parent = child;
      child = parent*2 +!;
    }
    else
    {
     break;
    }
   }
}

​

(8)删除堆顶的数据

思路：将堆顶元素和最后一个元素交换，然后size--，有效数据个数减一，即删除原来的堆顶元素，利用向下调整算法对堆处理

//删除堆顶元素
void HPPop(HP* php)
{
 assert(!HPEmpty(php));
 Swap(&php->arr[0], &php->arr[php->[size-1]);
 --php->size;
 //堆顶数据需要向下调整
 AdjustDown(php->arr, 0, php->size);
}

(9)取堆顶操作

//取堆顶
HPDataType HPTop(HP* hp）
{
 assert(!HPEmpty(php));
 return php->arr[0];
}

(10)以上方法中建小堆的实现

1 向上调整算法

其中的修改部分

2 向下调整算法

（11）堆排序

将一个乱序的数组变为一个有序的数组

1 向下调整算法建堆------利用堆的思想，不用堆的实现

• 建堆策略：建堆时，从最后一个非叶子节点开始(即最后一个节点的父节点），向前逐步处理每个节点，对每个节点都执行向下调整操作。最后一个非叶子节点的位置可以通过(n-2)/2（最后一个节点为n-1，它的父节点为n-1-1/2)（这里n是数组的长度）计算得出。
• 排序：对乱序数组建完堆之后，交换跟节点和最后一个节点（此时跟节点时最小值），对新的跟节点进行向下调整，得到一个新的跟节点（此时跟节点是第二小的值），end--，重复上述操作，得到一个降序数组

​
//堆排序
void HeapSort(int* arr, int n)
{
 //乱序数组-----建堆
 for(int i = (n-1-1)/2; i>=0; i--;)
 {
   AjustDown(arr,i,n);
 }
 int end = n-1;
 while(end > 0)
 {
   Swap(&arr[0], arr[end]);
   AdjustDown(arr, 0, end);
   end--;
 }
}

​

排升序-------建大堆

排降序------建小堆

2 向上调整算法建堆

实现步骤

1. 初始化堆：从一个空堆开始。
2. 逐个插入元素：依次将数组中的元素插入堆中，每次插入后执行向上调整。
3. 向上调整操作：将当前节点与其父节点比较，若大于父节点则交换，重复此过程直到满足堆的性质。

//向上调整建堆
void HeapSort(int* arr, int n)
{
 for(int i = 0; i<n; i++)
 {
  AdjustUp(arr,i);
  }
}

向上调整算法建堆时间复杂度

需要移动节点总的步数为：每层节点数*向上调整次数（第一次调整次数为0）

复杂度为：O(n log n)

向下调整算法建堆的时间复杂度

向下调整算法建堆时间复杂度为：O(n)

5 TOP-K问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

引入：假设有10亿个整数，需要申请多大的内存？

1G = 1024MB = 1024 * 1024 KB = 1024 * 1024 *1024 byte ≈10亿个字节

因为一个整型是4个字节，所以需要申请4G的空间

 假设现在只有1KB的内存，怎么办？

思路如下：

找最大的前K个数据：建小堆，遍历剩下的数据和堆顶比，比堆顶大的就要和堆顶交换，使用向下调整法，始终把最小值放在堆顶

找最小的前K个数据：建大堆，遍历剩下的数据和堆顶比，比堆顶小的就要和堆顶交换，使用向下调整法，始终把最大值放在堆顶

void CreateNDate()
{
 //造数据
 int n = 100000;
 srand(time(0));
 const char* file = "data.txt";
 FTLE* fin = fopen(file, "w");
 if(fin == NULL)
  {
    perror("fopen error!");
    return;
  }
 
for(iint i=0; i<n; i++)
 {
   int data = (rand()+i)%1000000;//创建了一百万个随机数
   fprintf(fin, "&d\n", data);
 }
fclose(fin);
}


void TopK()
{
  int k = 0;
  printf("请输入K： “）；
  scanf("%d", &k);
  
  const char* file = "data.txt";
  FILE* fout = fopen(file, "r");
  if(fout ==NULL)
   {
     perror("fopen fail!");
     exit(!);
   }

  //申请大小为K的整型数组
  int* minHeap = (int*)malloc(sizeof(int)*k);//找最大值，建小堆
  if（minHeap == Heap)
   {
     perror("malloc fail!):
     exit(2);
   }

 //读取文件中的K个数据放到数组中
 for(int i = 0; i < k; i++)
  {
    fscanf(fout, "%d", &minHeap[i]);
  }

 //数组调整建堆-----向下调整建堆
//找最大的前K个数，建小堆
 for(int i = (k-1-1)/2; i>=0; i--)
 {
   AdjustDown(minHeap, i,k);
 }

//遍历剩下的n-k个数据，和堆顶比较，谁大谁入堆
int data = 0;
while(fscnaf(fout, "%d", &data) != EOF)
{
  if(data > minHeap[0])
  {
    minHeap[0] = data;
    AdjustDown(minHeap, 0 ,k);
  }
}

//打印堆里数据
for(int i = 0; i<k;i++)
{
  printf("%d"; minheap[i]);
}
printf("\n"):


flose(fout);
}
  

6 实现链式结构二叉树

1 定义二叉树结点结构

​
//定义
typedef int BTDaraType;
//二叉链
typedef strcut BinaryTreeNode
{
 strcut BinaryTreeNode* left;//指向当前结点左孩子
 struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

​

2 二叉树的遍历方式

⼆叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历：访问顺序为：根结点、左⼦树、右⼦树
2）中序遍历： 访问顺序为：左⼦树、根结点、右⼦树
3）后序遍历：访问顺序为：左⼦树、右⼦树、根结点

Eg：

前序遍历：A B D   NULL     NULL     NULL     C   E   NULL    NULL   F     NULL    NULL

中序遍历：NULL     D   NULL     B    A    NULL   E    NULL  C   NULL F     NULL

后序遍历： NULL  NULL    D     NULL    B   NULL    NULL    E     NULL    NULL     F    C     A

3 手动创建一颗二叉树

如下图示例，创建一颗二叉树

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));

	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

void test01()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;


	PreOrder(nodeA);//前序遍历
	
}

4 前序遍历

void PreOder(BTNode* root)
{
 if(root == NULL)
  {
   printf("NULL"):
   return ;
  }
  printf("&c", root->data);
  PreOder( root->left);
  PreOder( root->right);
}

5 中序遍历

//中序遍历
void InOder(BTNode* root)
{
  if(root == NULL)
   {
     printf("NULL"):
     return ;
   }
  InOder(root->left);
  InOder(root->right);
}

6 后序遍历

//后序遍历
void  PostOrder(BTNode* root)
{
 if(root == NULL)
  {
   printf("NULL");
   return ;
  }
PostOrder(root->left);
PostOrder(root->right);
printf("%c", root->data);
} 

7 二叉树的应用

（1）二叉树节点个数

int  BinaryTreeSize(BTNOde* root)
{
 if(root ==NULL)
 {
   return 0;
 }
 return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
} 

二叉树总的结点个数 = 跟结点个数（1） + 左子树节点个数 + 右子树节点个数

（2）二叉树叶子节点个数

叶子节点：没有左右孩子节点（即度为0）

叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数

int  BinaryTreeLeafSize(BTNode* root)
{
  if(root ==NULL)
  {
    return 0;
  }
  if(root->left == NULL && root->right == NULL)
  {
    return 1;
  }
 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

（3）求第K层节点个数

思路： 第K层节点个数 = 左子树第K层节点个数 + 右子树第K层节点个数

每向下遍历一层，K-1，直到K = 1， 该层为所求层

void BinaryTreeLevelKSize( BTNode* root, int k)
{
 if( root ==NULL)
 {
  return 0;
 }
 if(k == 1)
 {
  return 1;
 }
 return BinaryTreeLevelKSize(root->left, k-1) + BinaryTreeLevelKSize(root->right, k-1);

(4)二叉树的深度/高度

思路： 二叉树的高度 = 跟节点 + max（左子树高度， 右子树高度）

void BinaryTreeDepth(BTNode* root)
{
 if(root ==NULL)
 {
  return 0;
 }
 int leftdeep = BinaryTreeDepth(root->left);
 int rightdeep = BinaryTreeDepth(root->right);
//跟节点 + max（左子树高度 + 右子树高度）
return 1 + (leftdeep > rightdeep ? leftdeep : rightdeep);
}

（5）查找值为X的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
//函数类型不是void，必须有返回值
 if(root == NULL)
 {
   return NULL:
 }
 if(root->data == x)
 {
  return root;
 }
 BTNode* leftFind = BinaryTreeFind(root->left, x);
 if(leftFind)//左子树的值不为空
  {
    return leftFind;
  }
 BTNode* rightFind = BinaryTreeFind(root->right, x);
 if(rightFind)//右子树的值不为空
  {
    return rightFind;
  }
return NULL:
}

（6）二叉树的销毁

后序遍历

//销毁
void BInaryTreeDestory(BTNode** root)
{
  if(*root == NULL)
  {
    return;//空节点没有返回值
  }
//注意此处的符号，因为是二级指针，其需传地址
 BInaryTreeDestory(&((*root)->left));
 BInaryTreeDestory(&((*root)->right));
 free(*root);
 *root = NULL:
}

8 层序遍历

层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2
层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要用到队列

思路：把头节点入队，使队列不为空，循环遍历判断队列是否为空，不为空取队头，将队头节点不为空的孩子节点入队列。重复上述操作，直到队列为空

注意：1 运用到队列的操作，需要将队列的实现函数等引用。

            2  节点的结构需要更改

typedef  int  QDataType;
//定义节点结构
typedef struct QueueNode
{
 QDataType datal
 struct QueueNode* next;
}QueueNode;

将其中的  int  更改为二叉树节点结构：struct  BinaryTreeNode*(即将二叉树节点类型存储在队列中）

void LevelOrder(BTNode* root)
{
 Queue q;
 QueueTnit(&q);
 QueuePush(&q, root);
 while(!QueueEmpty(&q));
 {
  //取队头，打印对头
  BTNode* top = QueueFront(&q);
  printf("%c", top->data);
  QueuePop(&q);
  //队头节点不为空的孩子节点入队列
  if(top->left)
    QueuePush(&q, top->left);
  if(top->right)
    QueuePush(&q, top->right);
 } 
QueueDesTroy(&q(;
}

9 判断是否为完全二叉树

完全二叉树：最后一层节点个数不一顶达到最大，其他每层节点个数都达到最大，节点从左到右依次排列

如图所示，该图为非·完全二叉树，因为最后一层的节点没有从左到右依次排列

思路：根节点先入队列，保证队列不为空，循环判断队列是否为空，不为空取对头，出对头，将队头节点的左右孩子都入队列。取到空的队头，跳出循环。如果此时队列中只有空的节点，则为完全二叉树，否则不是完全二叉树。

​
//判断队列是否为完全二叉树
bool BinartTreeComplete(BTNode* root)
{
 Queue q;
 QueueTnit(&q);
 //头节点入队列
 QueuePush(&q, root);
 while(!queueEmpty(&q));
 {
  //取队头，入队头
  BTNode* top = QueueFront(&q);
  QueuePop(&q);
  if(top == NULL)
  {
    //top取到空直接出队列
    break;
  }
  //将队列头节点的左右孩子入队列
  QueuePush(&q, top->left);
  QueuePush(&q, top->right);
 }
//前一个循环取到空，跳出循环，判断剩下的队列
//队列不为空，继续取队列中的对头
while(QueueEmpty(&q));
{
 BTNode* top = QueueFront(&q);
 QueuePop(&q);
 if(top != NULL)
 {
  //不是完全二叉树
  QueueDesTroy(&q);
  return false;
 }
}
QueueDesTroy(&q);
return true;
}

​

10 二叉树OJ题

（1）单值二叉树

bool isUnivalTree(struct TreeNode* root)
{
 if(root == NULL)
 {
  return true;
 }
//root非空，root跟左右孩子节点的值比较
 if(root->left && root->left->val != root->val)
 {
  return false;
 }
 if(root->right && root->right->val != root->val)
 {
  return false;
 }
 return isUnivalTree(root->left) && isUnivalTree(root->right);
}

（2）相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
 //都为空
 if（p == NULL && q == NULL)
 {
  return true;
 }
 //其中一个为空
 if(p == NULL || q == NULL)
 {
  return false;
 }
 //都不为空----比较节点的值
 if(p->val != q->val)
 {
   return false;
 }
 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

(3)对称二叉树

​
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
 //都为空
 if（p == NULL && q == NULL)
 {
  return true;
 }
 //其中一个为空
 if(p == NULL || q == NULL)
 {
  return false;
 }
 //都不为空----比较节点的值
 if(p->val != q->val)
 {
   return false;
 }
 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

​bool isSymmetric(struct TreeNode* root)
{
  return isSameTree(root->left, root->right);
} 

(4)另一颗树的的子树

​typedef struct TreeNode TreeNode
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
 //都为空
 if（p == NULL && q == NULL)
 {
  return true;
 }
 //其中一个为空
 if(p == NULL || q == NULL)
 {
  return false;
 }
 //都不为空----比较节点的值
 if(p->val != q->val)
 {
   return false;
 }
 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

​
bool isSubtree (struct TreeNode*root, struct TreeNode* subRoot)
{
 if(root == NULL)
 {
   return false;
 }
 if(isSameTree(root, subRoot))
 {
  return true;
 }
return isSubtree(root->left, subRoot) || isSubTree(root->right, subRoot);
}

(5)二叉树的前序遍历

题目要求中给出：Note: The returned array must be malloced, assume caller calls free().

需要自己开辟空间

int  BinaryTreeSize(struct TreeNode* root)
{
 if(root == NULL)
 {
  return 0;
 }
 return 1 + BinatyTreeSize(root->left)  + BinaryTreeSize(root->right);
}
//前序遍历
void preOrder(struct TreeNode* root, int*arr, int* pi)
{
 if(root == NULL)
 {
  return ;
 }
arr[(*pi)++] = root->val;
preOrder(root->left, arr, pi）；
preOrdedr(root->right,arr, pi);
}
//*returnSize表示要返回的数组的大小
int* preorderTraversal(struct TreeNode* root, int*returnSize)
{
 //二叉树节点个数 = *returnSize 
 *returnSize = BinaryTreeSize(root);
 int* arr = (int*)malloc(sizeof(int)*(*returnSize)):
 int i=0;
 preOrder(root, arr, &i);
 return arr;
}

(6)二叉树遍历

如题目中的例子：ABC##DE#G##F##，所得前序遍历之后的如下图所示

//定义二叉树的结构
typedef struct BinaryTreeNode
{
 char data;
 struct BinaryTreeNOde* left;
 struct BinaryTreeNode* right;
}BTNode:

//创建一个节点
BTNode* buyNode(char ch)
{
 BTNode* newnoded = (BTNode*)malloc(sizrof(BTNode)):
 newnode->data = ch;
 newnode->left = newnode->righr = NULL:
return newnode;
}

//构建二叉树
BTNOde* createTree(char* arr, int* pi)
{
 if(arr[*pi] = '#')
 {
  (*pi)++;
  return NULL:
 }
 BTNode* root = buyNode(arr(*pi)++]);
 root->left = createTree(arr,pi);
 root->right = createTree(arr,pi);
 rerturn root;
}

//中序遍历
void InOrder(BTNode* root)
{
 if(root ==NULL)
 {
   return ;
 }
 InOrder(root->left);
 printf("%c", root->data);
 InOrder(root->right);
}

int main()
{
 //读取输入·的字符保存到数组中
 char arr[100];
 scanf("%s", arr);
 //根据先序遍历创建二叉树
 int i=0;
 BTNode* root = createTree(arr, &i);
 //中序遍历
 InOrder(root);
 return 0;
}