数据结构重读 – 二叉树

Leave a reply

1、二叉树(Binary Tree)是一种特殊的树形结构：每个结点至多有两棵子树，即二叉树中不存在度大于2的结点。

2、二叉树的子树有左右之分，次序不能任意颠倒。

3、性质1：二叉树的第i层上至多有2^(i-1)个结点，i从1下标开始。所有

4、性质2：深度为k的二叉树至多有2^k -1个结点，k也是从1下标开始。

5、性质3：对于任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则n0 = n2+1。这个很简单：

(1)设度为1的结点数为n1，则总结点数n = n0 + n1 + n2。
(2)根据先前的(任意树)上的公式：结点数量 = 所有结点度之和 + 1，即n = n0+ n1 + n2 = n1 + 2 n2 +1，两边消掉，有：

n0 = n2 + 1。

6、满二叉树：一棵深度为k，且有2^k -1个结点的二叉树。特点是每一层都是满的。

7、完全二叉树：不是满二叉树！它的结点可以不足2^k - 1，但是深度必须和对应的满二叉树对应，已经有的结点从1~k必须和同深度的满二叉树一一对应(即在满二叉树的第k层从右向左去掉若干个结点，至少保留一个结点)。

8、满二叉树是完全二叉树，但完全二叉树不是满二叉树！

9、性质4：具有n个结点的完全二叉树，深度为[ log(n)] + 1，其中[]是向下取整。

10、性质5：如果对一棵有n个结点的完全二叉树的结点按层次编号，每层从左到右，层次从上到下。假设根存储在1号单元(设下标从1开始)，对任意结点i，
(1) 如果i=1，结点i是二叉树的根，无双亲。i>1，则双亲PARENT(i)是结点[i/2]，还是向下取整。
(2) 如果2i>n，则结点无左孩子，否则左孩子是2i。
(3)如果2i+1>n，无右孩子，否则右孩子是2i+1。

如果下标从0开始，上述结论变成：

(1)双亲是i/2-1
(2)左孩子是2i+1，>n无左孩子。
(3)右孩子是2i+2，>n无右孩子。

11、二叉树的遍历，先序、中序、后序遍历分别对应着表达式：前缀表示(又叫波兰式)、中缀表示和后缀表示(又叫逆波兰式)。

二叉树的顺序存储

利用上述性质5，可以把任何一个二叉树映射到完全二叉树上，从而映射到数组上。当然这个数组的中间某些位置可能是“空的”。

代码：包含创建、先、中后序遍历(递归版本)

#include <stdio.h>
#include <string.h>
#define MAX 100
#define EMPTY_NODE -1

struct BiTree
{
	int data[MAX];
};

void btree_create(struct BiTree* tree, int* data, int n)
{
	int i = 0;
	memset(tree->data, -1, sizeof(int)*MAX);
	for(i = 0; i<n && i<MAX; i++)
	{
		tree->data[i] = data[i]; // EMPTY_NODE stores as EMPTY_NODE
	}
}

void btree_pre_order(struct BiTree* tree, int pos)
{
	int left = 0, right = 0;
	if(pos >=MAX || tree->data[pos]==EMPTY_NODE)
	{
		return ;
	}
	// Mid
	printf("%d ", tree->data[pos]);
	left = pos*2 + 1;
	right = pos*2 + 2;
	// Left, Right
	btree_pre_order(tree, left);
	btree_pre_order(tree, right);
	if(pos==0)
	{
		printf("\n");
	}
}

void btree_in_order(struct BiTree* tree, int pos)
{
	int left = 0, right = 0;
	if(pos >=MAX || tree->data[pos]==EMPTY_NODE)
	{
		return ;
	}
	// Left
	left = pos*2 + 1;
	btree_in_order(tree, left);
	// Mid
	printf("%d ", tree->data[pos]);
	// Right
	right = pos*2 + 2;
	btree_in_order(tree, right);
	if(pos==0)
	{
		printf("\n");
	}
}

void btree_post_order(struct BiTree* tree, int pos)
{
	int left = 0, right = 0;
	if(pos >=MAX || tree->data[pos]==EMPTY_NODE)
	{
		return ;
	}
	// Left
	left = pos*2 + 1;
	btree_post_order(tree, left);
	// Right
	right = pos*2 + 2;
	btree_post_order(tree, right);
	// Mid
	printf("%d ", tree->data[pos]);
	if(pos==0)
	{
		printf("\n");
	}
}

int main()
{
	int data[7] = {1, 2, 3, 4, 5, EMPTY_NODE, 7};
	struct BiTree tree;
	// Create
	btree_create(&tree, data, 7);
	// Pre-order print
	btree_pre_order(&tree, 0);
	// In-order print
	btree_in_order(&tree, 0);
	// Post-order print
	btree_post_order(&tree, 0);

	return 0;
}

下面来说说非递归的：

首先是先序非递归，很简单，就是先visit，然后右压栈，然后左压栈。

void btree_pre_order_fdg(struct BiTree* tree)
{
	struct Stack stack;
	int tmp;
	stack_init(&stack);
	stack_push(&stack, 0);
	while(!stack_is_empty(&stack))
	{
		if(stack_pop(&stack, &tmp)==0)
		{
			if(tree->data[tmp]!=EMPTY_NODE)
			{
				printf("%d ", tree->data[tmp]);
				stack_push(&stack, tmp*2+2); // stack push right first
				stack_push(&stack, tmp*2+1); // stack push left then
			}
		}
	}
	printf("\n");
}

下面讨论下非递归的版本：

首先中序非递归遍历，略复杂一点：
(1)先root入栈
(2)对所有左子树入栈，直到到达左下角。
(3)依次出栈，对每个出栈元素先visit，然后入右子树，也是循环，直到右下角。

