03-树2 List Leaves (过程讲解)

先看一下题目:

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

int head;//存放树的头节点
int intputNums;//存放输入的总节点数int main() {//读入树scanf("%d",&intputNums);head = readTree(intputNums);//遍历树traverseTree(head);return 0;
}

我们来创建一个结构体treeNode表示树的一个节点，然后他的两个属性表示左孩子和右孩子的位置。

那么我们把总共输入的节点数那么多个treeNode结构体放入一个数组中，每个数组的下标表示当前节点的位置。

也就是用一个静态链表来表示树。

同时，既然需要层序遍历，就需要用到队列，那么我们也需要创建一个队列以及队列的相关操作。

#define MAXSIZE 10 //题目告诉我们总结点不超过10//树
struct treeNode{int left;int right;
};
struct treeNode tree[MAXSIZE];//队列 
struct treeQueue{int * trees; //存放的是下标int front,rear;
};
typedef struct treeQueue * tQueue;//下面是队列的相关操作
//创建队列
tQueue creatQueue(){tQueue q = (tQueue)malloc(sizeof(struct treeQueue));q->trees = (int*)malloc(MAXSIZE*sizeof(int));q->front = q->rear = -1;return q;
}
//判断是否为空
bool isEmpty(tQueue q){if (q->front == q->rear){return 1;}elsereturn 0;
}
//队列添加
void addQueue(tQueue q,int x){//判断队列是否满了if ((q->rear+1)%10 == q->front){return;}else{q->rear = (q->rear+1)%MAXSIZE;q->trees[q->rear] = x;}
}
//队列删除
int deleteQueue(tQueue q){if (q->front == q->rear){return -1;}else{q->front = (q->front+1)%MAXSIZE;return q->trees[q->front];}
}

来看一下读取树的操作:

这里我们   1.读取树 2.找到树的根节点。

我们可以这样想，在树中，除了根节点，每个节点都有其他节点指向它。我们可以用一个数组表示每个节点，初始化为0。当有节点指向了某个节点，把这个节点标记为1。最后没有被标记的节点就是根节点。

int readTree(int count){ //读入树并返回树的根节点int testArr[MAXSIZE];//树的根节点标记数组char cl,cr; //创建两个临时char变量for (int i = 0; i < count; ++i) testArr[i]=0; //初始化每个元素为0for (int i = 0; i < count; ++i){getchar(); //很关键scanf("%c %c",&cl,&cr);//因为要读取'-'所以先把'-'和数字都当成 char类型读取if (cl != '-'){//左孩子不是空tree[i].left = cl-'0'; // cl-'0' 可以把 char类型变回int类型testArr[tree[i].left] = 1; //把被指向的节点标记为1 最后没有被指向的节点就是根节点}else//左孩子是空tree[i].left = -1; //-1表示该节点的孩子是空if (cr != '-'){//右孩子不是空tree[i].right = cr-'0';testArr[tree[i].right] = 1;}else//右孩子是空tree[i].right = -1;}for (int i = 0; i < count; ++i){//遍历记录数组找到根节点并返回if (!testArr[i]) return i;}return -1;//没有找到返回-1
}

最后来看一下 层序遍历：

我们先把树的根节点放入队列中，然后弹出队列头(树的根节点)，队列里保存的是记录树的数组中节点的下标，根据这个下标，去记录树的数组中寻找相应的节点。该节点的结构体中保存了其左右孩子的位置，然后根据其左右孩子的具体情况做处理，如果存在则把左右孩子在数组中的下标入队。

void traverseTree(int top){//参数为树的根节点int i;//保存栈顶元素int num = 0;//记录遍历的节点数量if (top == -1){return;}//初始化队列并放入第一个元素tQueue q = creatQueue();  addQueue(q,top);while(q->front != q->rear){//队列不为空时循环num++;//记录遍历的节点数i = deleteQueue(q);//弹出栈顶元素if (tree[i].left != -1 && tree[i].right != -1){//左右孩子都存在addQueue(q,tree[i].left);//左孩子入队addQueue(q,tree[i].right);//右孩子入队}else if (tree[i].left != -1 && tree[i].right == -1){ //左孩子存在 右不存在addQueue(q,tree[i].left);}else if (tree[i].left == -1 && tree[i].right != -1){ //左孩子不存在 有孩子存在addQueue(q,tree[i].right);}else{//左右孩子都不存在 也就是找到了叶子节点if (num != intputNums) printf("%d ", i);//输出格式控制else printf("%d", i);}}}

• 最后附上整块代码:

#include 
#include 
#include 
#include 
#define MAXSIZE 10int head;//存放树的头节点
int intputNums;//树
struct treeNode{int left;int right;
};
struct treeNode tree[MAXSIZE];//队列 //存放的是下标
struct treeQueue{int * trees;int front,rear;
};
typedef struct treeQueue * tQueue;
//队列的相关操作
tQueue creatQueue(){tQueue q = (tQueue)malloc(sizeof(struct treeQueue));q->trees = (int*)malloc(MAXSIZE*sizeof(int));q->front = q->rear = -1;return q;
}
bool isEmpty(tQueue q){if (q->front == q->rear){return 1;}elsereturn 0;
}void addQueue(tQueue q,int x){//判断队列是否满了if ((q->rear+1)%10 == q->front){return;}else{q->rear = (q->rear+1)%MAXSIZE;q->trees[q->rear] = x;}
}int deleteQueue(tQueue q){if (q->front == q->rear){return -1;}else{q->front = (q->front+1)%MAXSIZE;return q->trees[q->front];}
}int readTree(int count){int testArr[MAXSIZE];char cl,cr;for (int i = 0; i < count; ++i) testArr[i]=0;for (int i = 0; i < count; ++i){getchar();scanf("%c %c",&cl,&cr);if (cl != '-'){//左孩子不是空tree[i].left = cl-'0';testArr[tree[i].left] = 1;}elsetree[i].left = -1;if (cr != '-'){//右孩子不是空tree[i].right = cr-'0';testArr[tree[i].right] = 1;}elsetree[i].right = -1;}for (int i = 0; i < count; ++i){if (!testArr[i]) return i;}return -1;
}void traverseTree(int top){int i;//保存栈顶元素int num = 0;//记录遍历的节点数量if (top == -1){return;}//初始化队列并放入第一个元素tQueue q = creatQueue();  addQueue(q,top);while(q->front != q->rear){num++;i = deleteQueue(q);//弹出栈顶元素if (tree[i].left != -1 && tree[i].right != -1){//左右孩子都存在addQueue(q,tree[i].left);addQueue(q,tree[i].right);}else if (tree[i].left != -1 && tree[i].right == -1){ //左孩子存在 右不存在addQueue(q,tree[i].left);}else if (tree[i].left == -1 && tree[i].right != -1){ //左孩子不存在 有孩子存在addQueue(q,tree[i].right);}else{//左右孩子都不存在if (num != intputNums) printf("%d ", i);else printf("%d", i);}}}int main() {
//读入树scanf("%d",&intputNums);head = readTree(intputNums);
//遍历树traverseTree(head);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！