数据结构与算法 3:二叉树,遍历,创建,释放,拷贝,求高度,面试,线索树

【本文谢绝转载，原文来自http://990487026.blog.51cto.com】

树
数据结构与算法 3:二叉树,遍历,创建,释放,拷贝,求高度,面试,线索树
	二叉树的创建,关系建立
	二叉树的创建,关系建立2
	三叉链表法
	双亲链表:
	二叉树的遍历
	遍历的分析PPT
	计算二叉树中叶子节点的数目:使用全局变量计数器
	计算二叉树中叶子节点的数目:不使用全局变量计数器
	无论是先序遍历,中序遍历,后序遍历,求叶子的数字都不变;因为本质都是一样的,任何一个节点都会遍历3趟
	求二叉树的高度
	二叉树的拷贝:
	二叉树的遍历-中序遍历非递归算法`栈的非常经典案例
	二叉树的遍历-中序遍历非递归算法,STL代码实现
	利用C++ STL实现 顺序存储  泛型 API
	泛型编程的威力,指针搞起来
	二叉树的创建 #号方法
	面试题-画二叉树
	面试题-画二叉树2
	数据结构演示工具
	二叉树的非递归遍历,C语言基于栈API实现
	线索二叉树[很难]

二叉树的创建,关系建立

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//二叉链表

#include <stdio.h>

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

//推导
//struct BiTNode
//{
//	int data;
//	struct BiTNode *lchild;
//	struct BiTNode *rchild;
//};
//typedef struct BiTNode  BiTNode;
//typedef struct BiTNode* BiTree;

int main()
{
	//创建节点
	BiTNode t1;	t1.data = 1;
	BiTNode t2;	t1.data = 2;
	BiTNode t3;	t1.data = 3;
	BiTNode t4;	t1.data = 4;
	BiTNode t5;	t1.data = 5;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  && ./a.out 
chunli@http://990487026.blog.51cto.com~/binary_tree$

2:二叉树的创建,关系建立

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//二叉链表
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

int main()
{
	BiTNode *p1;	p1 = (BiTNode*)malloc(sizeof(BiTNode));
	BiTNode *p2;	p2 = (BiTNode*)malloc(sizeof(BiTNode));
	BiTNode *p3;	p3 = (BiTNode*)malloc(sizeof(BiTNode));
	BiTNode *p4;	p4 = (BiTNode*)malloc(sizeof(BiTNode));
	BiTNode *p5;	p5 = (BiTNode*)malloc(sizeof(BiTNode));
	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;
	
	//建立关系
	p1->lchild = p2;
	p1->rchild = p3;
	p2->lchild = p4;
	p3->rchild = p5;
	
	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  && ./a.out 
chunli@http://990487026.blog.51cto.com~/binary_tree$

三叉链表法

//三叉链表
typedef struct TriTNode 
{
	int data;
	//左右孩子指针
	struct TriTNode *lchild, *rchild;
	struct TriTNode *parent;
}TriTNode, *TriTree;

双亲链表:

//双亲链表
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{
	int data;
	int parentPosition; //指向双亲的指针 //数组下标
	char LRTag; //左右孩子标志域
}BPTNode;

typedef struct BPTree
{
	BPTNode nodes[100]; //因为节点之间是分散的，需要把节点存储到数组中
	int num_node;  //节点数目
	int root; //根结点的位置 //注意此域存储的是父亲节点在数组的下标
}BPTree;

//用这个数据结构能表达出一颗树。。。能，怎么表达？不能why

程序:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//二叉链表
#include <stdio.h>
#include <stdlib.h>
typedef struct BPNode
{
	int data;
	int parentPosition;
	char LRTag;
}BPTNode;

typedef struct BPtree
{
	BPTNode nodes[100];
	int num_node;
	int root;
}BPTree;


int main()
{
	BPTree tree;

	//节点属性数值
	//根节点
	tree.nodes[0].parentPosition = 10000;//定义10000为root节点,自己定

	//B节点
	tree.nodes[1].parentPosition = 0;//0号节点是老爹的
	tree.nodes[1].data = ‘B‘;
	tree.nodes[1].LRTag  = 1;
	
	//C节点
	tree.nodes[2].parentPosition = 0;//0号节点是老爹的
	tree.nodes[3].data = ‘C‘;
	tree.nodes[4].LRTag  = 2;
	
	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  -Wall && ./a.out 
main.c: In function ‘main’:
main.c:21:9: warning: variable ‘tree’ set but not used [-Wunused-but-set-variable]
  BPTree tree;
         ^
chunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的遍历

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void pre_Order(BiTNode * root)	//先序遍历
{
	if(root == NULL)
	{
		return ;
	}
	printf("%d ",root->data);
	pre_Order(root->lchild);//遍历左子树
	pre_Order(root->rchild);//遍历右子树
}

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}

void post_Order(BiTNode * root)	//后序遍历
{
	if(root == NULL)
	{
		return ;
	}
	post_Order(root->lchild);//遍历左子树
	post_Order(root->rchild);//遍历右子树
	printf("%d ",root->data);
}
int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	//树的遍历
	pre_Order(&t1);		printf("    先序遍历\n");
	in_Order(&t1);		printf("    中序遍历\n");
	post_Order(&t1);	printf("    后序遍历\n");
	
	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c   && ./a.out 
1 2 4 3 5     先序遍历
4 2 1 5 3     中序遍历
4 2 5 3 1     后序遍历
chunli@http://990487026.blog.51cto.com~/binary_tree$

计算二叉树中叶子节点的数目:使用全局变量计数器

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void pre_Order(BiTNode * root)	//先序遍历
{
	if(root == NULL)
	{
		return ;
	}
	printf("%d ",root->data);
	pre_Order(root->lchild);//遍历左子树
	pre_Order(root->rchild);//遍历右子树
}

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}

void post_Order(BiTNode * root)	//后序遍历
{
	if(root == NULL)
	{
		return ;
	}
	post_Order(root->lchild);//遍历左子树
	post_Order(root->rchild);//遍历右子树
	printf("%d ",root->data);
}

int  count_leaf(BiTNode * root)	//中序遍历
{
	static num = 0;
	if(root)
	{
		if(!root->rchild && !root->rchild)//当左右孩子都为空,就是叶子节点
		{
			num++;
		}
		if(root->rchild)
		{
			count_leaf(root->lchild);//遍历左子树
		}
		if(root->rchild)
		{
			count_leaf(root->rchild);//遍历右子树
		}
	}
	return num;
}
int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	//树的遍历
	pre_Order(&t1);		printf("    先序遍历\n");
	in_Order(&t1);		printf("    中序遍历\n");
	post_Order(&t1);	printf("    后序遍历\n");

	int num = count_leaf(&t1);
	printf("叶子节点的个数 %d\n",num);

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c   && ./a.out 
1 2 4 3 5     先序遍历
4 2 1 5 3     中序遍历
4 2 5 3 1     后序遍历
叶子节点的个数 2
chunli@http://990487026.blog.51cto.com~/binary_tree$

计算二叉树中叶子节点的数目:不使用全局变量计数器

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void pre_Order(BiTNode * root)	//先序遍历
{
	if(root == NULL)
	{
		return ;
	}
	printf("%d ",root->data);
	pre_Order(root->lchild);//遍历左子树
	pre_Order(root->rchild);//遍历右子树
}

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}

void post_Order(BiTNode * root)	//后序遍历
{
	if(root == NULL)
	{
		return ;
	}
	post_Order(root->lchild);//遍历左子树
	post_Order(root->rchild);//遍历右子树
	printf("%d ",root->data);
}

void count_leaf(BiTNode * root,int * num)	 
{
	if(!root)
	{
		return ;
	}
	if(!root->rchild && !root->rchild)//当左右孩子都为空
	{
		(*num)++;
	}
	if(root->lchild)
	{
		count_leaf(root->lchild,num);//遍历左子树
	}
	if(root->rchild)
	{
		count_leaf(root->rchild,num);//遍历右子树
	}
	return ;
}
int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	//树的遍历
	pre_Order(&t1);		printf("    先序遍历\n");
	in_Order(&t1);		printf("    中序遍历\n");
	post_Order(&t1);	printf("    后序遍历\n");

	int num = 0;
	count_leaf(&t1,&num);	//解决多线程,资源竞争问题
	printf("叶子节点的个数 %d\n",num);

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  -Wall && ./a.out 
1 2 4 3 5     先序遍历
4 2 1 5 3     中序遍历
4 2 5 3 1     后序遍历
叶子节点的个数 2
chunli@http://990487026.blog.51cto.com~/binary_tree$

无论是先序遍历,中序遍历,后序遍历,求叶子的数字都不变;因为本质都是一样的,任何一个节点都会遍历3趟

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void count_leaf(BiTNode * root,int * num)	//求叶子的个数
{
	if(!root)
	{
		return ;
	}
	if(root->lchild)
	{
		count_leaf(root->lchild,num);//遍历左子树
	}
	if(!root->rchild && !root->rchild)//当左右孩子都为空
	{
		(*num)++;
	}
	if(root->rchild)
	{
		count_leaf(root->rchild,num);//遍历右子树
	}
	return ;
}
int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;

	int num = 0;
	count_leaf(&t1,&num);	//解决多线程,资源竞争问题
	printf("叶子节点的个数 %d\n",num);

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  -Wall && ./a.out 
叶子节点的个数 2
chunli@http://990487026.blog.51cto.com~/binary_tree$

求二叉树的高度:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

int tree_dept(BiTNode * root)
{
	int depth_left = 0;
	int depth_right = 0;
	if(!root)
	{
		return 0;
	}
	depth_left = tree_dept(root->lchild);
	depth_right = tree_dept(root->rchild);
	return  1+(depth_left>depth_right ? depth_left:depth_right);
}
int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	BiTNode t6;	memset(&t6,0,sizeof(BiTNode));  t6.data = 6;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	t2.rchild = &t6;

	int depth = 0;
	depth = tree_dept(&t1);	//解决多线程,资源竞争问题
	printf("树的高度 %d\n",depth);

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  -Wall &&  ./a.out 
树的高度 3
chunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的拷贝:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c 
//树的遍历
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

int tree_dept(BiTNode * root)
{
	int depth_left = 0;
	int depth_right = 0;
	if(!root)
	{
		return 0;
	}
	depth_left = tree_dept(root->lchild);
	depth_right = tree_dept(root->rchild);
	return  1+(depth_left>depth_right ? depth_left:depth_right);
}

BiTNode* CopyTree(BiTNode *T)
{
	BiTNode *newNode = NULL;
	BiTNode *newLp = NULL;
	BiTNode *newRp = NULL;
	if(!T)
	{
		return NULL;
	}
	if(T->lchild)	//拷贝左子树
	{
		newLp = CopyTree(T->lchild);
	}
	else	//如果左子树为NULL
	{
		newLp = NULL;
	}

	if(T->rchild)//拷贝右子树
	{
		newRp = CopyTree(T->rchild);
	}
	else
	{
		newRp = NULL;
	}
	//拷贝根节点
	newNode = (BiTNode *)malloc(sizeof(BiTNode));
	memset(newNode,0,sizeof(BiTNode));
	if(!newNode)
	{
		return NULL;
	}
	newNode->lchild = newLp;
	newNode->rchild = newRp;
	newNode->data = T->data;	
	return newNode;
}

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}


int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	BiTNode t6;	memset(&t6,0,sizeof(BiTNode));  t6.data = 6;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	t2.rchild = &t6;

	int depth = 0;
	depth = tree_dept(&t1);	//解决多线程,资源竞争问题
	printf("树的高度 %d\n",depth);

	printf("中序遍历t1\n");
	in_Order(&t1);
	printf("\n");

	printf("中序遍历拷贝树\n");
	BiTNode *root = CopyTree(&t1);
	in_Order(root);
	printf("\n");
	

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ gcc main.c  -Wall  && ./a.out 
树的高度 3
中序遍历t1
4 2 6 1 5 3 
中序遍历拷贝树
4 2 6 1 5 3 
chunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的遍历-中序遍历非递归算法`栈的非常经典案例