void btree_in_order_fdg(struct BiTree* tree)
{
	struct Stack stack;
	int tmp;
	stack_init(&stack);
	stack_push(&stack, 0); // push root
	while(!stack_is_empty(&stack))
	{
		if(stack_top(&stack, &tmp)==0)
		{
			// Push all left children while not EMPTY_NODE
			while((tmp*2+1)<MAX && tree->data[(tmp*2+1)!=EMPTY_NODE])
			{
				tmp = tmp * 2 +1;
				stack_push(&stack, tmp);
			}

			// Pop one left, print current, push right
			while(!stack_is_empty(&stack))
			{
				if(stack_pop(&stack, &tmp)==0)
				{
					if(tree->data[tmp]!=EMPTY_NODE)
					{
						printf("%d ", tree->data[tmp]);
						if((tmp*2+2)<MAX && tree->data[(tmp*2+2)]!=EMPTY_NODE)
						{
							stack_push(&stack, tmp*2+2);
						}
					}
				}
			}
		}
	}
	printf("\n");
}

后序非递归：比较复杂，还没写出来。

层序遍历，需要借助队列，比较简单，代码如下：

void btree_level(struct BiTree* tree)
{
	struct Queue queue;
	int tmp;
	queue_init(&queue);
	queue_enqueue(&queue, 0); // enqueue root
	while(!queue_is_empty(&queue))
	{
		// Visit
		if(0==queue_dequeue(&queue, &tmp))
		{
			if(tmp<MAX && tree->data[tmp]!=EMPTY_NODE)
			{
				printf("%d ", tree->data[tmp]);
				// enqueue left and right
				queue_enqueue(&queue, tmp*2+1);
				queue_enqueue(&queue, tmp*2+2);
			}
		}
	}
}

二叉树的链式存储

基础部分不用多解释了。

#include <iostream>
#include <stack>

#define EMPTY_NODE -1

struct BiTree
{
	struct BiTree* left;
	struct BiTree* right;
	int data;
	bool tag;
};

void bitree_init(struct BiTree* tree)
{
	tree->left = tree->right = NULL;
	tree->data = EMPTY_NODE;
}

// Use pre order with EMPTY flag to crate btree
int i = 0;
void bitree_create(struct BiTree*& tree, int* data, int n)
{
	if(i>=n || data[i]==EMPTY_NODE)
	{
		tree = NULL;
	}else
	{
		tree = new BiTree;
		tree->data = data[i];
		tree->tag = false;
		i++;
		bitree_create(tree->left, data, n);
		i++;
		bitree_create(tree->right, data, n);
	}
}

// Pre-order Traverse
void bitree_pre_order(struct BiTree* tree)
{
	if(tree && tree->data!=EMPTY_NODE)
	{
		::std::cout << tree->data << " ";
		bitree_pre_order(tree->left);
		bitree_pre_order(tree->right);
	}
}

// Post-order Traverse
void bitree_post_order(struct BiTree* tree)
{
	if(tree && tree->data!=EMPTY_NODE)
	{
		bitree_post_order(tree->left);
		bitree_post_order(tree->right);
		::std::cout << tree->data << " ";
	}
}

int main()
{
	struct BiTree* bt = NULL;
	int data[11] = {1, 2, 4, EMPTY_NODE, EMPTY_NODE, 5, EMPTY_NODE, EMPTY_NODE, 3, EMPTY_NODE, 7 };
	// BiTree create
	bitree_create(bt, data, 11);
	// Pre-order
	//bitree_pre_order(bt);
	//::std::cout << ::std::endl;
	// Post-order
	bitree_post_order(bt);
	::std::cout << ::std::endl;;
	return 0;
}

然后重点关注下非递归实现后序遍历：

算法分为三个部分：

(1)大循环，条件ptr!=NULL或者栈非空
(2)循环内1：压所有左子树，直到左下角
(3)循环内2：对于stack的top结点，如果是第一次visit(tag==false)，将它置为tag==true，然后ptr设为右子树。如果是第二次，说明右子树已经访问过了，直接访问自身，然后设置为NULL。

// Post-order Traverse
void bitree_post_order_fdg(struct BiTree* root)
{
	::std::stack<BiTree*> stk;
	BiTree* ptr = root;
	while(ptr!=NULL || !stk.empty())
	{
		// Push while has left children
		while(ptr!=NULL)
		{
			stk.push(ptr);
			ptr = ptr->left;
		}
		// Twice visit
		if(!stk.empty())
		{
			ptr = stk.top();
			if(!ptr->tag)
			{
				// First visit
				ptr->tag = true;
				ptr = ptr->right;
			} else
			{
				// Second visit, means right children has been visited
				::std::cout << ptr->data << " ";
				stk.pop();
				ptr = NULL;
			}
		}
	}
}

 二叉树求深度

采用递归的方法，max(左子树深度, 右子树深度) +1

int bitree_depth(struct BiTree* tree)
{
    if(tree==NULL)
    {   
        return 0;
    }else
    {   
        int ld = bitree_depth(tree->left);
        int rd = bitree_depth(tree->right);
        // return max(left_depth, right_depth) + 1
        return (ld>rd?ld:rd)+1;
    }   
}

 

 

 

您可能也喜欢如下文章:

  1. 数据结构重读 – 栈的基本操作
  2. 数据结构重读 – 循环队列
  3. 数据结构重读 - 线性表的链式存储
  4. 数据结构重读 – 队列 & 双端队列
  5. 数据结构重读 - 矩阵乘法

Leave a Reply

Your email address will not be published. Required fields are marked *