#include "stdafx.h"
#include <iostream>
using namespace std;
typedef struct BinTNode
{
int data;
BinTNode *lchild;
BinTNode *rchild;
BinTNode(int elemet = 0, BinTNode *left = NULL, BinTNode *right = NULL)
:data(elemet), lchild(left), rchild(right){}
}BinTNode;
//递归创建二叉树
BinTNode *CreateBinTree(int arr[],int begin, int end)
{
BinTNode *root = NULL;
if (begin >= end)
return root;
root = new BinTNode(arr[begin]);
root->lchild = CreateBinTree(arr, begin * 2 + 1, end);
root->rchild = CreateBinTree(arr, begin * 2 + 2, end);
return root;
}
//函数功能：递归，利用叶子结点中空的右指针域rchild，
//将所有叶子结点自左向右连接成一个单链表，返回最左叶子结点的地址
BinTNode *head = NULL;
BinTNode *temp = NULL;
void ChangleToSingleList(BinTNode *root)
{
if (NULL == root)//树为空
return ;
//叶子结点
if (root->lchild == NULL && root->rchild == NULL)
{
if(NULL == temp)
{
temp = head = root;
}
else
{
temp->rchild = root;
temp = root;
}
}
ChangleToSingleList(root->lchild);//左子树
ChangleToSingleList(root->rchild);//右子树
}
int main()
{
const int N = 10;
int arr[N];
for (int i = 0; i < N; i++)
arr[i] = i + 1;
BinTNode *root = CreateBinTree(arr, 0, N);
ChangleToSingleList(root);
while (head != NULL)
{
cout<<head->data<<" ";
head = head->rchild;
}
cout<<endl;
}