数据结构重读 – 二叉树

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;
    }   
}

 

 

 

Leave a Reply

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