二叉树

二叉树

二叉树是只有左右结点的特殊的树，可以分为满二叉树和完全二叉树（完全二叉树是满二叉树的特殊形式）
结点个数 = 边的个数 + 1
对于完全二叉树而言 结点个数:2^n----->高度为log(n)

二叉树的基本操作

二叉树的创建

根据前序遍历创建

typedef struct Node {
 char val;
 struct Node *left;
 struct Node *right;
} Node;
typedef struct ReturnType {
 Node * root; // 创建好树的根节点
 int used;  // 创建树过程中用掉的值个数
} ReturnType;
ReturnType createTree(char preorder[], int size) {
 char rootValue = preorder[0];
 if (rootValue == '#') {
  ReturnType returnValue;
  returnValue.root = NULL;
  returnValue.used = 1;
  return returnValue;
  }
 Node * root = (Node *)malloc(sizeof(Node));
 root->val = rootValue;
ReturnType left = createTree(preorder + 1, size - 1);
ReturnType right = createTree(preorder + 1 + left.used,size - 1 - left.used);
  root->left = left.root;
  root->right = right.root;
  
  ReturnType returnValue;
  returnValue.root = root;
  returnValue.used = +left.used+right.used;
  
return returnValue;
}

二叉树的遍历

前序遍历：首先遍历根节点，再遍历左右结点（递归/非递归实现）
中序遍历：遍历左结点后遍历根节点，最后遍历右结点（递归/非递归）
后序遍历：先遍历左右结点，再遍历根节点（递归/非递归）
非递归遍历需要使用栈。

//递归遍历
//前序遍历
void PreorderTraval(Node* root)
{
 printf("%c ", root->val);
 PreorderTraval(root->left);
 PreorderTraval(root->right);
}
//中序遍历
void inorderTraval(Node* root)
{
 PreorderTraval(root->left);
 printf("%c ", root->val);
 PreorderTraval(root->right);
}
//后序遍历
void postorderTraval(Node* root)
{
 PreorderTraval(root->left);
 PreorderTraval(root->right);
 printf("%c ", root->val);
}
//非递归
//前序遍历
void preorder(Node* root)
{
 Node* cur = root;
 Node* top = NULL;
 stack S;
 stackInit(&S);
 while (cur || stackempty(&S)!=0)
 {
  while (cur)
  {
   printf("%c ", cur->val);
   stackpush(&S, cur);
   cur = cur->left;
	}
  top = stacktop(&S);
  stackpop(&S);
  cur = cur->right;
}
//中序遍历
void inorder(Node* root)
{
 Node* cur = root;
 Node* top = NULL;
 stack S;
 stackInit(&S);
 while (cur || stackempty(&S)!=0)
 {
  while (cur)
  {
   stackpush(&S, cur);
   cur = cur->left;
 }
  top = stacktop(&S);
  printf("%c ", top->val);
  stackpop(&S);
  cur=top->right;
  }
 
 //后序遍历
void inorder(Node* root)
{
 Node* cur = root;
 Node* top = NULL;
 Node* prev = NULL;
 stack S;
 stackInit(&S);
 while (cur || stackempty(&S)!=0)
 {
  while (cur)
  {
   stackpush(&S, cur);
   cur = cur->left;
   }
   top=stacktop(&S);
   if(top->right==NULL||top->right==prev)
   {
	printf("%c ",top->val);
	prev = top;
	stackpop(&S);
   }
   else
   cur = cur->right;
   }
}
//按层遍历
#include<queue>
void levelorder(Node* root)
{
	if(root==NULL)
		return;
	std::queue<Node*>   q;
	q.push(root);
	if(!q.empty())
	{
		Node* front = q.front();
		q,pop();
		printf("%c ",front->val);
		if(front->left != NULL)
			q.push(front->left);
		if(front->right != NULL)
			q.push(front->right);

	}
}

二叉树的结点数

递归求左右结点数，总结点数为左右结点数加1。

int GetNodeCount(Node* root)
{
 if (root == NULL)
  return;
 int left = GetNodeCount(root->left);
 int right = GetNodeCount(root->right);
 return left + right + 1;
}

二叉树的高度

递归：左右子树较高的加1。

int Mymax(int a,int b)
{
	return a>b?a:b;
}
int Height(Node* root)
{
 if (root == NULL)
  return 0;
 int left = Height(root->left);
 int right = Height(root->right);
 return Mymax(left, right) + 1;
 }

获取叶子结点

int GetLeafNodeCount(Node* root)
{
 if (root == NULL)
  return 0;
 if (root->right == NULL&&root->left == NULL)
  return 1;
 int left = GetLeafNodeCount(root->left);
 int right = GetLeafNodeCount(root->right);
 return right + left;
 }

获取第k层结点个数

利用递归求第k–,我们仅能知道第一层结点个数是1。

int GetKLevelNodeCount(Node* root, int k)
{
 if (root == NULL)
  return 0;
 if (k == 1)
  return 1;
 return GetKLevelNodeCount(root->left, k - 1) + GetKLevelNodeCount(root->right, k - 1);
 }

销毁二叉树

使用递归的方法从下往上销毁

void DestroyBinTree(Node* root)
{
 if (root)
 {
  DestroyBinTree(root->left);
  DestroyBinTree(root->right);
  free(root);
  }