中序 遍历的几种情况

分析1：什么时候访问根、什么时候访问左子树、什么访问右子树

       当左子树为空或者左子树已经访问完毕以后，再访问根

       访问完毕根以后，再访问右子树。

分析2：为什么是栈，而不是其他队列。

        先走到的后访问、后走到的先访问，显然是栈结构

分析3：结点所有路径情况

步骤1：

如果结点有左子树，该结点入栈；

如果结点没有左子树，访问该结点；

步骤2：

如果结点有右子树，重复步骤1；

如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1

如果栈为空，表示遍历结束。

注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

分析4：有一个一直往左走入栈的操作

二叉树的遍历-中序遍历非递归算法,STL代码实现

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.cpp 
//树的非递归遍历(中序遍历)
//	g++ main.cpp  -Wall  && ./a.out 
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}

BiTNode* go_left(BiTNode *T,stack<BiTNode *> *s)//一直往左走,直到找到中序遍历的起点,注意C++的引用*s->&s
{
	if(!T)
	{
		return NULL;
	}
	while(T->lchild)//如果T有左孩子,就入栈
	{
		//s.push(T);  如果上面参数带有引用
		(*s).push(T);
		T = T->lchild;
	}
	return T;//如果T没有左孩子,就返回
}

void in_Order2(BiTNode * T)
{
	stack<BiTNode *> s;//使用C++ STL库,当然也可以使用自己的栈API
	//BiTNode* t = go_left(T,s);//如果go_left函数参数是引用可以直接这么写
	BiTNode* t = go_left(T,&s);
	while(t)//回到了起点
	{
		printf("%d ",t->data);//打印 
		if(t->rchild)//如果有右子树
		{
			//t = go_left(t->rchild,s);//回到右子树中序遍历的起点,如果go_left函数参数是引用可以直接这么写	
			t = go_left(t->rchild,&s);//回到右子树中序遍历的起点	
		}
		else if (!s.empty())//如果t没有右子树,根据栈指示,回退
		{
			t = s.top();
			s.pop();
		}
		else//如果t没有右子树,且栈为空
		{
			t = NULL;
		}
	}
}

