BTree非递归

小鱼儿 2023-08-17 15:15 131阅读 0赞

preorder

void PreOrder(BTNode* b)
    {
    	BTNode* p = b;
    	SqStack* st;
    	InitStack(st);
    	if (b != NULL)
    	{
    		Push(st, p);
    		while (!StackEmpty(st))
    		{
    			Pop(st,p);
    			printf("%c", p->data);
    			if (p->rchild != NULL)
    			{
    				Push(st,p->rchild);
    			}
    			if (p->lchild != NULL)
    			{
    				Push(st,p->lchild);
    			}
    		}
    		printf("\n");
    	}
    	DestroyStack(st);
    }

void PreOrder1(BTNode* b)
    {
    	BTNode* p = b;
    	SqStack* st;
    	InitStack(st);
    	while(p != NULL || !StackEmpty(st))
    	{
    		while (p != NULL)
    		{
    			printf("%c", p->data);
    			Push(st,p);
    			p = p->lchild;
    		}
    		if (!StackEmpty(st))
    		{
    			Pop(st, p);
    			p = p->rchild;
    		}
    	}
    	printf("\n");
    	DestroyStack(st);
    }

inorder

void InOrder(BTNode* b)
    {
    	BTNode* p = b;
    	SqStack* st;
    	InitStack(st);
    
    	while (p != NULL || !StackEmpty(st))
    	{
    		while (p != NULL)
    		{
    			Push(st,p);
    			p = p->lchild;
    		}
    		if (!StackEmpty(st))
    		{
    			Pop(st, p);
    			printf("%c", p->data);
    			p = p->rchild;
    		}
    	}
    	printf("\n");
    	DestroyStack(st);
    }

postorder

void PostOrder(BTNode* b)
    {
    	BTNode* p = b;
    	BTNode* r;
    	SqStack* st;
    	InitStack(st);
    	bool flag;
    	do
    	{
    		while (p != NULL)
    		{
    			Push(st,p);
    			p = p->lchild;
    		}
    		r = NULL;
    		flag= true;
    		while (!StackEmpty(st) && flag)
    		{
    			GetTop(st, p);
    			if (r == NULL&&p->rchild==NULL)
    			{
    				printf("%c", p->data);
    				Pop(st, p);
    				r = (BTNode*)malloc(sizeof(BTNode));
    				r->data = p->data;
    			}
    			else if ((r != NULL&&p->rchild!=NULL)&&r->data==p->rchild->data)
    			{
    				printf("%c", p->data);
    				Pop(st, p);
    				r = (BTNode*)malloc(sizeof(BTNode));
    				r->data = p->data;
    			}
    			else
    			{
    				p = p->rchild;
    				flag = false;
    			}
    		}
    	} while (!StackEmpty(st));
    	printf("\n");
    	DestroyStack(st);
    }

层次遍历

typedef struct {
    	BTNode data[MAXSIZE];
    	int front, rear;
    }SqQueue;

void LevelOrder(BTNode* b)
    {
    	SqQueue* q;
    	InitQueue(q);
    	BTNode* p = b;
    	enQueue(q,p);
    	while (!QueueEmpty(q))
    	{
    		deQueue(q, p);
    		printf("%c", p->data);
    		if (p->lchild != NULL)
    			enQueue(q, p->lchild);
    		if (p->rchild != NULL)
    			enQueue(q, p->rchild);
    	}
    }

利用层次遍历输出从根结点到每个叶子结点的逆路径

typedef struct {
    	BTNode* pt;
    	int parent;
    }NodeType;

typedef struct {
    	NodeType data[MAXSIZE];
    	int front, rear;
    }QuType

void AllPath2(BTNode* b)
    {
    	int k;
    	BTNode* p;
    	QuType* qu;
    	InitQueue2(qu);
    	NodeType* qelem = (NodeType*)malloc(sizeof(NodeType));
    	qelem->pt = b;
    	qelem->parent = -1;
    	enQueue2(qu,qelem);
    	while (!QueueEmpty2(qu))
    	{
    		deQueue2(qu, qelem);
    		p = qelem->pt;
    		if (p->lchild == NULL && p->rchild == NULL)
    		{
    			k = qu->front;
    			while (qu->data[k].parent != -1)
    			{
    				printf("%c", qu->data[k].pt->data);
    				k = qu->data[k].parent;
    			}
    			printf("%c\n", qu->data[k].pt->data);
    
    		}
    		if (p->lchild != NULL)
    		{
    			qelem->pt = p->lchild;
    			qelem->parent = qu->front;
    			enQueue2(qu, qelem);
    		}
    		if (p->rchild != NULL)
    		{
    			qelem->pt = p->rchild;
    			qelem->parent = qu->front;
    			enQueue2(qu, qelem);
    		}
    	}
    }

转载于:https://www.cnblogs.com/KIROsola/p/11439996.html