[数据结构与算法]数据结构C语言树

二叉树的存储结构
顺序存储：适合于完全二叉树

链式存储：
定义

typedef struct BTNode{
	char data;
	struct BTNode *lchild;
	struct BTNode *rchild;
}BTNode;

递归遍历：先序，中序，后序

先序

void preorder(BTNode *p){
	if(p!=NULL){
		Visit(p);
		preorder(p->lchild);
		preorder(p->rchild);
	}
}

中序

void inorder(BTNode *p){
	if(p!=NULL){
		inorder(p->lchild);
		Visit(p);
		inorder(p->rchild);
	}
}

后序

void postorder(BTNode *p){
	if(p!=NULL){
		postorder(p->lchild);
		postorder(p->rchild);
		Visit(p);
	}
}

写一个算法求一颗二叉树的高度

int getDepth(BTNode *p){
	int LD,RD;
	if(p==NULL)
		return 0
	else
	{
		LD=getDepth(p->lchild);
		RD=getDepth(p->rchild);
		return (LD>RD?LD:RD)+1;
	}
}

在一颗以二叉链表为存储结构的二叉树中，查找data域值等于key的结点是否存在（找到任何一个就可以），如果存在则将q指向该结点，否则q赋值为NULL
分析：三种遍历方法都可以查到一棵树的每一个结点

void search(BTNode *p,BTNode *&q ,int key)
//q定义为引用型指针因为q要改变
	if(p!=NULL){
		if(p->data==key)
			q=p;
		else
		{
			search(p->lchild,q,key);
			search(p->rchild,q,key);
		}
	}

假设二叉树采用二叉链表存储结构存储，输出先序遍历中第k个节点的值

int n=0;
void trave(BTNode *p,int k){
	if(p!=NULL){
		++n;
		if(k==n){
			cout<<p->data<<endl;
			return;
		}
		trave(p->lchild,k);
		trave(p->rchild,k);
	}
}

层次遍历
建立循环队列，先将二叉树头节点入队列，然后出队列，访问该结点，如果他有左子树，则将左子树的根节点入队，如果他有右子树，则将右子树的根节点入队，然后出队，对出队结点进行访问，如此反复，直至队列为空为止。

void level(BTNode *p){
	int front,rear;
	BTNode *que[maxSize];
	front=rear=0;
	BTNode *q;
	if(p!=NULL){
		rear=(rear+1)%maxSize;
		que[rear]=p;//根节点入队
		while(front!=rear){
			front=(front+1)%maxSize;
			q=que[front];
			Visit(q);
			if(q->lchild!=NULL){
				rear=(rear+1)%maxSize;
				que[rear]=q->lchild;
			}
			if(q->rchild!=NULL){
				rear=(rear+1)%maxSize;
				que[rear]=q->rchild;
			}
		}
	}
}