数据结构简单入门/复习(五)-树与二叉树的代码示例(C语言)

链式存储结构

typedef struct BiTNode{
TElemType data;                   //数据存储
struct BiTNode *lchild, *rchild;  //左右孩子指针
}BiTNode;

递归遍历

原理:以先序遍历为例,为了完成 根左右 的遍历方式,我们每次碰到根,就要输出根,输出完成后,再遍历左孩子,左孩子遍历完成后,遍历右孩子,之后结束遍历,这个遍历在递归遍历中较为容易理解与使用。

//先序遍历的递归算法
void preOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL,则直接结束这次小遍历。 
    printf("%d,", T->data);         //先进行结点数据输出。    (根)
    preOrderTraverse(T->lchild);    //再遍历左孩子。          (左)
    preOrderTraverse(T->rchild);    //最后遍历右孩子。        (右)
}
//中序遍历的递归算法
void inOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL,则直接结束这次小遍历。
    inOrderTraverse(T->lchild);     //先遍历左孩子。          (左) 
    printf("%d,", T->data);         //再进行结点数据输出。     (根)
    inOrderTraverse(T->rchild);     //最后遍历右孩子。        (右)
}
//后续遍历的递归算法
void postOrderTraverse(BiTNode *T){
    if(!T) return;                  //如果这个结点是NULL,则直接结束这次小遍历。
    postOrderTraverse(T->lchild);   //先遍历左孩子。           (左) 
    postOrderTraverse(T->rchild);   //再遍历右孩子。           (右)
    printf("%d,", T->data);         //最后进行结点数据输出。    (根)
}

非递归遍历

原理:
在非递归先序遍历中,我们使用栈,
先初始化一个栈,并将根结点推入栈
开始一个循环(栈非空){
栈顶结点设置为node;
栈顶结点退出;
循环(node存在){
输出node数据;
如果(node有右孩子)右孩子推入栈;
node的左孩子设置为node;

原理:
在非递归先序遍历中,我们使用栈,
先初始化一个栈,并将根结点推入栈
开始一个循环(栈非空){
栈顶结点设置为node;
栈顶结点退出;
循环(node存在){
输出node数据;
如果(node有右孩子)右孩子推入栈;
node的左孩子设置为node;


示例:
以左图的六结点完全二叉树为例:
1.初始化栈S;
2.根结点1推入栈S;
3.栈非空:栈顶结点1设置为node,栈退出一个结点1;
4.node1存在:输出1数据,右孩子3推入栈,左孩子2设置为node;
5.node2存在:输出2数据,右孩子5进入栈,左孩子4设置为node;
6.node4存在:输出4数据,左孩子NULL设置为node:
7.node不存在:栈顶结点5设置为node,栈退出一个结点5;
8.node5存在:输出5数据,左孩子NULL设置为node;
9.node不存在:栈顶结点3设置为node,栈退出一个结点3;
10.node3存在:输出3数据,左孩子6设置为node;
11.node6存在;输出6数据,左孩子NULL设置为node;
12.node不存在:栈空:循环结束。

//先序遍历非递归算法代码实现
//这串代码自带了简单的栈功能,为了方便理解,因为作为入门,栈的使用大多还不是很熟练。
//除非特殊需求或者爱好,请不要学习这个栈调用方式。
//伪代码已经在上方原理处了,稍微修改即可
void preOrderTraverse(BiTNode *T){
    BiTNode *stack[20], *node;            //定义一个大小为20的顺序栈stack,以及一个临时变量node
    int stackSize = 0;                    //栈的当前大小设置为0
    stack[stackSize] = T;                 //栈顶设置为根节点T
    stackSize++;                          //栈的大小增加
    while(stackSize != 0){                //如果栈非空,循环
        node = stack[stackSize-1];        //将栈顶元素设置成node
        stackSize--;                      //退栈
        while(node){                      //node存在,则循环
            printf("%d,", node->data);    //打印数据
            if(node->rchild){             //如果node的右孩子存在,则:
                stack[stackSize] = node->rchild;    //右孩子入栈
                stackSize++;              //栈的大小增加
            }
            node = node->lchild;          //node设置成node的左孩子
        }
    }
}

层序遍历

今天这篇工作量有点大,我翻了翻以前写的代码,直接用了。

原理:与非递归算法类似,但是调用的是队列,更简单。
一句话概括:开始根节点入队,执行循环,循环中将队列出队一个,输出数据,并将其左右孩子入队,直到队列空,循环结束。

也以六结点完全二叉树为例
根结点1入队
1出队,输出1数据,1的孩子2 3入队
2出队,输出2数据,2的孩子4 5入队
3出队,输出3数据,3的孩子6入队
4出队,输出4数据,无孩子入队
5出队,输出5数据,无孩子入队
6出队,输出6数据,无孩子入队
队列空,循环结束

typedef struct queue {//层序遍历存储队列单元
	BiTNode *node;
	struct queue *next;
}queue;

typedef struct linkQueue {//层序遍历存储队列
	queue *front;
	queue *rear;
}linkQueue;

void levelOrder(BiTNode *bTree) {//层序遍历
	BiTNode *temp = bTree;
	if (temp) {
		linkQueue linkQ;
		queue *q=(queue*)malloc(sizeof(queue));
		q->node = temp;
		q->next = NULL;
		linkQ.front = linkQ.rear = q;
		while (linkQ.front) {    //队列非空
			if (linkQ.front->node->lChild) {    //有左孩子,入队左孩子
				linkQ.rear->next = (queue*)malloc(sizeof(queue));
				linkQ.rear->next->node = linkQ.front->node->lChild;
				linkQ.rear = linkQ.rear->next;
				linkQ.rear->next = NULL;
			}
			if (linkQ.front->node->rChild) {    //有右孩子,入队右孩子
				linkQ.rear->next = (queue*)malloc(sizeof(queue));
				linkQ.rear->next->node = linkQ.front->node->rChild;
				linkQ.rear = linkQ.rear->next;
				linkQ.rear->next = NULL;
			}
			printf("%d ", linkQ.front->node->data);    //打印队头数据
			if(linkQ.front->next)linkQ.front = linkQ.front->next;    //队列非空,出队一个
			else break;    //队列空,结束循环
		}
		printf("\n");

	}
}

使用示例

//创建一个六结点完全二叉树
//下面这串创建二叉树的代码只是为了方便使用,用函数展示不太方便
//如果有人参考下面这个创建示例,请不要找我出医药费。
BiTNode *bTree = (BiTNode*)malloc(sizeof(BiTNode));
bTree->data = 1;
bTree->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->data = 2;
bTree->rchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->rchild->data = 3;
bTree->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->lchild->data = 4;
bTree->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->lchild->rchild->data = 5;
bTree->lchild->lchild->lchild = NULL;
bTree->lchild->lchild->rchild = NULL;
bTree->lchild->rchild->lchild = NULL;
bTree->lchild->rchild->rchild = NULL;
bTree->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
bTree->rchild->lchild->data = 6;
bTree->rchild->rchild = NULL;
bTree->rchild->lchild->lchild = NULL;
bTree->rchild->lchild->rchild = NULL;

//先序遍历
preOrderTraverse(bTree);
levelOrder(bTree);

//结束前暂停
system("PAUSE");

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注