int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	BiTNode t6;	memset(&t6,0,sizeof(BiTNode));  t6.data = 6;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	t2.rchild = &t6;

	printf("递归中序遍历t1\n");
	in_Order(&t1);
	printf("\n");

	printf("非递归中序遍历t1\n");
	in_Order2(&t1);
	printf("\n");

	

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$ g++ main.cpp  -Wall  && ./a.out 
递归中序遍历t1
4 2 6 1 5 3 
非递归中序遍历t1
4 2 6 1 5 3 
chunli@http://990487026.blog.51cto.com~/binary_tree$

利用C++ STL实现 顺序存储  泛型 API

项目文件

chunli@http://990487026.blog.51cto.com~/binary_tree$ tree
.
├── main.cpp
├── SeqList.cpp
└── SeqList.h

0 directories, 3 files

main.c

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.cpp 
//g++ main.cpp  -Wall  && ./a.out 
//利用C++ STL实现 顺序存储  泛型 API

#include <iostream>
#include <stdio.h>
#include <string.h>
#include "SeqList.cpp"
using namespace std;

struct Teacher
{
	char name[64];
	int age;
};

void fun()
{
	int i = 0;
	struct Teacher  tmp;
	struct Teacher  t1;	t1.age = 31;
	struct Teacher  t2;	t2.age = 32;
	struct Teacher  t3;	t3.age = 33;
	
	SeqList<Teacher> list(10);//创建顺序表
	list.insert(t1,0);//头插法
	list.insert(t2,0);//头插法
	list.insert(t3,0);//头插法
	//遍历链表
	for(i=0;i<list.getLen();i++)
	{
		list.get(i,tmp);
		cout <<tmp.age <<"  get\n";
	}
	//循环删除
	while(list.getLen() > 0)
	{
		list.del(0,tmp);////头删除
		cout <<tmp.age <<" del\n";
	}
}

