学习笔记

数据结构与算法

1. 二叉树的二叉链结点结构

typedef struct Node  
{
    	DataType data;
	struct Node *LChild,*RChild;
	}BiTNode,*BiTree;  

2.用扩展先序遍历序列创建二叉树

void CreateBiTree(BiTree *root)    
{   
  char ch;
 	  ch=getchar();
	    if(ch==‘#‘)
	       *root=NULL;
		else
		{
			*root=(BiTree)malloc(sizeof(BiTNode));
	  			(*root)->data=ch;
	     		   CreateBiTree(&((*root)->LChild));
	       			  CreateBiTree(&((*root)->RChild));
	    }
}

3.先序遍历二叉树

void PreOrder(BiTree root)
{
		if(root!=NULL)
	{
			printf("%c",root->data);
	  			PreOrder(root->LChild);
  	    			PreOrder(root->RChild);

	}
}

4.中序遍历二叉树

     void InOrder(BiTree root)
   {
        if(root!=NULL)
	 {
			InOrder(root->LChild);
	 			 printf("%c",root->data);
	   				 InOrder(root->RChild);

 	 }
  }

5. 后序遍历二叉树

void PostOrder(BiTree root)
{
	if(root!=NULL)
 	{
    		PostOrder(root->LChild);
	  			PostOrder(root->RChild);
	   				printf("%c",root->data);
 	
 	}
}

6.输出叶子结点

   void PreleafOrder(BiTree root)  
   {
 	 	if(root!=NULL)
	 {
		if(root->LChild==NULL && root->RChild==NULL)
 		    printf("%c",root->data);
 		        PreleafOrder(root->LChild);
 		         	PreleafOrder(root->RChild);
	 }
   }

7.统计叶子结点数目

void  leaf(BiTree root)     
{
	    if(root!=NULL)
	{
 	  	leaf(root->LChild);
 			leaf(root->RChild);
 			    if(root->LChild==NULL&&root->RChild==NULL)
     				leafcount++;
}

}

8.先序遍历求树的高度

void  PreTreeDepth(BiTree root,int h)   
{  
	  if(root!=NULL)
	{   
      	if(h>depth) depth=h;                  /*如果该结点的层次值大于depth ,更新depth的值*/ 
		 	PreTreeDepth(root->LChild,h+1);          /*遍历左子树*/ 
				PreTreeDepth(root->RChild,h+1);          /*遍历右子树*/ 
 	} 
}

第八—九周 总结

这两周学了二叉树的定义，性质，链式存储结构。
1.定义：满足每个结点的度不大于2，每个结点的孩子结点次序不能任意颠倒。
2.性质。共5种。
性质1.在二叉树的第i层上最多有2^（i-1）个结点。
性质2.深度为K的二叉树，最多有2^k-1个结点。
性质3.对于任意一棵二叉树都满足，终端结点n0,其度为2的结点数n2，则n0=n2+1。
性质4.具有n个结点的完全二叉树的深度为[log2N]+1。
性质5.对于具有n个结点的完全二叉树，对于任意的序号为i的结点有：
1.如i=1,则序号为i的结点是根节点，无双亲结点；如i>1,则序号为i的双亲结点序号为[i/2]。
2.如2i>n,则序号为i的结点无左孩子,如2i<=n，则序号为i的结点的左孩子结点的序号是2i。
3.如2i+1>n,则序号为i的结点无右孩子,如2i+1<=n,则序号为i的结点的右孩子结点为2i+1。
3.二叉树的链式存储结构中，遍历的方法有三种。分别为先序遍历（DLR），中序遍历（LDR），后序遍历（LDR）。这三种方法都有用到递归的算法。的方法有三种。分别为先序遍历（DLR），中序遍历（LDR），后序遍历（LDR）。这三种方法都有用到递归的算法。

第八-九周学习笔记

原文：https://www.cnblogs.com/lan-adress/p/12811808.html