二叉树（2）之二叉树的基本操作（遍历，找节点个数）

全栈程序员-站长 • 2021年9月28日上午6:00 • 未分类 • 阅读 55

最难的也就是层次遍历：各种遍历函数其实就是各种递归。叶子节点，深度，总节点，掌握性质都不难‘’

层次遍历

层次遍历，就是从上到下一层一层的遍历
例如：

思路：

这里写图片描述

上代码：层次遍历暂时没用真正的队列不够原理上是一样的。（以后能力提高了在搞）

#include<algorithm> 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
using namespace std;
typedef struct bitnode//处理前面和这有关后面基本上和这无关 
{
	char  data;//shurudshuju
    struct	bitnode *lchild, *rchild; //houzaohanshu
}bitnode, *bittree;
void create(bittree &t)
{
	char c;
	cin >> c;
	if(c=='#')
		t = NULL ;
	else 
	{
		t=new bitnode;
		t->data = c;	
		create(t->lchild);
		create(t->rchild);
	 } 
}
void xianxu(bittree t)
{
	if(t==NULL)
		return ;
	else
	{
		cout<<t->data;
		xianxu(t->lchild);
		xianxu(t->rchild);
	}
}
void zhongxu(bittree t)
{
	if(t==NULL)
		return  ;
	else
	{
		zhongxu(t->lchild);
		cout<<t->data;
		zhongxu(t->rchild);
	} 
}
void houxu(bittree t)
{
	if(t==NULL)
		return ;
	else 
	{
		houxu(t->lchild);
		houxu(t->rchild);
		cout<<t->data;
	}
}
int deep(bittree t)
{
	int d1=0,d2=0;
	if(t==NULL)
		return 0;
	else 
	{
		d1=deep(t->lchild)+1;
		d2=deep(t->rchild)+1;
	}
	return d1>=d2?d1:d2;
}
//yezhishu
int yezhi(bittree t)
{
	if(t==NULL)
	return 0;
	if(t->lchild==NULL&&t->rchild==NULL)
	return 1;
	else 
	{
		return yezhi(t->lchild) + yezhi(t->rchild);
	}
}
int jiedian(bittree t)
{
	if(t == NULL)
	return 0;
	else
		return jiedian(t->lchild)+jiedian(t->rchild)+1;
}
void cengci(bittree t)
{
	bittree q;
	bittree queue[10];
	int front = 0, rear = 0;
	if(t == NULL)
		return ;
	else 
	{
		rear = (rear+1)%10;
		queue[rear]=t;
		while(front!=rear)
		{
			front=(front+1)%10;
			q=queue[front];
			cout<<q->data;
			if(q->lchild!=NULL)
			{
				rear=(rear+1)%10;
				queue[rear]=q->lchild;
			}
			if(q->rchild!=NULL)
			{
				rear = (rear+1)%10;
				queue[rear]=q->rchild;
			}
		}
	}
} 
int main()
{
	bittree T;
	cout<<"jianshu:"<<endl;
	create(T);
	cout<<endl;
	cout<<"qianxu:"<<endl;
	xianxu(T);
	cout<<endl;
	cout<<"zhongxu"<<endl;
	zhongxu(T);
	cout<<endl;
	cout<<"houxu"<<endl;
	houxu(T);
	cout<<endl;
	cout<<yezhi(T)<<" "<<jiedian(T)<<"  "<<deep(T)<<endl;
	cengci(T);
	return 0;
}
//ABC##DE#G##F###

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114882.html原文链接：https://javaforall.net