0.二叉树结构体

typedef struct treenode{
	struct treenode * lchild,rchild;
	int info;
	int tag;
}*tree;

0.二叉树的建立

void buildtree(tree t)
{
	char ch;
	ch=getchar();
	if(ch='#') return t=NULL;
	else{
		t=(tree)malloc(sizeof(treenode));
		t->info=ch;
		t->lchild=NULL;
		t->rchild=NULL;
		buildtree(t->lchild);
		buildtree(t->rchild)
	}
}

1.前序递归

void preOrder(tree t)
{
	printf(”%d“,t->info);
	preOrder(t->lchild);
	preOrder(t->rchild);
}

2.递归后续

void lastOrder(tree t)
{
	preOrder(t->lchild);
	preOrder(t->rchild);
	printf(”%d“,t->info);
}

3.递归中序

void midOrder(tree t)
{
	preOrder(t->lchild);
	printf(”%d“,t->info);
	preOrder(t->rchild);
}

4.非递归前序

void preOrder(tree t)
{
	treenode *stack[10];
	treenode *p;
	p=t;
	int top=-1;
	while(p || top!=-1)
	{
		if(p)
		{
			top++;
			stack[top]=p;
			printf("%d",p->info);
			p=p->lchild;
		}else{
			p=stack[top];
			top--;
			p=p->rchild;
		}
	}
	
}

5.非递归中序

void preOrder(tree t)
{
	treenode *stack[10];
	treenode *p;
	p=t;
	int top=-1;
	while(p || top!=-1)
	{
		if(p)
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}else{
			p=stack[top];
			top--;
			printf("%d",p->info);
			p=p->rchild;
		}
	}
	
}

6.非递归后续

void preOrder(tree t)
{
	treenode *stack[10];
	treenode *p;
	p=t;
	int top=-1;
	while(p || top!=-1)
	{
		if(p)
		{
			top++;
			stack[top]=p;
			p=p->lchild;
		}else{
			p=stack[top];
			if(p->rchild&&p->rchild->tag==0)
				p=p-rchild;
			else{
				p=stack[top];
				top--;
				printf("%d",p->info);
				p->tag=1;
				p=NULL;
			}
		}
	}
	
}

7.递归树高 (***)

int depth(tree t)
{
	
	int lh,rh,h;
	if(t==NULL)return 0;
	else{
		lh=depth(t->lchild);
		rh=depth(t->rchild);
		if(lh>=rh)
			h=lh+1
		else
			h=rh+1;
	}
	return h;
}

8.非递归树高 (***)

int depth(tree t)
{
	if(t==NULL) return 0;
	treenode *s[10];
	treenode *p;
	int front=-1,rear=-1;
	int h=0,L=0;
	s[++rear]=t;
	if(front<rear)
	{
		p=s[++front];
		if(p->lchild) 
			s[++rear]=p->lchild;
		if(p->rchild) 
			s[++rear]=p->rchild;
		if(front==L)
		{
			L=rear;
			h++;
		}
	}
	return h;
}

9.前序遍历最后一个元素

void preOrderlast(tree t)
{
	if(t->rchild)
		t=preOrderlast(t->rchild);
	else
		t=preOrderlast(t->lchild);
	return t;
}

10.中序遍历第一个元素

void midOrderfirst(tree t)
{
	if(t->lchild)
		t=midOrderfirst(t->lchild);
	return t;
}

11.中序遍历最后一个元素

void midOrderlast(tree t)
{
	if(t->rchild)
		t=midOrderlast(t->rchild);
	return t;
}

12.后续遍历第一个元素

void postOrderfirst(tree t)
{
	if(t->lchild)
		t=postOrderfirst(t->lchild);
	else
		t=postOrderfirst(t->rchild);
	return t;
}

13.交换左右子树

void change(tree t)
{
	tree p;
	if(t)
	{
		p=t->rchild;
		t->rchild=t->lchild;
		t->lchild=t->rchild;
		change(t->lchild);
		change(t->rchild);
	}
}

14.双分支结点个数 (****)

int num(tree t)
{
	if(t==NULL)
		return 0;
	if(t->rchild&&t->lchild)
		return num(t->lchild)+num(t->rchild)+1;
	else
		return num(t->lchild)+num(t->rchild);
}

15.总结点个数

1.递归

