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

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

阅读量：6592 次

发布时间：2019-06-24

本文共 30164 字，大约阅读时间需要 100 分钟。

【本文谢绝转载，原文来自】

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

二叉树的创建,关系建立

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c //二叉链表#include 
     
      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 
     
      #include 
      
       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 100typedef 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 
     
      #include 
      
       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 
     
      #include 
      
       #include 
       
        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 
     
      #include 
      
       #include 
       
        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     后序遍历叶子节点的个数 2chunli@http://990487026.blog.51cto.com~/binary_tree$

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

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c //树的遍历#include 
     
      #include 
      
       #include 
       
        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     后序遍历叶子节点的个数 2chunli@http://990487026.blog.51cto.com~/binary_tree$

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

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c //树的遍历#include 
     
      #include 
      
       #include 
       
        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 叶子节点的个数 2chunli@http://990487026.blog.51cto.com~/binary_tree$

求二叉树的高度:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c //树的遍历#include 
     
      #include 
      
       #include 
       
        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 树的高度 3chunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的拷贝:

chunli@http://990487026.blog.51cto.com~/binary_tree$ cat main.c //树的遍历#include 
     
      #include 
      
       #include 
       
        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中序遍历t14 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 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
           *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
          
            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 递归中序遍历t14 2 6 1 5 3 非递归中序遍历t14 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.h0 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 
     
      #include 
      
       #include 
       
        #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
        
          list(10);//创建顺序表	list.insert(t1,0);//头插法	list.insert(t2,0);//头插法	list.insert(t3,0);//头插法	//遍历链表	for(i=0;i
         
           0)	{		list.del(0,tmp);头删除		cout <
          
           <<" 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 
     
      #include "SeqList.h"template 
      
       SeqList
       
        ::SeqList(int Capacity){	this->pArray = new T[Capacity];	this->capacity = Capacity;	this->len = 0;}template 
        
         SeqList
         
          ::~SeqList(void){	delete [] this->pArray;	this->pArray = NULL;        this->capacity = 0;        this->len = 0;}template 
          
           int SeqList
           
            ::getLen(){ return this->len;}template 
            
             int SeqList
             
              ::getCapacity(){ return this->capacity;}template 
              
               int SeqList
               
                ::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 
                
                 int SeqList
                 
                  ::get(int pos,T &t){ if(pos <0) { return -1; } t = pArray[pos]; return 0;}template 
                  
                   int SeqList
                   
                    ::del(int pos,T &t){ int i = 0; t = pArray[pos]; for(i=pos+1;i
                    
                     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 oncetemplate 
     
      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  get32  get31  get33 del32 del31 delchunli@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 
     
      #include 
      
       #include 
       
        #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
        
          list(10);//创建顺序表	list.insert(p1,0);//头插法	list.insert(p2,0);//头插法	list.insert(p3,0);//头插法	//遍历链表	for(i=0;i
         
          age <<"  get\n";	}	//循环删除	while(list.getLen() > 0)	{		list.del(0,tmp);头删除		cout <
          
           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  get32  get31  get33 del32 del31 delchunli@http://990487026.blog.51cto.com~/binary_tree$

二叉树的创建 #号方法

chunli@http://990487026.blog.51cto.com~/tree_up$ cat main.c #include 
     
      #include 
      
       #include 
       
        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########123445678chunli@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.c0 directories, 5 files

源代码:

linklist.c

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linklist.c #include 
     
      #include 
      
       #include 
       
        #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
        
         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
         
          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
          
           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);#endifchunli@http://990487026.blog.51cto.com~/tree_2$

linkstack.c

chunli@http://990487026.blog.51cto.com~/tree_2$ cat linkstack.c #include 
     
      #include 
      
       #include 
       
        #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 
     
      #include 
      
       #include 
       
        #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$