int main()
{
	fun();

	return 0;
}
chunli@http://990487026.blog.51cto.com~/binary_tree$

SeqList.cpp 

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat SeqList.cpp 
#include <stdio.h>
#include "SeqList.h"
template <typename T>
SeqList<T>::SeqList(int Capacity)
{
	this->pArray = new T[Capacity];
	this->capacity = Capacity;
	this->len = 0;
}

template <typename T>
SeqList<T>::~SeqList(void)
{
	delete [] this->pArray;
	this->pArray = NULL;
        this->capacity = 0;
        this->len = 0;

}

template <typename T>
int SeqList<T>::getLen()
{
	return this->len;
}

template <typename T>
int SeqList<T>::getCapacity()
{
	return this->capacity;
}

template <typename T>
int SeqList<T>::insert(T &t,int pos)
{
	int i = 0;
	if(pos <0)
	{
		return -1;
	}
	for(i=this->len;i>pos;i--)
	{
		pArray[i] = pArray[i-1];
	}
	pArray[i] = t;//STL元素保存时,通过复制机制实现的,你的类要可以复制才行
	this->len++;
	return 0;
}

template <typename T>
int SeqList<T>::get(int pos,T &t)
{
	if(pos <0)
	{
		return -1;
	}
	t = pArray[pos];
	return 0;
}