int sum(tree t)
{
	if(!t) retrun 0;
	else{
		return sum(t->lchild)+sum(t->rchild)+1;
	}
16.叶子结点个数
1.递归
int CountLeafCount(tree t)
{
	if(t==NULL)
		return 0;
	if(t->lchild==NULL&&t->rchild==NULL)
		return 1;
	return CountLeafCount(t->rchild)+CountLeafCount(t->lchild);
}

2.非递归

int CountLeafCount(tree t)
{
	int count=0;
	int top=-1;
	tree stack[100];
	while(t!=NULL || top!=-1)
	{
		while(t!=NULL)
		{
			if(t->lchild==NULL&&t->rchild==NULL)
				count++;
			s[++top]=t;
			t=t->lchild;
		}
		if(top!=-1)
		{
			t=s[--top];
			t=t->rchild;
		}
	}
	return count;
}

17.第k层结点个数

/*
递归解法：
（1）如果二叉树为空或者k<1返回0
（2）如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
*/
int getCountK(tree t,int k)
{
	if(k<0 ||t==NULL) return 0;
	if(!t) return 0;
	if(k==1) return1;
	else
		return getCountK(t->lchild,k-1)+getCountK(t->rchild,k-1);
}

18.层序遍历 (****)

void levelOrder(tree t)
{
	squeue q[10];
	int front,rear,tag;
	front=rear=tag=0;
	treenode *p;
	EnQueue(q,t);
	while(!(front==rear&&tag==0))
	{
		DeQueue(q,p);
		printf("%c",p->info);
		if(p->lchild)
			EnQueue(q,p->lchild);
		if(p->rchild)
			EnQueue(q,p->rchild);
	}
}

19.判断二叉树等价 (****)

int isequal(tree t1,tree t2)
{
	int t;
	t=0;
	if(t1==NULL&&t2==NULL)
		return 1;
	else{
		if(t1!=NULL&&t2!=NULL)
			if(t1->info==t2->info)
				if(isequal(t->lchild,t->lchild))
					t=isequal(t->rchild,t->rchild)
	}
	return t;
}

20.查找第x结点 (****)

tree searchX(tree t,char x)
{
	if(t==NULL)
		return NULL;
	else{
		if(t->data == x) return t;
		else{
			p->searchX(t->lchild);
			if(p)
				return p;
			else
				p=searchX(t->rchild);
		}
	}
}

21.返回X结点所在二叉树的层数

int Level(tree t, char x,int h)
{
	int l;
	if (t == NULL)
		return 0;
	else if (t->data == x)
		return h;
	else
	{
		l = Level(t->lchild, x,h+1);
		if (l == 0)
			return Level(t->rchild, x, h + 1);
		else
			return l;
	}
}

22.根据前序和中序和长度，返回二叉树根地址

tree findKey(treenode* t, int key1, int key2) {
	 if (t == NULL) return NULL;

	 if (t->data == key1 || t->data == key2) return t;  // 1. 其中一个key在root上; 

	 treenode* left = findKey(t->lchild, key1, key2);
	 treenode* right = findKey(t->rchild, key1, key2);

	 if (left && right) return t;  // 2. key分布在两侧

	 if (left) return left;  // 3. key分布在一侧：左侧
	 if (right) return right;  // 3. key分布在一侧：右侧

	 return NULL;
 }

23.求公共祖先

typedef struct node /*二叉树结点定义*/
{
	char data;
	struct node* lchild, * rchild;
}bintnode;
typedef bintnode* bintree;
typedef struct stack //顺序栈结构定义
{
	bintree data[100];
	int tag[100];
	int top;
}seqstack;
void creat(bintree* t);
void SeekAncestor(bintree t, char x, char y, bintree* antor)
{
	seqstack s;
	bintree data[100] = { 0 };
	int i = 0, j;
	s.top = -1;
	while (t || s.top > -1)
	{
		while (t)
		{
			s.data[++s.top] = t;
			s.tag[s.top] = 0;
			t = t->lchild;
		}
		while (s.top > -1 && s.tag[s.top])
		{
			t = s.data[s.top];
			if (t->data == x)
				while (i <= s.top) //记录 x 结点的所有祖先结点
				{
					data[i] = s.data[i];
					i++;
				}
			else
				if (t->data == y)
				{
					while (s.top > -1)
					{
						j = i - 1;
						while (j >= 0 && t != data[j])
							//查找 y 与 x 的最近公共祖先结点
							j--;
						if (j >= 0)
						{
							*antor = data[j]; //返回公共祖先结点地址
							return;
						}
						t = s.data[--s.top];
					}
				}
			--s.top;
		}
		if (s.top > -1)
		{
			t = s.data[s.top];
			s.tag[s.top] = 1;
			t = t->rchild;
		}
		else t = NULL;
	}
}

24.二叉排序树

1.二叉排序树建立

treenode* buildBst()
{
    treenode *t = NULL;
    int data;
    printf("\n请输入666为结束标记");
    scanf("%d", &data);
    while (data != 666) 
    {
        InsertBstree(&t, data);
        scanf("%d", &data);
    }
    return t;
}

2.插入

treenode* InsertBstree(treenode* t, int data)
{
    treenode *temp, *p;
    p = t;
    while (p) 
    {
        if (data == p->data)return;//二叉排序树中已有此data不用插入
        temp = p;//用temp存储p
        p = (data < p->data) ? p->lchild : p->rchild;
    }
    p = (treenode*)malloc(sizeof(treenode));//生成待插入的新结点
    p->data = data;
    p->lchild = p->rchild = NULL;
    if (t == NULL) 
        t = p;
    else 
    {
        if (data < temp->data)
            temp->lchild = p;
        else
            temp->rchild = p;
    }
}

3.判断二叉排序树

int IsBST(const tree t)  //递归遍历二叉树是否为二叉排序树  
{
    if (!t)        //空二叉树情况  
        return 1;
    else if (!(t->lchild) && !(t->rchild))   //左右子树都无情况  
        return 1;
    else if ((t->lchild) && !(t->rchild))    //只有左子树情况  
    {
        if (t->lchild->data > t->data)
            return 0;
        else
            return IsBST(t->lchild);
    }
    else if ((t->rchild) && !(t->lchild))   //只有右子树情况  
    {
        if (t->rchild->data < t->data)
            return 0;
        else
            return IsBST(t->rchild);
    }
    else         //左右子树全有情况  
    {
        if ((t->lchild->data > t->data) || (t->rchild->data < t->data))
            return 0;
        else
            return (IsBST(t->lchild) && IsBST(t->rchild));
    }
}

25.穿线二叉树

1.结构体

typedef struct treenode {
	char data;
	struct treenode* lchild, * rchild;
	int ltag,rtag;
}treenode,*tree;

2.创建穿线二叉树

tree pre;   //  全局变量，始终指向刚刚访问过的结点
//    中序遍历进行中序线索化
void InThreading (tree p)
{
    if(p)
    {
        InThreading(p->lchild);    //  递归左子树线索化
        if(!p->lchild)     //    没有左孩子
        {
            p->LTag=Thread;  //前驱线索
            p->lchild=pre;   //左孩子的指针指向前驱
        }
        if(!pre->rchild)     //前驱没有右孩子
        {
            pre->RTag=Thread;  // 后继线索
            pre->rchild=p;
        }
        pre=p;    //  保持pre始终指向p的前驱
        InThreading(p->rchild);
    }
}

3.穿线二叉树线索化

void InThread(tree p, tree* pre) {
    // 中序遍历对二叉树线索化的递归算法
    if (p) {
        InThread(p->lchild, pre);       // 递归，线索化左子树
        if (!p->lchild) {               // 左子树为空，则建立前驱线索
            p->lchild = *pre;
            p->ltag = 1;
        }
        if (*pre && !(*pre)->rchild) {  // 建立前驱结点的后继线索
            (*pre)->rchild = p;
            (*pre)->rtag = 1;
        }
        *pre = p;                       // 标记当前结点成为刚刚访问过的结点
        InThread(p->rchild, pre);       // 递归，线索化右子树
    }
}

void CreateInThread(ThreadTree T)
{// 通过中序遍历建立中序线索二叉树的主过程
  ThreadTree pre = NULL;
  if (T) {                            // 非空二叉树，线索化
    InThread(T, &pre);                // 线索化二叉树
    pre->rchild = NULL;               // 处理遍历的最后一个结点
    pre->rtag = 1;
  }
}

4.中序遍历穿线二叉树

tree insuccnode(tree p) //寻找p结点中序下的后继结点
{
    tree q;
    if (p->rtag == 1)   //p的右指针为线索，恰巧指向p的后继结点
        return p->rchild;
    else
    {
        q = p->rchild;  //寻找p的右子树中最左下的结点
        while (q->ltag == 0)
            q = q->lchild;
        return q;
    }
}

5.中序遍历中序穿线二叉树

void inthrtree(tree p) 
{
    if (p)
    {
        while (p->ltag == 0)
            p = p->lchild;  //求p遍历下的第一个结点
        do
        {
            printf("%c", p->data);
            p = insuccnode(p);  //求p中序遍历下的后继结点
        } while (p);
        }
}

Q.E.D.