template <typename T>
int SeqList<T>::del(int pos,T &t)
{
	int i = 0;
	t = pArray[pos];
	for(i=pos+1;i<this->len;i++)
	{
		pArray[i-1] = pArray[i];
	}
	this->len--;
	return 0;
}



chunli@http://990487026.blog.51cto.com~/binary_tree$

SeqList.h

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat SeqList.h
#pragma once
template <typename T>
class SeqList
{
public:
	SeqList(int Capacity);
	~SeqList(void);
	int getLen();
	int getCapacity();
	int insert(T &t,int pos);
	int get(int pos,T &t);
	int del(int pos,T &t);
private:
	int len;
	int capacity;
	T *pArray;	

};
chunli@http://990487026.blog.51cto.com~/binary_tree$

编译运行

chunli@http://990487026.blog.51cto.com~/binary_tree$ g++ main.cpp SeqList.cpp -Wall  && ./a.out 
33  get
32  get
31  get
33 del
32 del
31 del
chunli@http://990487026.blog.51cto.com~/binary_tree$

泛型编程的威力,指针搞起来

主程序稍作修改,其他都不变:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.cpp 
//g++ main.cpp  -Wall  && ./a.out 
//利用C++ STL实现 顺序存储  泛型 API

#include <iostream>
#include <stdio.h>
#include <string.h>
#include "SeqList.cpp"
using namespace std;

struct Teacher
{
	char name[64];
	int age;
};

void fun()
{
	int i = 0;
	struct Teacher  *tmp;
	struct Teacher  t1;	t1.age = 31;
	struct Teacher  t2;	t2.age = 32;
	struct Teacher  t3;	t3.age = 33;
	
	struct Teacher  *p1 = &t1;	
	struct Teacher  *p2 = &t2;	
	struct Teacher  *p3 = &t3;	

	SeqList<Teacher *> list(10);//创建顺序表
	list.insert(p1,0);//头插法
	list.insert(p2,0);//头插法
	list.insert(p3,0);//头插法
	//遍历链表
	for(i=0;i<list.getLen();i++)
	{
		list.get(i,tmp);
		cout <<tmp->age <<"  get\n";
	}
	//循环删除
	while(list.getLen() > 0)
	{
		list.del(0,tmp);////头删除
		cout <<tmp->age <<" del\n";
	}
}

int main()
{
	fun();

	return 0;
}

编译运行:
chunli@http://990487026.blog.51cto.com~/binary_tree$ g++ main.cpp SeqList.cpp -Wall  && ./a.out 
33  get
32  get
31  get
33 del
32 del
31 del
chunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的创建 #号方法

chunli@http://990487026.blog.51cto.com~/tree_up$ cat main.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

void in_Order(BiTNode * root)	//先序遍历
{
	if(root == NULL)
	{
		return ;
	}
	printf("%c",root->data);
	in_Order(root->lchild);//遍历左子树
	in_Order(root->rchild);//遍历右子树
}

BiTNode* create_tree()//先序创建
{
	BiTNode *node = NULL;
	BiTNode *pleft  = NULL;
	BiTNode *pright = NULL;
	char c = getchar();	
	if(c == ‘#‘)
	{
		return NULL;
	}
	else
	{
		node = (BiTNode*)malloc(sizeof(BiTNode));
		memset(node,0,sizeof(BiTNode));
		node->data = c;

		pleft = create_tree();
		if(pleft != NULL)
		{
			node->lchild = pleft;
		}
		else
		{
			node->lchild = NULL;
		}
		
		pright = create_tree();
		if(pleft != NULL)
		{
			node->rchild = pright;
		}
		else
		{
			node->rchild = NULL;
		}
	}
	return node;	
}

void free_tree(BiTNode* T)
{
	if(!T)
	{
		return ;
	}
	if(T->lchild)
	{
		free_tree(T->lchild);
		T->lchild = NULL;
	}
	if(T->rchild)
	{
		free_tree(T->rchild);
		T->rchild = NULL;
	}
	if(T)
	{
		free(T);
		T = NULL;
	}
}

int  main()
{
	BiTNode *p = create_tree();	
	in_Order(p);			printf("\n");
	free_tree(p);
	return 0;
}
chunli@http://990487026.blog.51cto.com~/tree_up$ 
chunli@http://990487026.blog.51cto.com~/tree_up$ gcc main.c  -Wall  -g && ./a.out 
1234##45678########
123445678
chunli@http://990487026.blog.51cto.com~/tree_up$

面试题-画二叉树

面试题-画二叉树2

数据结构演示工具

二叉树的非递归遍历,C语言基于栈API实现

项目文件:

chunli@http://990487026.blog.51cto.com~/tree_2$ tree
.
├── linklist.c
├── linklist.h
├── linkstack.c
├── linkstack.h
└── main.c
0 directories, 5 files

源代码:

linklist.c 

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linklist.c 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "linklist.h"

typedef struct _tag_LinkList
{
	//这个句柄里面，需要保存所有节点信息。需要有一个起始点
	//就是带头节点的链表。。。
	LinkListNode header;
	int length;
}TLinkList;

LinkList* LinkList_Create()
{
	TLinkList *ret = (TLinkList *)malloc(sizeof(TLinkList));
	if (ret == NULL)
	{
		return NULL;
	}
	//memset(ret, 0, sizeof(TLinkList));
	ret->header.next = NULL;
	ret->length = 0;
	return ret;
}

void LinkList_Destroy(LinkList* list)
{
	if (list == NULL)
	{
		return ;
	}
	free(list);
	return ;
}

void LinkList_Clear(LinkList* list)
{

	TLinkList *tList =NULL;
	
	if (list == NULL)
	{
		return ;
	}
	tList = (TLinkList *)list;
	tList->length = 0;
	tList->header.next = NULL;
	return ;
}

int LinkList_Length(LinkList* list)
{

	TLinkList *tList = (TLinkList *)list;
	if (tList == NULL)
	{
		return -1;
	}

	return tList->length;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;

	tList = (TLinkList *)list;

	if (list==NULL || node==NULL) //modify by bombing 2014.06.26
	{
		return -1;
	}

	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}

	//让node节点链接后续链表
	node->next = current->next ;
	//让前边的链表。链接node
	current->next = node;
	tList->length ++;	
	return 0;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{

	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;
	LinkListNode *ret = NULL;
	tList = (TLinkList *)list;

	if (list == NULL || pos <0 ||pos>=tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;

	return ret;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
	int i = 0;

	TLinkList *tList  = NULL;
	LinkListNode *current = NULL;
	LinkListNode *ret = NULL;
	tList = (TLinkList *)list;

	if (list == NULL || pos <0 ||pos>=tList->length)
	{
		return NULL;
	}
	//准备环境让辅助指针变量 指向链表头节点
	current = &tList->header;
	for (i=0; i<pos &&(current->next!=NULL); i++)
	{
		current = current->next;
	}
	ret = current->next;

	//删除算法
	current->next =ret->next;
	tList->length--;

	return ret;
}
chunli@http://990487026.blog.51cto.com~/tree_2$

linklist.h

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linklist.h
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_

typedef void LinkList;
/*
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{
	LinkListNode* next;
};
*/
typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* next;
}LinkListNode;

LinkList* LinkList_Create();

void LinkList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif


chunli@http://990487026.blog.51cto.com~/tree_2$

linkstack.c

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linkstack.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linkstack.h"
#include "linklist.h"
typedef struct linkstack_node
{
	LinkListNode node;//让万象包含链表
	void *item;	//栈的业务节点
}linkstack_node;


LinkStack* LinkStack_Create()//创建一个栈,相当于创建一个线性表
{
	return LinkList_Create();
}

void LinkStack_Destroy(LinkStack* stack)//销毁一个栈,相当于销毁一个线性表
{
	LinkStack_Clear(stack);
	LinkList_Destroy(stack);
	return ;
}

void LinkStack_Clear(LinkStack* stack)//清空一个栈,相当于清空一个线性表
{
	//清空栈的时候,涉及到元素生命周期管理
	if(stack == NULL)
	{
		return;
	}
	while(LinkStack_Size(stack) > 0)
	{
		LinkStack_Pop(stack);//释放链表节点
	}
	return ;
}

int LinkStack_Push(LinkStack* stack, void* item)//向线性表的头部插入元素
{
	linkstack_node *tmp = (linkstack_node*)malloc(sizeof(linkstack_node));
	if(tmp == NULL)
	{
		return -1;
	}
	memset(tmp,0,sizeof(linkstack_node));
	tmp->item = item;
	int ret = LinkList_Insert(stack,(LinkListNode*)tmp,0);//把数据转换成链表的业务节点
	if(ret != 0)
	{
		printf("数据插入失败!\n");
		if(tmp != NULL)//业务失败时,及时释放内存
		{
			free(tmp);
		}
		return -2;
	}
	return 0;
}

void* LinkStack_Pop(LinkStack* stack)//相当于从线性表的头部弹出元素
{
	linkstack_node *tmp = NULL;//返回一个linkstack_node
	tmp = (linkstack_node *)LinkList_Delete(stack,0);//把链表节点转成业务节点
	if(tmp == NULL)
	{
		return NULL;
	}
	void *item = tmp->item;//还原业务节点
	free(tmp);		//干掉链表节点
	return item;
}

void* LinkStack_Top(LinkStack* stack)//获取栈顶元素
{
	linkstack_node *tmp = (linkstack_node *)LinkList_Get(stack,0);
	if(tmp == NULL)
	{
		return NULL;
	}
	return tmp->item;
}

int LinkStack_Size(LinkStack* stack)//求栈的大小,相当于求线性表的额length
{
	return LinkList_Length(stack);
}

chunli@http://990487026.blog.51cto.com~/tree_2$

linkstack.h

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linkstack.h
#ifndef _MY_LINKSTACK_H_
#define _MY_LINKSTACK_H_

typedef void LinkStack;

LinkStack* LinkStack_Create();

void LinkStack_Destroy(LinkStack* stack);

void LinkStack_Clear(LinkStack* stack);

int LinkStack_Push(LinkStack* stack, void* item);

void* LinkStack_Pop(LinkStack* stack);

void* LinkStack_Top(LinkStack* stack);

int LinkStack_Size(LinkStack* stack);

#endif //_MY_LINKSTACK_H_

chunli@http://990487026.blog.51cto.com~/tree_2$ 


chunli@http://990487026.blog.51cto.com~/tree_2$ cat main.c 
//非递归遍历二叉树,栈模式API实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linklist.h"
#include "linklist.h"
#include "linkstack.h"

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;

BiTNode * goleft(BiTNode *T,LinkStack *s)
{
	int ret = 0;
	if(T == NULL)
	{
		return NULL;
	}
	while(T->lchild != NULL)
	{
		ret = LinkStack_Push(s,(void*)T);//压栈
		if(ret != 0)
		{
			printf("error in LinkStack_Push \n");
		}
		T = T->lchild;
	}
	return T;
}

void tree_print(BiTNode *root)
{
	if(!root)
	{
		return ;
	}
	LinkStack *stack = LinkStack_Create();//创建栈
	if(stack == NULL)
	{
		printf("error in LinkStack_Create\n");
	}
	BiTNode *tmp_node = goleft(root,stack);
	while(tmp_node)
	{
		printf("%d ",tmp_node->data);
		if(tmp_node->rchild != NULL)
		{
			tmp_node = goleft(tmp_node->rchild,stack);
		}
		else if(LinkStack_Size(stack)>0)
		{
			tmp_node = (BiTNode *)LinkStack_Top(stack);
			LinkStack_Pop(stack);
		}
		else
		{
			tmp_node = NULL;
		}
	}
	printf("\n");
}

void in_Order(BiTNode * root)	//中序遍历
{
	if(root == NULL)
	{
		return ;
	}
	in_Order(root->lchild);//遍历左子树
	printf("%d ",root->data);
	in_Order(root->rchild);//遍历右子树
}



int main()
{
	//创建节点
	BiTNode t1;	memset(&t1,0,sizeof(BiTNode));	t1.data = 1;
	BiTNode t2;	memset(&t2,0,sizeof(BiTNode));  t2.data = 2;
	BiTNode t3;	memset(&t3,0,sizeof(BiTNode));  t3.data = 3;
	BiTNode t4;	memset(&t4,0,sizeof(BiTNode));  t4.data = 4;
	BiTNode t5;	memset(&t5,0,sizeof(BiTNode));  t5.data = 5;
	BiTNode t6;	memset(&t6,0,sizeof(BiTNode));  t6.data = 6;
	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t3.lchild = &t5;
	t2.rchild = &t6;
	printf("  递归遍历");	in_Order(&t1);	printf("\n");
	printf("非递归遍历");	tree_print(&t1);
	return 0;
}
chunli@http://990487026.blog.51cto.com~/tree_2$

编译运行:

chunli@http://990487026.blog.51cto.com~/tree_2$ gcc main.c linkstack.c linklist.c  -Wall -g && ./a.out 
  递归遍历4 2 6 1 5 3 
非递归遍历4 2 6 1 5 3 
chunli@http://990487026.blog.51cto.com~/tree_2$

线索二叉树[很难]

chunli@http://990487026.blog.51cto.com~/tree_3$ cat main.c 
#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link==0表示指向左右孩子指针, */
										/* Thread==1表示指向前驱或后继的线索 */
typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

TElemType Nil=‘#‘; /* 字符型以空格符为空 */

Status visit(TElemType e)
{
	printf("%c ",e);
	return OK;
}

/* 按前序输入二叉线索树中结点的值,构造二叉线索树T */
/* 0(整型)/空格(字符型)表示空结点 */
Status CreateBiThrTree(BiThrTree *T)
{ 
	TElemType h;
	scanf("%c",&h);

	if(h==Nil)
		*T=NULL;
	else
	{
		*T=(BiThrTree)malloc(sizeof(BiThrNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=h; /* 生成根结点(前序) */
		CreateBiThrTree(&(*T)->lchild); /* 递归构造左子树 */
		if((*T)->lchild) /* 有左孩子 */
			(*T)->LTag=Link;
		CreateBiThrTree(&(*T)->rchild); /* 递归构造右子树 */
		if((*T)->rchild) /* 有右孩子 */
			(*T)->RTag=Link;
	}
	return OK;
}

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

/* 中序遍历二叉树T,并将其中序线索化,Thrt指向头结点 */
Status InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ 
	*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
	if(!*Thrt)
		exit(OVERFLOW);
	(*Thrt)->LTag=Link; /* 建头结点 */
	(*Thrt)->RTag=Thread;
	(*Thrt)->rchild=(*Thrt); /* 右指针回指 */
	if(!T) /* 若二叉树空,则左指针回指 */
		(*Thrt)->lchild=*Thrt;
	else
	{
		(*Thrt)->lchild=T;
		pre=(*Thrt);
		InThreading(T); /* 中序遍历进行中序线索化 */
		pre->rchild=*Thrt;
		pre->RTag=Thread; /* 最后一个结点线索化 */
		(*Thrt)->rchild=pre;
	}
	return OK;
}

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根结点 */
	while(p!=T)
	{ /* 空树或遍历结束时,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		if(!visit(p->data)) /* 访问其左子树为空的结点 */
			return ERROR;
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data); /* 访问后继结点 */
		}
		p=p->rchild;
	}
	return OK;
}

int main()
{
	BiThrTree H,T;
	printf("请按前序输入二叉树(如:‘ABDH##I##EJ###CF##G##‘)\n");
 	CreateBiThrTree(&T); /* 按前序产生二叉树 */
	InOrderThreading(&H,T); /* 中序遍历,并中序线索化二叉树 */
	printf("中序遍历(输出)二叉线索树:\n");
	InOrderTraverse_Thr(H); /* 中序遍历(输出)二叉线索树 */
	printf("\n");
	return 0;
}



chunli@http://990487026.blog.51cto.com~/tree_3$ gcc main.c -Wall && ./a.out 
请按前序输入二叉树(如:‘ABDH##I##EJ###CF##G##‘)
ABDH##I##EJ###CF##G## 
中序遍历(输出)二叉线索树:
H D I B J E A F C G 
chunli@http://990487026.blog.51cto.com~/tree_3$

霍夫曼树(最优二叉树)

【本文谢绝转载，原文来自http://990487026.blog.51cto.com】

本文出自 “魂斗罗” 博客，谢绝转载！

数据结构与算法 3:二叉树,遍历,创建,释放,拷贝,求高度,面试,线索树

原文：http://990487026.blog.51cto.com/10133282/1852987